题解 | #表达式求值#迪杰斯特拉双栈解法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        System.out.println(djt(s));
    }

    /**
     * 迪杰斯特拉算法
     *
     * @param s 运算字符串
     * @return 运算结果
     */
    private static Integer djt(String s) {
        Map<String, Integer> symbolMap = new HashMap<String, Integer>() {{
            put("+", 1);
            put("-", 1);
            put("*", 2);
            put("/", 2);
            put("(", 0);
        }};
        Stack<Integer> numberStack = new Stack<>();
        Stack<String> symbolStack = new Stack<>();
        String[] arr = s.split("");
        boolean negative = false;
        for (int i = 0; i < arr.length; i++) {
            String value = arr[i];
            if (value.equals("(")) {
                symbolStack.push(value);
            } else if (value.equals(")")) {
                String pop;
                while (!symbolStack.isEmpty() && !(pop = symbolStack.pop()).equals("(")) {
                    Integer b = numberStack.pop();
                    Integer a = numberStack.pop();
                    if (pop.equals("+")) {
                        numberStack.push(a + b);
                    } else if (pop.equals("-")) {
                        numberStack.push(a - b);
                    } else if (pop.equals("*")) {
                        numberStack.push(a * b);
                    } else if (pop.equals("/")) {
                        numberStack.push(a / b);
                    }
                }
            } else if (symbolMap.containsKey(value)) {
                if (value.equals("-") && (i == 0 || arr[i - 1].equals("("))) {
                    negative = true;
                } else {
                    while (!symbolStack.isEmpty()) {
                        String pop = symbolStack.pop();
                        if (symbolMap.get(pop) >= symbolMap.get(value)) {
                            Integer b = numberStack.pop();
                            Integer a = numberStack.pop();
                            if (pop.equals("+")) {
                                numberStack.push(a + b);
                            } else if (pop.equals("-")) {
                                numberStack.push(a - b);
                            } else if (pop.equals("*")) {
                                numberStack.push(a * b);
                            } else if (pop.equals("/")) {
                                numberStack.push(a / b);
                            }
                        } else {
                            symbolStack.push(pop);
                            break;
                        }
                    }
                    symbolStack.push(value);
                }
            } else {
                StringBuilder tmp = new StringBuilder(negative ? "-" : "");
                tmp.append(value);
                while (i < arr.length - 1 && Character.isDigit(arr[i + 1].charAt(0))) {
                    i++;
                    tmp.append(arr[i]);
                }
                negative = false;
                numberStack.push(Integer.valueOf(tmp.toString()));
            }
        }
        while (!symbolStack.isEmpty()) {
            String pop = symbolStack.pop();
            Integer b = numberStack.pop();
            Integer a = numberStack.pop();
            if (pop.equals("+")) {
                numberStack.push(a + b);
            } else if (pop.equals("-")) {
                numberStack.push(a - b);
            } else if (pop.equals("*")) {
                numberStack.push(a * b);
            } else if (pop.equals("/")) {
                numberStack.push(a / b);
            }
        }
        return numberStack.pop();
    }
}