表达式求值

1、栈实现中缀表达式求值

package bytedance;

import java.util.*;

public class Expression {
    public static void main(String[] args) {
        System.out.println(solve("2*(3+5)-7"));
        System.out.println(solve("(2+3)*4-5"));
    }

    static int[][] priorities = {
            //+ -  *   /   (   )
            {1, 1, -1, -1, -1, 1}, // +
            {1, 1, -1, -1, -1, 1}, // -
            {1, 1, 1, 1, -1, 1}, // *
            {1, 1, 1, 1, -1, 1}, // /
            {-1, -1, -1, -1, -1, 0}, // (
            {1, 1, 1, 1, 0, 1} // )
    };

    static Map<Character, Integer> map = new HashMap<>();

    public static int solve(String expression) {
        char[] cs = expression.toCharArray();
        char[] ss = {'+', '-', '*', '/', '(', ')'};
        for (int i = 0; i < ss.length; i++) map.put(ss[i], i);
        Deque<Character> ops = new ArrayDeque<>();
        Deque<Integer> nums = new ArrayDeque<>();
        for (int i = 0; i < cs.length; i++) {
            if (Character.isDigit(cs[i])) { // 如果是操作数，直接入栈
                nums.push(cs[i] - '0');
            } else { // 如果是运算符
                if (ops.isEmpty()) ops.push(cs[i]);
                else {
                    char op1 = ops.peek(), op2 = cs[i];
                    int comp = priorities[map.get(op1)][map.get(op2)];
                    if (comp > 0) { // 栈顶优先级更大
                        op1 = ops.pop(); // 操作符退栈
                        int num2 = nums.pop(), num1 = nums.poll();
                        nums.push(calculate(num1, num2, op1)); // 运算
                        i--; // 注意一定要将i--因为大于不扫描下一个字符
                    } else if (comp == 0) {
                        ops.pop(); // 弹出 ( 运算符
                    } else {
                        ops.push(op2);
                    }
                }
            }
        }
        while (!ops.isEmpty()) {
            int num2 = nums.poll(), num1 = nums.poll();
            nums.push(calculate(num1, num2, ops.pop()));
        }
        return nums.peek();
    }

    private static int calculate(int num1, int num2, char op) {
        if (op == '+') return num1 + num2;
        else if (op == '-') return num1 - num2;
        else if (op == '*') return num1 * num2;
        return num1 / num2;
    }
}

2、递归实现表达式求值

package bytedance;

public class ExpressionRecursion {
    static int idx = 0;
    static char[] cs;

    public static void main(String[] args) {
        cs = "(7+2)/3-5*2+12*(4+3)".toCharArray();
        System.out.println(expressionValue());
    }

    // 求一个因子的值（一个因子可以是一个数，或者一个(xxx)表达式）
    public static int factorValue() {
        int ret = 0;
        char c = cs[idx];
        if (c == '(') { // 因子是由左右括号和表达式组成
            idx++; // 把左括号扔掉
            ret = expressionValue(); // 处理表达式
            idx++; // 把右括号扔掉
        } else { // 因子是一个数
            while (idx < cs.length && Character.isDigit(cs[idx])) {
                ret = ret * 10 + (cs[idx++] - '0');
            }
        }
        return ret;
    }

    // 求一项的值（一个项必须是+-号的一边，由至少一个因子组成）
    public static int termValue() {
        // 求一个项的值
        int ret = factorValue();
        while (idx < cs.length) {
            char op = cs[idx];
            if (op == '*' || op == '/') { // 说明后面还有后续因子
                idx++;
                int val = factorValue();
                if (op == '*') ret *= val;
                else ret /= val;
            } else break; // 没有因子了
        }
        return ret;
    }

    // 表达式（由多个项组成，通过+-号运算这些项）
    public static int expressionValue() { // 求一个表达式的值
        int ret = termValue(); // 求第一项的值
        while (idx < cs.length) {
            char op = cs[idx];
            if (op == '+' || op == '-') {
                idx++;
                int val = termValue();
                if (op == '+') ret += val;
                else ret -= val;
            } else break; // 如果是右括号，说明输入结束
        }
        return ret;
    }
}