Leetcode刷题100天—856. 括号的分数（栈）—day03

太过爱你忘了你带给我的痛 2022-09-02 11:37 136阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]

给定一个平衡括号字符串 `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.com/problems/score-of-parentheses  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

思路:由于是平衡括号字符串，所以肯定全部左括号都有对应的右括号，所以如果碰到(就入栈0,如果碰到），并且栈顶的第一个元素是0，那么就加1，在加上第二个元素。如果栈顶第一个元素不是0，那么就乘2，在加上第二个元素。

public class _56_括号的分数 { 
    	public int scoreOfParentheses(String s) { 
    // 创建一个栈
    		Stack<Integer> stack = new Stack();
    		
    // 存入一个0,为了接下来弹出栈判断得分准备
    		stack.push(0);
    		int len=s.length();
    		for (int i=0;i<len;i++) { 
    			char c=s.charAt(i);
    // 按照题目要求，我们将存入的(设置为0
    			if (c=='(') { 
    				stack.push(0);
    			}else { 
    // 如果遇到),就弹出栈,且我们将当前深度的得分乘二并加到上一层的深度。
    				int top=stack.pop();//这是栈的第一层
        			int second=stack.pop();//这是栈的第二层
    // AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
    // 题目要求,如果top是(),需要乘2
        			stack.push(second+Math.max(top*2, 1));
    			}
    		}
    		return stack.pop();
        }	
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]: /images/20220829/ca05e4709e5a40949f84e6cfea33836a.png