Minimum Add to Make Parentheses Valid Solutions in C++

/// Source : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13

#include <iostream>
#include <stack>

using namespace std;


/// Using Stack
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int minAddToMakeValid(string S) {

        stack<char> s;
        for(char c: S)
            if(c == '(')
                s.push(c);
            else{
                if(!s.empty() && s.top() == '(')
                    s.pop();
                else
                    s.push(c);
            }
        return s.size();
    }
};


int main() {

    cout << Solution().minAddToMakeValid("()))((") << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
/// Author : liuyubobobo
/// Time   : 2018-10-14

#include <iostream>
#include <stack>

using namespace std;


/// Using balance to record the stack top '(' size
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int minAddToMakeValid(string S) {

        int res = 0, bal = 0;
        for(char c: S)
            if(c == '(')
                res ++, bal ++;
            else{
                if(bal)
                    res --, bal --;
                else
                    res ++, bal = 0;
            }
        return res;
    }
};


int main() {

    cout << Solution().minAddToMakeValid("()))((") << endl;
    // 4

    return 0;
}