# 856. Score of Parentheses 括号的分数

@TOC

## # 题目描述

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

## # 解题方法

### # 栈

Python代码如下：

class Solution(object):
def scoreOfParentheses(self, S):
"""
:type S: str
:rtype: int
"""
stack = []
score = 0
for c in S:
if c == '(':
stack.append("(")
else:
tc = stack[-1]
if tc == '(':
stack.pop()
stack.append(1)
else:
num = 0
while stack[-1] != '(':
num += stack.pop()
stack.pop()
stack.append(num * 2)
return sum(stack)

For example, when counting (()(())), our stack will look like this:

[0, 0] after parsing ( [0, 0, 0] after ( [0, 1] after ) [0, 1, 0] after ( [0, 1, 0, 0] after ( [0, 1, 1] after ) [0, 3] after ) [6] after )

python代码如下：

class Solution(object):
def scoreOfParentheses(self, S):
"""
:type S: str
:rtype: int
"""
stack = [0]
score = 0
for c in S:
if c == '(':
stack.append(0)
else:
v = stack.pop()
stack[-1] += max(v * 2, 1)
return sum(stack)

### # 递归

C++代码如下：

class Solution {
public:
int scoreOfParentheses(string S) {
return helper(S, 0, S.size() - 1);
}
private:
int helper(string& s, int l, int r) {//[l, r]
if (r - l == 1) return 1;
int count = 0;
for (int i = l; i < r; i++) {
if (s[i] == '(')
count++;
else
count--;
if (count == 0) {
return helper(s, l, i) + helper(s, i + 1, r);
}
}
return helper(s, l + 1, r - 1) * 2;
}
};

### # 计数

C++代码如下：

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

## # 日期

2018 年 12 月 11 日 —— 双十一已经过去一个月了，真快啊。。