括号的分数｜Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看<活动链接>

一、题目描述

括号的分数

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

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

示例 1：

输入： "()"
输出： 1
复制代码

示例 2：

输入： "(())"
输出： 2
复制代码

示例 3：

输入： "()()"
输出： 2
复制代码

示例 4：

输入： "(()(()))"
输出： 6
复制代码

提示：

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

二、思路分析

看到括号类的题目首先想到的就是用栈来解决。

我们可以创建一个栈，遍历给定的字符串，把每个字符都压入栈中。虽然我们是想把括号依次放入栈中，但也不能思想固化，栈中也可以放入其它元素(比如分数)。

如果是(就压入栈中。

如果是)就遍历计算与栈顶元素的分数。

下面以输入(()(()))为例：

第一个括号

第二个括号

第三个括号

第四个括号

第五个括号

第六个括号

第七个括号

第八个括号

在整个过程中，我们只需要遍历一次字符串，所以时间复杂度是O(n)，执行用时1ms。

三、AC代码

public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        for (Character c : S.toCharArray()) {
            if (c == '(') {
                stack.push(-1);
            } else {
                int temp = 0;
                while (stack.peek() != -1) {
                    temp += stack.pop();
                }
                stack.pop();
                stack.push(temp == 0 ? 1 : 2 * temp);
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
复制代码