227. 基本计算器 II

227. 基本计算器 II

class Solution {
    public int calculate(String s) {
        // 预处理
        s = s.replace(" ", "");
        s = s.replace("(-", "(0-");
        Deque<Integer> num = new LinkedList<>();
        num.push(0);
        Deque<Character> ch = new LinkedList<>();
        int index = 0;
        while (index < s.length()) {
            char cur = s.charAt(index);
            if (cur == '(') {
                ch.push(cur);
            } else if (cur == ')') {
                // 计算直到遇到左边的'('
                while (ch.peek() != '(') {
                    cal(num, ch);
                }
                // 弹出左边的'('
                ch.pop();
            } else if (cur == '+' || cur == '-' || cur == '*' || cur =='/') {
                while (!ch.isEmpty() && ch.peek() != '(') {
                    // 将优先级高的全部进行计算
                    char pre = ch.peek();
                    if (compare(pre, cur)) {
                        // pre的优先级高
                        cal(num, ch);
                    } else {
                        break;
                    }
                }
                ch.push(cur);
            } else {
                int curNum = 0;
                while (index < s.length() && Character.isDigit(s.charAt(index))) {
                    curNum = 10 * curNum + (s.charAt(index) - '0');
                    ++index;
                }
                num.push(curNum);
                continue;
            }
            ++index;
        } 
        while (!ch.isEmpty()) {
            cal(num, ch);
        }
        return num.peek();
    } 
    private boolean compare(char pre, char opt) {
        if (pre == '*' || pre == '/')
            return true;
        if ((pre == '+' || pre == '-') && (opt == '-' || opt == '+'))
            return true;
        return false;
    }
    private void cal(Deque<Integer> num, Deque<Character> ch) {
        int num1 = num.pop();
        int num2 = num.pop();
        if (ch.peek() == '+') {
            num.push(num1 + num2);
        } else if (ch.peek() == '*') {
            num.push(num1 * num2);
        } else if (ch.peek() == '/') {
            num.push(num2 / num1);
        }else {
            num.push(num2 - num1);
        }
        ch.pop();
    }
}