題目
-
概述：給定一個正確閉合的括號字符串，按如下規(guī)則計算括號字符串的分數(shù)：
- 嵌套字符串的分數(shù)等于內(nèi)嵌字符串分數(shù)*2
- 并列的字符串分數(shù)等于各個字符串分數(shù)之和
輸入：一個正確閉合的括號字符串盏求，長度范圍為[2, 50]
輸入子項：'('或')'
輸出：該括號字符串的得分
思路
由于需要存儲括號子串的得分造锅，在之后需要的時候使用褐健，所以考慮使用棧
-
遍歷字符串乾颁，將每個字符依次入棧：
- '(' => 直接入棧
- ')' => 依次彈出棧中分數(shù)并累加直至遇到'('缓呛，將'('出棧，若分數(shù)累加和大于0靠欢，則將2 * 分數(shù)累加和入棧廊敌，否則將分數(shù)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;
}
}
