题目
-
概述：给定一个正确闭合的括号字符串，按如下规则计算括号字符串的分数：
- 嵌套字符串的分数等于内嵌字符串分数*2
- 并列的字符串分数等于各个字符串分数之和
输入：一个正确闭合的括号字符串，长度范围为[2, 50]
输入子项：'('或')'
输出：该括号字符串的得分
思路
由于需要存储括号子串的得分，在之后需要的时候使用，所以考虑使用栈
-
遍历字符串，将每个字符依次入栈：
- '(' => 直接入栈
- ')' => 依次弹出栈中分数并累加直至遇到'('，将'('出栈，若分数累加和大于0，则将2 * 分数累加和入栈，否则将分数1入栈
该括号字符串的最终得分为栈中元素累加和
代码
class Solution {
public int scoreOfParentheses(String S) {
LinkedList<Integer> stack = new LinkedList<>();
int sum, top;
for (char c : S.toCharArray()) {
switch (c) {
case '(':
stack.push(-1);
break;
case ')':
top = stack.pop();
sum = 0;
while (top != -1) {
sum += top;
top = stack.pop();
}
if (sum > 0) {
stack.push(2 * sum);
} else {
stack.push(1);
}
break;
}
}
sum = 0;
while (!stack.isEmpty()) {
sum += stack.pop();
}
return sum;
}
}
