856. Score of Parentheses

Posted on Edited on In

856. Score of Parentheses

Description

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is 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:

1
2
Input: s = "()"
Output: 1

Example 2:

1
2
Input: s = "(())"
Output: 2

Example 3:

1
2
Input: s = "()()"
Output: 2

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<string> stk;
        for (char& c : s) {
            if (c == '(') {
                stk.push({c});
            } else {
                int sum = 0;
                while (stk.top() != "(") {
                    sum += stoi(stk.top());
                    stk.pop();
                }
                // pop out the "("
                stk.pop();
                if (sum == 0) sum = 1; else sum *= 2;
                stk.push(to_string(sum));
            }
        }
        int res = 0;
        while (!stk.empty()) {
            res += stoi(stk.top());
            stk.pop();
        }
        return res;
    }
};