博客

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

输入： "()"
输出： 1

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

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

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

3. 提示
   
   S 是平衡括号字符串，且只含有 ( 和 ) 。
   
   2 <= S.length <= 50
4. 代码实现
   
   a.数据结构：操作数栈，运算符栈；
   
   b.遍历平衡括号字符串，因其只有(和)，则只有4种情形，依次为()、((、)(、((。
   
   ()：将1压入操作数栈；
   
   ((：将*压入运算符栈；
   
   )(：将+压入运算符栈；
   
   ((：执行运算，分两种情形：若栈顶元素为乘法运算符，则取操作数栈栈顶元素直接进行运算；若栈顶元素不为乘法运算符，则需要先执行上方的所有+运算，再执行乘法运算。
   
   c.执行运算符栈所有运算；
   
   d.操作数栈栈顶运算即为所求。

import java.util.Stack;

class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> number = new Stack<>();
        Stack<Character> operation = new Stack<>();
        for(int i=0;i<S.length()-1;i++){
            char current = S.charAt(i);
            char next = S.charAt(i+1);
            if(current=='('&&next==')'){
                number.push(1);
            }
            if(current=='('&&next=='('){
                operation.push('*');
            }
            if(current==')'&&next=='('){
                operation.push('+');
            }
            if(current==')'&&next==')'){
                char op =operation.pop();
                //执行*前，需要先执行前面所有的+运算
                while (op!='*'){
                    int num1 = number.pop();
                    int num2 = number.pop();
                    number.push(num1+num2);
                    op = operation.pop();
                }
                number.push(number.pop()*2);
            }
        }
        while (!operation.empty()){
            char op = operation.pop();
            //前面遍历只到S.length()-1，所以仍然可能存在栈顶元素为*的情况
            if(op=='*'){
                int numTop = number.pop();
                numTop = numTop*2;
                number.push(numTop);
            }
            if(op=='+'){
                int num1 = number.pop();
                int num2 = number.pop();
                number.push(num1+num2);
            }
        }
        return  number.peek();
    }
}

5.总结

程序即人思维的体现。看到这个题目你会怎么样计算，程序也就是反映你的计算过程而已。