Score of Parentheses Solutions in C++

/// Source : https://leetcode.com/problems/score-of-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-06-23

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

/// Recursive
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int scoreOfParentheses(string S) {

        int res = 0;

        int left = 0;
        int start = 0;
        for(int i = 0 ; i < S.size() ; i ++){
            if(S[i] == '(')
                left ++;
            else{
                left --;
                if(left == 0){
                    res += score(S, start, i);
                    start = i + 1;
                }
            }
        }
        return res;
    }

private:
    int score(const string& s, int l, int r){

        if(l + 1 == r){
            assert(s[l] == '(' && s[r] == ')');
            return 1;
        }

        return 2 * scoreOfParentheses(s.substr(l + 1, r - l + 1 - 2));
    }
};


int main() {

    cout << Solution().scoreOfParentheses("()") << endl;
    cout << Solution().scoreOfParentheses("(())") << endl;
    cout << Solution().scoreOfParentheses("()()") << endl;
    cout << Solution().scoreOfParentheses("(()(()))") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/score-of-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-06-25

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

/// Recursive Optimized
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int scoreOfParentheses(string S) {

        return score(S, 0, S.size() - 1);
    }

private:
    int score(const string& s, int l, int r){

        int res = 0;

        int balance = 0;
        int start = l;
        for(int i = l ; i <= r ; i ++){
            if(s[i] == '(')
                balance ++;
            else{
                balance --;

                if(balance == 0){
                    if(l + 1 == i)
                        res += 1;
                    else
                        res += 2 * score(s, l + 1, i - 1);
                    l = i + 1;
                }
            }
        }
        return res;
    }
};


int main() {

    cout << Solution().scoreOfParentheses("()") << endl; // 1
    cout << Solution().scoreOfParentheses("(())") << endl; // 2
    cout << Solution().scoreOfParentheses("()()") << endl; // 2
    cout << Solution().scoreOfParentheses("(()(()))") << endl; // 6

    return 0;
}

/// Source : https://leetcode.com/problems/score-of-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-06-25

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

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

        stack<int> stack;
        stack.push(0);
        for(char c: S){
            if(c == '(')
                stack.push(0);
            else{
                int v = stack.top();
                stack.pop();
                int w = stack.top();
                stack.pop();

                stack.push(w + max(2 * v, 1));
            }
        }

        return stack.top();
    }
};


int main() {

    cout << Solution().scoreOfParentheses("()") << endl; // 1
    cout << Solution().scoreOfParentheses("(())") << endl; // 2
    cout << Solution().scoreOfParentheses("()()") << endl; // 2
    cout << Solution().scoreOfParentheses("(()(()))") << endl; // 6

    return 0;
}

/// Source : https://leetcode.com/problems/score-of-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-06-25

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

/// Calculating Cores
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int scoreOfParentheses(string S) {

        int balance = 0;
        int res = 0;
        for(int i = 0 ; i < S.size() ; i ++)
            if(S[i] == '(')
                balance ++;
            else{
                balance --;
                if(S[i - 1] == '(')
                    res += (1 << balance);
            }

        return res;
    }
};


int main() {

    cout << Solution().scoreOfParentheses("()") << endl; // 1
    cout << Solution().scoreOfParentheses("(())") << endl; // 2
    cout << Solution().scoreOfParentheses("()()") << endl; // 2
    cout << Solution().scoreOfParentheses("(()(()))") << endl; // 6

    return 0;
}