博客

856. 括号的分数

难度:中等

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

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

示例 1：

输入： “()”

输出： 1

示例 2：

输入： “(())”

输出： 2

示例 3：

输入： “()()”

输出： 2

示例 4：

输入： “(()(()))” 即 ( 1 (1) ) -> ( 1 + 2) -> 6

输出： 6

提示：

S 是平衡括号字符串，且只含有 ( 和 ) 。

2 <= S.length <= 50

伪代码

1. 一般遇到括号匹配问题，都会先想到栈的使用，所以先定义一个栈
2. 遍历平衡括号字符串 S，如果遇到 ‘(’ 则入栈
3. 遇到右括号，则判断栈顶是否是 ‘(’，如果是则得 1 分
4. 如果不是，则说明是 ( A ) 或 ( A + B + C)… 的情况，则弹出所有数字，直到弹出第一个 ‘(‘为止，将 ABC相加乘2，再入栈
5. 如果遍历结束了，也就是没有括号了，那么就栈内只剩下纯数字，相加求和即可
   
   

    public static int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        char c;
        for (int i = 0; i < S.length(); i++) {
            c = S.charAt(i);
            if(c == '('){
                stack.push(0); //用0来模拟'('
            }else {
                if(stack.peek() == 0){
                    //先弹出 '(',得一分入栈
                    stack.pop();
                    stack.push(1);
                }else {
                    int Scores = 0;
                    while(stack.peek() != 0){
                        Scores += stack.peek();
                        stack.pop();
                    }
                    stack.pop(); //最后弹出 '('
                    stack.push(Scores * 2);
                }
            }

        }
        int AllScore = 0;
        while (!stack.isEmpty()){
            AllScore += stack.pop();
        }
        return AllScore;
    }