18. Score of Parentheses

Given a balanced parentheses string S, compute the score of the string based on the following rule:

• () has score 1

• AB has score A + B, where A and B are balanced parentheses strings.

• (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Solution: (Stack)

class Solution
{
public:
    int scoreOfParentheses(string s)
    {

        stack<int> st;
        st.push(0);

        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] == '(')
            {
                st.push(0);
            }
            else
            {
                int v = st.top();
                st.pop();
                int c = st.top();
                st.pop();
                c += max(1, 2 * v);
                st.push(c);
            }
        }

        return st.top();
    }
};

Time Complexity: O(n)