23-05-26 刷题-【中缀表达式求值的模板】

发布时间 2023-05-26 19:11:16作者: 编程爱好者-java

basic calculator系列题目:(可以作为模板题,记住)

224. 基本计算器 - 力扣(LeetCode) [hard]

想法:

  • 中缀表达式求值。数据结构中栈的应用

    • 中缀转后缀。后缀能去掉括号。a + (b + c)*d ==》 abc+d*+
    • 后缀表达式求值: abc+d*+
    • 要考虑表达式的优先级,怎么处理括号。 括号的优先级,不知道怎么处理。
    • 处理特殊情况: 1 + (-2)这种情况
  • 总结1:这题处理特例1-( -2)太恶心了。

  • 总结2:对于运算符和符号,分两类,运算符有优先级,左右括号特殊处理一下。

  • 代码技巧1:evaluate函数,直接传入两个stack,然后计算一次。不加返回值。这种写法比传入numStack和opCode,然后返回计算结果好。因为后者还需要在调用处,把结果push到栈里。

  • 代码技巧2:parse 数字时,使用循环直接解析,而不要重用外层的循环。这样更清晰一点。

class Solution {
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>(); // 存操作数的栈
        Deque<Character> opStack = new ArrayDeque<>(); // 存运算符的栈
        // 原则:能算就算
        // 将运算符+-*/ 和 ()分成两类。运算符定义优先级,括号特殊处理
        int prev = -1;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') continue;
            else if (Character.isDigit(ch)) {
                // parse the number use a loop
                int j = i, num = 0;
                for (; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
                    num = num * 10 + (s.charAt(j) - '0');
                }
                numStack.push(num);
                i = j - 1;
            } else { // operation code
                if (ch == '(') { //压栈
                    opStack.push(ch);
                } else if (ch == ')') {
                    while (opStack.peek() != '(') {
                        // evaluate the stack
                        evaluate(numStack, opStack);
                    }
                    opStack.pop();
                } else {
                    if (prev == -1 || s.charAt(prev) == '+' || s.charAt(prev) == '-' || s.charAt(prev) == '(') {
                        numStack.push(0);
                    }
                    // 因为只有+-,优先级一样,不需要比较优先级了
                    while (!opStack.isEmpty() && opStack.peek() != '(') {
                        evaluate(numStack, opStack);
                    }
                    opStack.push(ch);
                }
            }
            prev = i;
        }       
        while (!opStack.isEmpty()) {
            evaluate(numStack, opStack);
        }
        return numStack.pop();
    }

    void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
        int b = numStack.pop();
        int a = 0;
        if (!numStack.isEmpty())
            a = numStack.pop();
        char opCode = opStack.pop();
        if (opCode == '+') {
            numStack.push(a + b);
        } else if (opCode == '-') {
            numStack.push(a - b);
        }
    }
}

复杂度分析:

  • 时间:O(n), 字符串遍历一遍,最多有n个元素入栈和出栈, 空间O(n)

官方答案的解法:

227. 基本计算器 II - 力扣(LeetCode) 【mid】

直接套用上面的模板,修改下优先级即可。这题没有括号,也没有单目运算符,所以是mid级别,不是很难。

class Solution {
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();

        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') continue;
            if (Character.isDigit(ch)) {
                int num = 0, j = i;
                for(; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
                    num = num * 10 + (s.charAt(j) - '0');
                }
                numStack.push(num);
                i = j - 1;
            } else {
                while (!opStack.isEmpty() && getPriority(ch) <= getPriority(opStack.peek())) {
                    evaluate(numStack, opStack);
                }
                opStack.push(ch);
            }
        }
        while (!opStack.isEmpty()) {
            evaluate(numStack, opStack);
        }
        return numStack.peek();
    }

    void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
        int a = numStack.pop(), b = numStack.pop();
        char op = opStack.pop();
        int res = 0;
        if (op == '+') res = b + a;
        else if (op == '-') res = b - a;
        else if (op == '*') res = b * a;
        else if (op == '/') res = b / a;
        numStack.push(res);
    }

    int getPriority(char ch) {
        if (ch == '+' || ch == '-') return 1;
        if (ch == '*' || ch == '/') return 2;
        return 0;
    }
}

/*
思路:
1. 中缀表达式求值,使用两个stack,一个numStack, 一个opStack
2. 原则,能算则算。 a + b + c   --》 先计算a+b, 然后入栈
   a+b*c 不能先算a+b 因此,当后面*优先级高于栈顶时,直接入栈。
   操作数直接入栈。
   操作符: 如果当前操作符比栈顶高,入栈。否则,先计算栈顶。
   当表达式遍历完成,再处理opStack,每次取出一个op,然后从numStack取出两个数计算,将结果压到numStack中
   最后结果是numStack的栈顶元素
 */

772. 基本计算器 III - 力扣(LeetCode) 【hard】

  • 使用上面的模板。同样这题没有空格,也没有恶心的单目运算符,所以还好。
class Solution {
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();

        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') continue;
            if (Character.isDigit(ch)) {
                int num = 0, j = i;
                for(; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
                    num = num * 10 + (s.charAt(j) - '0');
                }
                numStack.push(num);
                i = j - 1;
            } else {
                if (ch == '(') {
                    opStack.push(ch);
                } else if (ch == ')') {
                    while (opStack.peek() != '(') {
                        evaluate(numStack, opStack);
                    }
                    opStack.pop();
                } else {
                    while (!opStack.isEmpty() && opStack.peek() != '(' && getPriority(ch) <= getPriority(opStack.peek())) {
                        evaluate(numStack, opStack);
                    }
                    opStack.push(ch);
                }
            }
        }
        while (!opStack.isEmpty()) {
            evaluate(numStack, opStack);
        }
        return numStack.peek();
    }

    void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
        int a = numStack.pop(), b = numStack.pop();
        char op = opStack.pop();
        int res = 0;
        if (op == '+') res = b + a;
        else if (op == '-') res = b - a;
        else if (op == '*') res = b * a;
        else if (op == '/') res = b / a;
        numStack.push(res);
    }

    int getPriority(char ch) {
        if (ch == '+' || ch == '-') return 1;
        if (ch == '*' || ch == '/') return 2;
        return 0;
    }
}

770. 基本计算器 IV - 力扣(LeetCode) [hard]

这个有变量,似乎跟前面不太一样,很难。TODO。