Calculator

224. Basic Calculator

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

My Solutions:

stack 储存的是括号前的符号。括号内的每一个数字加入result时，都要peek一下stack里的符号，相乘之后，再加入result。e.g. -(3 - 6) ， result -3+6

class Solution {
    public int calculate(String s) {
        s = s.replace(" ", ""); //去掉空格
        int len = s.length(), sign = 1, res = 0, i = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(1); //一开始设置为正号
        while (i < len) {
            char c = s.charAt(i);
            
            if (c == '+') {
                sign = 1;
                i++;
            } else if (c == '-') {
                sign = -1; 
                i++;
            } else if (c == '(') {
                stack.push(sign * stack.peek()); //stack里有（1, -1）
                sign = 1;
                i++;
            } else if (c == ')') {
                stack.pop();
                i++;
            } else {
                int num = 0;
                //判断是否超出边界或者不是digit(不再是一个数字)
                while (i < len && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                res += num * sign * stack.peek();
            }
        }
        return res;
        
    }
}

227. Basic Calculator II

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces. The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

My Solutions:

用一个sign的char储存之前的符号，用数字num储存数字，用stack储存所有可以相加的项。当遇见一个新符号，把num的数字做好相应的变化，压栈到stack里。最后把stack里的所有元素相加起来。

e.g., 3 * 2 - 5

• 碰到3： stack：空； sign = +； num = 3

• 碰到*： stack： 3； sign = *； num = 0

• 碰到2： num = 2；

• 碰到-： (stack pop出3，再push进6)stack: 6；sign = -; num = 0

• 碰到5：num = 5；

  • 进入下一个if block，因为5是最后一个数字

  • stack：6， -5

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int num = 0; //num放在外面
        char sign = '+'; //sign 储存的是数字之前的符号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            // 如果当前字符是数字
            if (Character.isDigit(c)) num = num * 10 + c - '0';
            
            // 如果当前字符是+-*/, 先处理之前的数字
            // 注意这里并不是else if，因为必须要处理最后一个数字
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                if (sign == '+') stack.push(num); //stack只储存最后可以相加的项
                else if (sign == '-') stack.push(-num);  //把数字变为负号，stack只储存最后可以相加的项
                else if (sign == '*') stack.push(stack.pop() * num);  //把之前的数字pop出来，做乘运算，stack 只储存最后可以相加的项
                else if (sign == '/') stack.push(stack.pop() / num);   //把之前的数字pop出来，做除运算，stack 只储存最后可以相加的项
                // 再更新新符号，以及重置num
                sign = c; //符号更新成现在的char
                num = 0;
            }
        }
        
        //相加所有数字
        int res = 0; 
        for (int i: stack) res += i;
        return res;
    }
}

也可以优化一下，不用stack，直接用一个数字储存之前的数字

class Solution {
    public int calculate(String s) {
        int num = 0, res = 0, last = 0;
        char sign = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                if (sign == '+') {
                    res += last;
                    last = num;
                }
                else if (sign == '-') {
                    res += last;
                    last = -num;
                }
                else if (sign == '*') {
                    last = last * num;
                }
                else if (sign == '/') {
                    last = last / num;
                }
                sign = c;
                num = 0;
            }
        }
        res += last;
        return res;
    }
}

Basic Calculator III

The expression string contains only non-negative integers, +, -, *, / operators, open ( and closing parentheses ) , and empty spaces. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647]

My Solutions:

和上一题的区别是既有加减乘除，又有括号。

用两个栈，一个存放数字，一个存放操作符。用evaluate方法解决计算问题，例如evaluate(op, num1, num2)，就表示num2 op(+-*/) num1。用isPrior判断哪个操作符优先级更高。

大概分以下情况：

1. 走到一个数字，看下一位是否也是数字，如果是将他们拼接起来，压到栈里去

2. 走到左括号，直接压入到操作符栈里去

3. 走到右括号，从数字栈取2个数字，从操作符栈取1个操作符，进行运算，将结果压回到数字栈里去，重复这样的操作，直到操作符栈顶元素是左括号，这样说明这个括号内的就计算完成了。

4. 走到操作符（+-*/)，查看操作符栈顶元素优先级是否低于当前操作符优先级，如果是的话，则跳过，不是的话，则进行evaluate运算。举个例子：当前操作符是"*"，栈顶是"+"，那么就是val1+val2*nextVal，这里肯定不能计算val1+val2，因为当前操作符的优先级更高。但是如果当前操作符是"+"，而操作符栈的栈顶元素是"*"，就可以经进行val1+val2的运算了，计算完的结果，放回数字栈里。（这里nextVal还有被遍历到）

public class Solution {

    private int evaluate(char op, int b, int a) {
        switch(op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
        }
        return 0;
    }

    private boolean isBeforeHigherPriority(char curr, char before) {
        if (before == '(') return false;
        if ((curr == '*' || curr == '/') && (before == '+' || before == '-')) return false;
        return true;
    }

    public int calculate(String s) {
        // 初始化两个栈：数字栈，操作符栈
        Stack<Integer> stack = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int num = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果是空格，直接跳过
            if (c == ' ') continue;
            // 如果是数字，那么继续查找下一个位置，直到拼接完整个数
            if (Character.isDigit(c)) {
                num = c - '0';
                while (i < s.length() - 1 && Character.isDigit(s.charAt(i + 1))) {
                    num = num * 10 + (s.charAt(i + 1) - '0');
                    i++;
                }
                // 拼接完之后，压回数字栈里去
                stack.push(num);
                num = 0;
            // 如果是左括号，直接压到操作符栈里去
            } else if (c == '(') {
                ops.push(c);
            // 如果是右括号，则用evaluate计算，并将结果放回数字栈
            // 直到操作符栈顶是左括号位置
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    int val = evaluate(ops.pop(), stack.pop(), stack.pop());
                    stack.push(val);
                }
                ops.pop();
            // 如果是操作符，且当前操作符优先级低于操作符栈顶的操作符优先级
            // 则用evaluate计算一下结果，并将结果压回数字栈里
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!ops.isEmpty() && isBeforeHigherPriority(c, ops.peek())) {
                    int val = evaluate(ops.pop(), stack.pop(), stack.pop());
                    stack.push(val);
                }
                ops.push(c);
            }
        }
        // 如果操作符栈不空，那么继续evaluate运算，并将结果放回数字栈
        while(!ops.isEmpty()) {
            int val = evaluate(ops.pop(), stack.pop(), stack.pop());
            stack.push(val);
        }
        // 返回数字栈中的元素
        return stack.pop();
    }
}