[数据结构与算法]leetcode 224. Basic Calculator | 224. 基本计算器（中缀表达式求值）

题目

https://leetcode.com/problems/basic-calculator/

题解

中缀表达式求值，之前学数据结构的笔记：

class Solution {
    public int calculate(String s) {
        if (s.trim().startsWith("-")) s = "0" + s;
        
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        int cur = 0;
        boolean pending = false;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                // pass
            } else if (c == '(') {
                if (pending) {
                    numStack.push(cur);
                    cur = 0;
                    pending = false;
                }
                opStack.push(c);
            } else if (c == ')') {
                if (pending) {
                    numStack.push(cur);
                    cur = 0;
                    pending = false;
                }
                char op = opStack.pop();
                while (op != '(') {
                    int b = numStack.pop();
                    int a = numStack.pop();
                    numStack.push(cal(a, b, op));
                    op = opStack.pop();
                }
            } else if (c >= '0' && c <= '9') {
                cur *= 10;
                cur += c - '0';
                pending = true;
            } else {
                if (pending) {
                    numStack.push(cur);
                    cur = 0;
                    pending = false;
                }
                if (!opStack.isEmpty() && opStack.peek() != '(') {
                    char op = opStack.pop();
                    int b = numStack.pop();
                    int a = numStack.pop();
                    numStack.push(cal(a, b, op));
                }
                opStack.push(c);
            }
        }
        if (pending) {
            numStack.push(cur);
        }
        if (!opStack.isEmpty()) {
            char op = opStack.pop();
            int b = numStack.pop();
            int a = numStack.pop();
            numStack.push(cal(a, b, op));
        }
        return numStack.pop();
    }

    public int cal(int a, int b, char op) {
        return op == '+' ? a + b : a - b;
    }
}