LeetCode——括号的分数

淩亂°似流年 2022-02-21 15:09 216阅读 0赞

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

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

**题目**：

**示例 1：**

输入： "()"
    输出： 1

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**提示：**

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

`思路：题目可能刚开始看比较难懂，下面举例子就明白了，"()"="0", `"()()"="1 1", "(())" = "( 1 )",分数为1\*2=2，"(()(()))"="( 1 (1)  )" ="( 1 2 )"="(3)"=6,总的来说就是括号里面有括号，则分数要加倍。理解题目，对于括号匹配的问题，肯定要用栈，但是栈不仅要存放左括号，还要存放分数，毕竟不能一下子计算好分数，比如“（1  1  2）”，肯定要依次将1， 1， 2压入栈，然后最后一个又括号出现时，依次相加1  1  2得到（4），所以最后得分为2\*4=8。那么如何让栈存储int和char类型呢？用ascii码的话，那可能存在超过9的数，所以我们将括号用整数表示，这里分数肯定是正数，所以用“-1”表示左括号。

**代码**：

char[] chars = S.toCharArray();
            //栈
            Stack<Integer> stack = new Stack<>();
            //遍历String
            for(char s : chars){
                //如果是左括号则压栈
                if(s == '('){
                    stack.push(-1);
                }else{//如果遇到右括号，那分情况
                    //出栈
                    int temp = 0;
                    //首先出栈，直到遇到左括号，夹在括号之间的东西要么为空，要么就是分数
                    while(!stack.empty() && stack.peek()!=-1){
                        //对应“AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。”
                        temp += stack.pop();
                    }
                    //把左括号出栈
                    stack.pop();
                    //如果两个括号没有内容，则对应() 得 1 分。
                    if(temp == 0){
                        stack.push(1);
                    }else{
                        //如果有内容,对应(A) 得 2 * A 分，其中 A 是平衡括号字符串。
                        stack.push(temp*2);
                    }
                }
            }
            //出现"()()"类似
            if(stack.size()>1){
                int result = 0;
                while(!stack.empty() ){
                    result += stack.pop();
                }
                return result;
            }
            //出现"(()(()))"情况
            return stack.peek();