Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2" 2-1 + 2 " = 3"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

栈法

复杂度

时间 O(N) 空间 O(N)

思路

很多人将该题转换为后缀表达式后（逆波兰表达式）求解，其实不用那么复杂。题目条件说明只有加减法和括号，由于加减法是相同顺序的，我们大可以直接把所有数顺序计算。难点在于多了括号后如何处理正负号。我们想象一下如果没有括号这题该怎们做：因为只有加减号，我们可以用一个变量sign来记录上一次的符号是加还是减，这样把每次读到的数字乘以这个sign就可以加到总的结果中了。有了括号后，整个括号内的东西可一看成一个东西，这些括号内的东西都会受到括号所在区域内的正负号影响（比如括号前面是个负号，然后括号所属的括号前面也是个负号，那该括号的符号就是正号）。但是每多一个括号，都要记录下这个括号所属的正负号，而每当一个括号结束，我们还要知道出来以后所在的括号所属的正负号。根据这个性质，我们可以使用一个栈，来记录这些括号所属的正负号。这样我们每遇到一个数，都可以根据当前符号，和所属括号的符号，计算其真实值。

注意

先用String.replace()去掉所有的空格

代码

public class Solution {    public int calculate(String s) {        // 去掉所有空格        s = s.replace(" ", "");        Stack<Integer> stk = new Stack<Integer>();        // 先压入一个1进栈，可以理解为有个大括号在最外面        stk.push(1);        int i = 0, res = 0, sign = 1;        while(i < s.length()){char c = s.charAt(i);// 遇到正号，将当前的符号变为正号if(c=='+'){    sign = 1;    i++;// 遇到负号，将当前的符号变为负号} else if(c=='-'){    sign = -1;    i++;// 遇到左括号，计算当前所属的符号，压入栈中// 计算方法是当前符号乘以当前所属括号的符号} else if(c=='('){    stk.push(sign * stk.peek());    sign = 1;    i++;// 遇到右括号，当前括号结束，出栈} else if(c==')'){    stk.pop();    i++;// 遇到数字，计算其正负号并加入总结果中} else {    int num = 0;    while(i < s.length() && Character.isDigit(s.charAt(i))){        num = num * 10 + s.charAt(i) - '0';        i++;    }    res += num * sign * stk.peek();}        }        return res;    }}