题目描述:
404收藏分享切换为英文接收动态反馈
给定一个平衡括号字符串 S
,按下述规则计算该字符串的分数:
-
()
得 1 分。 -
AB
得A + B
分,其中 A 和 B 是平衡括号字符串。 -
(A)
得2 * A
分,其中 A 是平衡括号字符串。
示例 1:
输入: "()"
输出: 1
示例 2:
输入: "(())"
输出: 2
示例 3:
输入: "()()"
输出: 2
示例 4:
输入: "(()(()))"
输出: 6
提示:
-
S
是平衡括号字符串,且只含有(
和)
。 2 <= S.length <= 50
解法:栈
根据题目描述,我们可以使用栈结构来解决。针对题目描述的几种计算分数的情况,我们可以做对应处理即可。
创建一个栈stack,并定义一个临时变量temp,在每次遍历时,使temp = 0。现将字符串转为对应的字符数组chars,遍历字符数组chars,有下面几种情况:
-
当
chars[i] == '('
,将 chars[i] 入栈。 -
当
chars[i] == ')'
,需要取出栈首元素 poll,若栈首元素不为'('的话,就一直从栈中取,直到栈为空。poll元素又有下面几种情况:-
poll == '('
,判断 temp 是否等于0:- 若等于0,说明这个是最内层的括号,
temp += 1
。 - 若不等于0,说明该括号为外层括号,
temp *= 2
。
计算完temp后,退出出栈操作。
- 若等于0,说明这个是最内层的括号,
-
poll != 0
,即为之前括号组成的分数,temp += poll,继续从栈中出栈。
将计算完的temp压栈,继续遍历。
-
经过上面一系列操作后,就会计算出最终的分数,并在栈中,然后再依次出栈,将元素进行相加得到最终结果。
代码:
class Solution {
public int scoreOfParentheses(String s) {
Deque<String> stack = new ArrayDeque<>();
char[] chars = s.toCharArray();
int temp = 0;
for (int i = 0; i < chars.length; i++) {
temp = 0;
if (chars[i] == '(') {
stack.addFirst(String.valueOf(chars[i]));
} else if (chars[i] == ')') {
while (!stack.isEmpty()) {
String poll = stack.pollFirst();
if ("(".equals(poll)) {
if (temp != 0) {
temp *= 2;
} else {
temp += 1;
}
break;
} else {
temp += Integer.valueOf(poll);
}
}
stack.addFirst(String.valueOf(temp));
}
}
int result = 0;
while (!stack.isEmpty()) {
result += Integer.valueOf(stack.poll());
}
return result;
}
}
网友评论