题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

样例

输入: "1 + 1"
输出: 2

输入: " 2-1 + 2 "
输出: 3

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

算法分析

开两个栈，数字栈和操作符栈，统一原则，遇到操作符时才进行数的操作

eval()操作：将数字栈pop()出两个数字分别对应b和a，再从操作符栈pop()出操作符号，进行相应操作后将结果数字加入到数字栈中，

• 1、当遇到'('时，则直接加入到操作符栈中
• 2、当遇到数字时，则读取连续的一个完整数字，再直接加入到数字栈中
• 3、当遇到'+'，'-'时，先解决好前面操作符的操作，判断栈顶符号，一旦出现栈顶符号不是'('，进行eval()操作，前面的操作符都解决后，再把当前遇到的'+'或'-'符号加入到操作栈中
• 4、当遇到')'时，先解决好前面操作符的操作，判断栈顶符号，一旦出现栈顶符号不是'('，进行eval()操作，最后把'('符号pop()出
• 5、最后操作符栈中还存在元素（如果是只有'+'，'-'最多有一个操作符存在），因此一直进行eval()操作，最终返回结果

时间复杂度 $O(n)$

Java 代码

class Solution {
    static Stack<Integer> num = new Stack<Integer>();
    static Stack<Character> op = new Stack<Character>();
    static void eval()
    {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int r = 0;
        if(c == '+') r = a + b;
        else r = a - b;
        num.add(r);  
    }
    public int calculate(String s) {
        for(int i = 0;i < s.length();i ++)
        {
            char c = s.charAt(i);
            if(c == ' ') continue;
            if(c == '(') op.add(c);
            else if(c == ')')
            {
                while(op.peek() != '(') eval();
                op.pop();
            }
            else if(c >= '0' && c <= '9')
            {
                int x = 0,j = i;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9')
                {
                    x = x * 10 + s.charAt(j) - '0';
                    j ++;
                }
                num.add(x);
                i = j - 1;
            }
            else 
            {
                while(!op.isEmpty() && op.peek() != '(') eval();
                op.add(c);
            }

        }
        while(!op.isEmpty()) eval();
        return num.pop();
    }
}