LeetCode 224. 基本计算器_基本计算器leetcode

224. 基本计算器

【双栈】nums用来存数，ops用来存符号。

1.预处理：把所有空格去掉，在前面加个‘0'，防止出现 -1 + 2 这种样例。

2.遍历

（1）遇到 '(' 直接压入ops。

（2）遇到数字，通过 t * 10 + c - ‘0’ 直接计算出数值。

（3）遇到 ')' 把前面直到 '(' 的表达式算完，并把 '(' 丢掉。

（4）遇到 '+' 把前面直到  '(' 的表达式算完，'(' 不能丢；或者算到ops为空。

（5）遇到 '-'，这种情况比较特殊，需要看一下前面是不是 '(' ，如果是的话往nums里插入一个0，防止这种不讲武德的样例 0 - ( - ( - 3 + 4) - 4)。

class Solution {
 
    // 双栈 1:23 2:48
 
    public int calculate(String s) {
        Deque<Integer> nums = new LinkedList();
        Deque<Character> ops = new LinkedList(); 
        s = s.replace(" ", "");
        s = "0" + s;
        int n = s.length(), t = 0;
        int flag = 0;
        for (var i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                if (flag != 0) {
                    nums.push(t); t = 0;
                    flag = 0;
                }
                while (!ops.isEmpty()) {
                    char top = ops.poll();
                    if (top == '(') break;
                    else if (top == '+') {
                        nums.push(nums.poll() + nums.poll());
                    } else if (top == '-') {
                        int tmp = nums.poll();
                        nums.push(nums.poll() - tmp);
                    }
                }
                // System.out.println(nums.peek());
            } else if (c == '+' || c == '-') {
                if (s.charAt(i - 1) == '(') {
                    nums.push(0);
                    ops.push('-'); continue;
                }
                if (flag != 0) {
                    nums.push(t); t = 0;
                    flag = 0;
                }
                while (!ops.isEmpty()) {
                    char top = ops.poll();
                    if (top == '(') {
                        ops.push('('); break;
                    } else if (top == '+') {
                        nums.push(nums.poll() + nums.poll());
                    } else if (top == '-') {
                        int tmp = nums.poll();
                        nums.push(nums.poll() - tmp);
                    }
                }
                // System.out.println(nums.peek());
                ops.push(c);
            } else {
                t = t * 10 + c - '0';
                if (flag == 0) flag = 1;
                if (i == n - 1) {
                    nums.push(t); t = 0;
                }
            }
        }
        while (!ops.isEmpty()) {
            char top = ops.poll();
            if (top == '+') {
                nums.push(nums.poll() + nums.poll());
            } else if (top == '-') {
                int tmp = nums.poll();
                if (nums.isEmpty()) {
                    nums.push(-tmp);
                } else {
                    nums.push(nums.poll() - tmp);
                }
            }
        }
        return nums.poll();
    }
}