题解 | #四则运算#

import java.util.*;
/**
 * @author hll[yellowdradra@foxmail.com]
 * @date 2022-10-10 21:03
 **/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String expression = in.nextLine();
        // 拆分表达式 e.g. "2+5" -> "2" "+" "5"
        List<String> infix = splitExpression(expression);
        // 将中缀表达式转换为后缀表达式
        List<String> suffix = infix2suffix(infix);
        // 逆波兰算法
        LinkedList<Integer> numberStack = new LinkedList<>();
        for (String op : suffix) {
            // 如果op是运算符 则弹出运算数栈numberStack的两个运算数进行运算
            if (isOperation(op)) {
                // 注意先出栈的是运算数2 完了是运算数1 四则运算中"-","/"的运算结果是与运算数的顺序是相关的
                numberStack.push(operate(numberStack.pop(), numberStack.pop(), op));
            } else {
                numberStack.push(Integer.parseInt(op));
            }
        }
        System.out.println(numberStack.pop());
    }

    static Integer operate(Integer operator2, Integer operator1, String operation) {
        Integer result = 0;
        switch (operation) {
            case "+":
                result = operator1 + operator2; break;
            case "-":
                result = operator1 - operator2; break;
            case "*":
                result = operator1 * operator2; break;
            case "/":
                result = operator1 / operator2; break;
            default:
                break;
        }
        return result;
    }

    static List<String> splitExpression(String expression) {
        // 为了方便拆分 先对表达式进行预处理
        expression = expression
                .replaceAll("\\{|\\[", "(")
                .replaceAll("\\}|\\]", ")")
                .replaceAll(" ", "");
        List<String> infix = new ArrayList<>();
        for (int i = 0; i < expression.length();) {
            int j = i;
            // 考虑几种 "-" 作为运算数的符号 而不是运算符的情况
            // '-' 开头 && 后一位是数字的 有可能是负数
            // 情况1: '-'号位于第一位 "-2";
            // 情况2: '-'号位于左括号后面 "2+(-3)"
            boolean isNegativeNumber = expression.charAt(j) == '-'
                    && Character.isDigit(expression.charAt(j + 1))
                    && (j == 0 || '(' == expression.charAt(j - 1));
            // 正数情况 根据题意 不考虑浮点数
            boolean isPositiveNumber = Character.isDigit(expression.charAt(j));
            if (isNegativeNumber || isPositiveNumber) {
                // 如果是负数 那么要从负号后一位开始找0-9的数字 一直找到找不到为止
                j = isNegativeNumber ? j + 1 : j;
                while (j < expression.length() && Character.isDigit(expression.charAt(j))) {
                    j++;
                }
                infix.add(expression.substring(i, j));
                i = j;
            } else {
                infix.add(String.valueOf(expression.charAt(i++)));
            }
        }
        return infix;
    }

    static List<String> infix2suffix(List<String> infix) {
        List<String> suffix = new ArrayList<>();
        LinkedList<String> stack1 = new LinkedList<>();
        LinkedList<String> stack2 = new LinkedList<>();
        for (String op : infix) {
            if (isOperation(op)) {
                if (stack1.isEmpty() || "(".equals(op)) {
                    stack1.push(op);
                } else {
                    // stack1 非空 且 op为右括号
                    if (")".equals(op)) {
                        // 把stack1里左括号之前的运算数/符 全部倒入stack2
                        while (!"(".equals(stack1.peek())) {
                            stack2.push(stack1.pop());
                        }
                        // 丢掉左括号
                        stack1.pop();
                    } else {
                        // 如果op是 + - * /
                        while (!stack1.isEmpty() && higherPriority(stack1.peek(), op)) {
                            stack2.push(stack1.pop());
                        }
                        stack1.push(op);
                    }
                }
            } else {
                stack2.push(op);
            }
        }

        // stack1 剩余操作符全部倒入 stack2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        
        // 利用LinkedList的双端队列性质倒序输出stack2的数
        while (!stack2.isEmpty()) {
            suffix.add(stack2.removeLast());
        }

        return suffix;
    }

    static boolean isOperation(String op) {
        // 四则运算("+", "-", "*", "/")的运算符长度都为1
        return op.length() == 1 && !Character.isDigit(op.charAt(0));
    }

    static boolean higherPriority(String operate1, String operate2) {
        return priority(operate1) - priority(operate2) >= 0;
    }


    static int priority(String operate) {
        // "+" "-" 优先级为0 "*" "/" 优先级为1
        if ("+".equals(operate) || "-".equals(operate)) {
            return 0;
        } else if ("*".equals(operate) || "/".equals(operate)){
            return 1;
        } else {
            return -1;
        }
    }
}