856. Score of Parentheses - Medium
문제
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.
제한사항
- S is a balanced parentheses string, containing only ( and ).
- 2 <= S.length <= 50
입출력 예
1
2
3
4
Example 1:
Input: "()"
Output: 1
1
2
3
4
Example 2:
Input: "(())"
Output: 2
1
2
3
4
Example 3:
Input: "()()"
Output: 2
1
2
3
4
Example 4:
Input: "(()(()))"
Output: 6
풀이
- Stack
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
28
29
30
31
32
33
class Solution {
public:
int scoreOfParentheses(string S) {
std::stack<int> items;
items.push(0);
// (()(()))
//
// 0 : '(', [0, 0]
// 1 : '(', [0, 0, 0]
// 2 : ')', [0, 1]
// 3 : '(', [0, 1, 0]
// 4 : '(', [0, 1, 0, 0]
// 5 : ')', [0, 1, 1]
// 6 : ')', [0, 3]
// 7 : ')', [6]
for (const char& c : S) {
if (c == ')') {
int temp1 = items.top();
items.pop();
int temp2 = items.top();
items.pop();
items.push(temp2 + std::max(2 * temp1, 1));
} else {
items.push(0);
}
}
return items.top();
}
};