LeetCode_栈_中等_856.括号的分数

拼搏现实的明天。 2023-10-07 20:11 14阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**  
输入： “()”  
输出： 1

**示例 2：**  
输入： “(())”  
输出： 2

**示例 3：**  
输入： “()()”  
输出： 2

**示例 4：**  
输入： “(()(()))”  
输出： 6

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/score-of-parentheses

## 2.思路 ##

（1）栈  
思路参考[该 LeetCode 用户题解][LeetCode]。

① 定义栈 stack，初始化将 0 放入栈中；

② 遍历字符串 s，如果遇到 ‘(’，则存入数值 0；如果遇到 ‘)’，则取出栈顶元素 cur，并根据栈顶元素数值情况进行讨论：  
1）如果 cur == 0，即当前的 ‘)’ 的前一个元素是 ‘(’，根据 `() 得 1 分`的规则可知，本次得分为 1；  
2）如果 cur != 0，即当前 ‘)’ 与其匹配的 ‘(’ 中间相隔了其它括号，根据 `(A) 的得 2 * A 分`的规则，此时可知得分为 2 \* cur；  
将上面的两种情况结合，可知本次得分为 Math.max(1, cur \* 2)

③ 由于每次遇到 ‘)’ 时，都将最近一次操作计算出来。而前面无论是 ‘)’ 还是 ‘(’，我们都可以使用 `AB 得 A + B 分`的规则，将其新得分累加到栈顶元素上，其中 ‘(’ 仍采用累加规则，则利用我们将 ‘(’ 定义为 0 的设定。

④ 遍历结束后，栈顶元素即为括号的分数，此时将其返回即可。

相关题目：  
[LeetCode\_栈\_简单\_20.有效的括号][LeetCode_20.]  
[LeetCode\_递归\_回溯算法\_中等\_22.括号生成][LeetCode_22.]  
[LeetCode\_栈\_动态规划\_困难\_32.最长有效括号][LeetCode_32.]  
[LeetCode\_回溯\_困难\_301. 删除无效的括号][LeetCode_301.]  
[LeetCode\_栈\_中等\_921.使括号有效的最少添加][LeetCode_921.]

## 3.代码实现（Java） ##

//思路1————栈
    class Solution {
        
        public int scoreOfParentheses(String s) {
        
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            for (char c : s.toCharArray()) {
        
                if (c == '(') {
        
                    stack.push(0);
                } else {
        
                    int cur = stack.pop();
                    stack.push(stack.pop() + Math.max(1, cur * 2));
                }
            }
            return stack.peek();
        }
    }

[LeetCode]: https://leetcode.cn/problems/score-of-parentheses/solution/by-ac_oier-0mhz/
[LeetCode_20.]: https://blog.csdn.net/weixin_43004044/article/details/118957884
[LeetCode_22.]: https://blog.csdn.net/weixin_43004044/article/details/123493807
[LeetCode_32.]: https://blog.csdn.net/weixin_43004044/article/details/122975965
[LeetCode_301.]: https://blog.csdn.net/weixin_43004044/article/details/125029726
[LeetCode_921.]: https://blog.csdn.net/weixin_43004044/article/details/127160064