LeetCode856括号的分数

给定一个平衡括号字符串S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得A + B分，其中 A 和 B 是平衡括号字符串。
(A) 得2 * A分，其中 A 是平衡括号字符串。

示例 1：

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

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

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

输入： “(()(()))”
输出： 6

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/score-of-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

图解

代码

public static int scoreOfParentheses(String S) {
        int length = S.length();
        int sum = 0;
        int n = 0;
        for (int i = 0; i < length; i++) {
            if (S.charAt(i) == '(') {
                if (n == 0) {
                    n = 1;
                } else {
                    n = n << 1;
                }
            } else if (S.charAt(i) == ')') {
                if (S.charAt(i - 1) == '(') {
                    sum += n;
                }
                n = n >> 1;

            }
        }
        return sum;
    }

    public static int scoreOfParentheses2(String S) {
        Stack<Integer> stack = new Stack<>();
        int length = S.length();
        for (int i = 0; i < length; i++) {
            if (S.charAt(i) == '(') {
                stack.push(-1);
            } else {
                int temp = 0;
                while (!stack.isEmpty()) {
                    Integer pop = stack.pop();
                    if (pop != -1) {
                        temp += pop;
                        continue;
                    } else {
                        if (temp == 0)
                            stack.push(1);
                        else
                            stack.push(temp * 2);
                        break;
                    }

                }
            }
        }
        int res = 0;
        while (!stack.empty()) {
            res += stack.pop();
        }
        return res;
    }
    /*
	时间复杂度：O(n)
	空间复杂度：O(n)
    */	
    public static  int scoreOfParentheses3(String s) {
        Deque<Integer> st = new ArrayDeque<Integer>();
        st.push(0);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(0);
            } else {
                int v = st.pop();
                int top = st.pop() + Math.max(2 * v, 1);
                st.push(top);
            }
        }
        return st.peek();
    }

    public static void main(String[] args) {
        String s = "((((((())))()())))";
      /*  System.out.println(scoreOfParentheses(s));

        System.out.println(scoreOfParentheses2(s));*/

        System.out.println(scoreOfParentheses3(s));
    }

大佬实现：耗时0ms

解题思路

根据题目描述，我们需要对字符串s进行解析，并利用堆栈的特点帮助我们进行计算。以下图为例，s = “(()(()))”，遍历前两个字符都是‘(’，所以我们将‘(’执行入栈操作。遍历到的第三个字符是‘)’，我们要将栈顶元素弹出，发现可以匹配成一个括号，由于题目描述，一个“()”等于1，所以，我们将字符‘1’入栈。此时堆栈中的元素为[‘(‘, ‘1’]。具体操作如下图所示

我们在继续遍历，由于第4和第5个字符都是‘(’，所以我们直接入栈即可。当遍历到第6个字符的时候，由于是‘)’，所以我们再次执行将栈顶元素踢出堆栈的操作，由于题目描述，一个“()”等于1，所以，我们将字符‘1’入栈。此时堆栈中的元素为[‘(‘, ‘1’,’(‘, ‘1’]。具体操作如下图所示：

当遍历到第7个字符的时候，由于是‘)’，所以我们再次执行将栈顶元素踢出堆栈的操作，由于出栈的字符不是‘(’而是‘1’，所以我们继续踢出栈顶元素，此时出栈字符为‘(’，满足匹配题目中描述的(A) 得2 * A分的情况，所以计算出来的结果为 2*1 等于2，我们将字符‘2’入栈。此时堆栈中的元素为[‘(‘, ‘1’,’2’]
我们在继续向后遍历，由于第8个字符是‘)’，我们执行栈顶元素出栈操作，由于栈顶和次栈顶元素分别是‘2’和‘1’，都不是‘(’,所以继续执行栈顶出栈操作。然后这次出栈的元素是‘(’，可以匹配成一个括号，同时也满足了题目中描述的 AB 得A + B分 和 (A) 得2 * A分这两种情况。所以，计算结果为：2 * (1 + 2) 等于 6，在将6入栈。此时堆栈中的元素为[‘6’]。那么遍历s字符串完毕之后，我们将堆栈中所有元素值相加就是最终结果。具体操作，如下图所示：

代码

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Character> deque = new ArrayDeque();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') deque.addLast('(');
            else {
                char c = deque.removeLast();
                if (c == '(') {
                    deque.addLast('1');
                } else {
                    int sum = c - '0';
                    while ((c = deque.removeLast()) != '(')  sum += c - '0';
                    deque.addLast((char) ((sum << 1) + '0'));
                }
            }
        }
        int result = 0;
        while (!deque.isEmpty()) result += deque.removeLast() - '0';
        return result;
    }
}

作者：muse-77
链接：https://leetcode.cn/problems/score-of-parentheses/solution/zhua-wa-mou-si-by-muse-77-hy72/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。