[亚麻高频题] Leetcode 224. Basic Calculator(计算器)

题目描述 & 链接

​​​​​​Leetcode 224​​​​​​: 给点一个String表达式 "1  + 2 - 3"返回最后的计算结果，运算符有+/-, () 数值存在负数。

题目思路

基本表达式计算类问题的通用思路，就是采用双栈，一个栈保存运算符号和括号，一个栈来保存数字。需要注意的是符号栈根据优先级维护一个单调递增栈，首先定义运算符的优先级："(" 是1优先级； "+","-"是2优先级。基本思路遍历每一个字符，当遇到"(" 进符号栈，当找到")"时开始进行数字运算，直到符号栈栈顶是"("为止；如果遇到数字，直接加入数字栈；当遇到"+/-"时，先查看符号栈顶元素优先级是不是更大或者相同，如果是触发运算直到栈顶为空或者栈顶优先级更小。

基本思路

1. 初始化两个栈，这里为了防止一开始第一个数为负数，可以初始化数字栈时加入0
2. 遍历每一个表达式中字符
   1. 遇到"(" -> 直接加入符号栈
   2. 遇到")" -> 触发计算，pop之前符号栈顶和数字栈顶，直到符号栈为空或者栈顶为"("。
   3. 遇到数字 ->加入数字栈
   4. 遇到"("外其他符号 -> 维护栈顶，如果栈顶优先级更大或相同，触发计算
3. 返回结果

代码如下：

class Solution {
    public int calculate(String str) {
        String s = str.replace(" ", "");
        HashMap<Character, Integer> prio = new HashMap<>();

        // 定义运算符优先级
        prio.put('(', 1);
        prio.put('+', 2);
        prio.put('-', 2);

        Deque<Character> ops = new ArrayDeque();
        Deque<Integer> stk = new ArrayDeque();

        int i = 0;
        stk.addLast(0); // 避免第一位是负数的情况

        while(i<s.length()) {
            char ch = s.charAt(i);
            // 是(直接入栈
            if(ch=='(') {
                ops.addLast(ch);
                i++;

            } else if(Character.isDigit(ch)) {
                // 是数字入数字栈
                String tmp = "";
                while(i<s.length() && Character.isDigit(s.charAt(i))) {
                    tmp+=s.charAt(i);
                    i++;
                }
                stk.addLast(Integer.parseInt(tmp));
            } else if(ch==')') {
                // 是 ")" 开始触发计算直到找到左括号
                while(!ops.isEmpty() && ops.peekLast()!='(') {
                    cal(ops, stk);
                }
                ops.pollLast();
                i++;
            } else {
                if (i > 0 && s.charAt(i-1) == '(') {
                    stk.addLast(0);
                }
                // 如果同级或者优先级比栈顶小触发计算
                while(!ops.isEmpty() && prio.get(ch)<=prio.get(ops.peekLast()) && ops.peekLast()!='(') {
                    cal(ops, stk);
                }
                ops.addLast(ch);
                i++;
            }
        }
        while(!ops.isEmpty()) {
            cal(ops, stk);
        }
        return stk.peekLast();
    }

    private void cal(Deque<Character> ops, Deque<Integer> stk) {
        if(ops.isEmpty() || stk.size()<2) return;
        char op = ops.pollLast();
        int r = stk.pollLast();
        int l = stk.pollLast();
        int res = 0;

        if(op=='+') res = l+r;
        if(op=='-') res = l-r;

        stk.addLast(res);
    }
}

时间复杂度：；空间复杂度：。