# 856. 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
``````

Note:

1. `S` is a balanced parentheses string, containing only `(` and `)`.
2. `2 <= S.length <= 50`

``````class Solution {
public:
int scoreOfParentheses(string S) {
int res = 0, n = S.size();
for (int i = 0; i < n; ++i) {
if (S[i] == ')') continue;
int pos = i + 1, cnt = 1;
while (cnt != 0) {
(S[pos++] == '(') ? ++cnt : --cnt;
}
int cur = scoreOfParentheses(S.substr(i + 1, pos - i - 2));
res += max(2 * cur, 1);
i = pos - 1;
}
return res;
}
};
``````

``````class Solution {
public:
int scoreOfParentheses(string S) {
int res = 0;
stack<int> st;
for (char c : S) {
if (c == '(') {
st.push(res);
res = 0;
} else {
res = st.top() + max(res * 2, 1);
st.pop();
}
}
return res;
}
};
``````

``````class Solution {
public:
int scoreOfParentheses(string S) {
int res = 0, cnt = 0, n = S.size();
for (int i = 0; i < n; ++i) {
(S[i] == '(') ? ++cnt : --cnt;
if (S[i] == ')' && S[i - 1] == '(') res += (1 << cnt);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/856

Valid Parentheses

https://leetcode.com/problems/score-of-parentheses/

https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation