227 Basic Calculator II

227. Basic Calculator II

1. Question

Implement a basic calculator to evaluate a simple expression string.

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

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.

• Do not use theevalbuilt-in library function.

2. Implementation

(1) Stack

思路: 用两个stack，一个是nums,存放数字，一个是operators, 存放运算符号，注意计算时，如果operators顶部的运算符的计算优先级高于当前的运算符，需要先将顶部的运算符出栈，然后计算结果

class Solution {
    public int calculate(String s) {
        Stack<Character> operators = new Stack();
        Stack<Integer> nums = new Stack();

        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                int num = c - '0';

                while ((i + 1) < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    num = 10 * num + s.charAt(i + 1) - '0';
                    ++i;
                }
                nums.push(num);
            }
            else if (isOperator(c)) {
                while (!operators.isEmpty() && hasPrecedence(c, operators.peek())) {
                    nums.push(calculate(operators.pop(), nums.pop(), nums.pop()));
                }
                operators.push(c);
            }
            ++i;
        }

        while (!operators.isEmpty()) {
            nums.push(calculate(operators.pop(), nums.pop(), nums.pop()));
        }
        return nums.isEmpty() ? 0 : nums.pop();
    }

    public boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    public int calculate(char operator, int num1, int num2) {
        int res = 0;
        switch(operator) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num2 * num1;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }

    public boolean hasPrecedence(char op1, char op2) {
        if ((op2 == '-' || op2 == '+') && (op1 == '*' || op1 == '/')) {
            return false;
        }
        return true;
    }
}

3. Time & Space Complexity

(1) Stack: 时间复杂度O(n), 空间复杂度O(n)