Leetcode 856: Score of Parenthese

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 0 阅读时长 ≈ 1 分钟

题目描述

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

  • () 得 1 分。
  • AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例

示例1

1
2
输入： "()"
输出： 1

示例2

1
2
输入： "(())"
输出： 2

示例3

1
2
输入： "()()"
输出： 2

示例4

1
2
输入： "(()(()))"
输出： 6

提示

  • S是平衡括号字符串，且只含有 ( 和 ) 。
  • 2 <= S.length <= 50

解题思路

这道题我是看了讨论区别人的解法后做出来的。
开始我思路也是用栈，不过我想的是用两个栈，不过没有思考出一个具体的思路。下面代码这个思路比较巧妙和简单，值得借鉴。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(-1);
            } else {
                int cur = 0;
                while (stack.peek() != -1) {
                    cur += stack.pop();
                }
                stack.pop();
                stack.push(cur == 0 ? 1 : cur * 2);
            }
        }
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }
}