题解 | #表达式求值#

package com.hhdd;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @Author huanghedidi
 * @Date 2022/8/21 22:27
 */
public class 表达式求值 {


    public static void main(String[] args) {
        String res = "1-2-3";
        List<String> list = mid2Posix(res);
        System.out.println("res = " + res);
        int calculate = calculate(list);
        System.out.println("calculate = " + calculate);
//        String[] aa = res.split("[+\\-\\*/()]");
//        System.out.println("aa = " + aa);
    }

    public int solve(String s) {
        // write code here
        List<String> strings = mid2Posix(s);
        return calculate(strings);
    }

    /**
     * 后缀表达式计算
     * 使用栈
     *
     * @param express
     * @return
     */
    public static int calculate(List<String> express) {
        Pattern isDigital = Pattern.compile("[0-9]*");
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < express.size(); i++) {
            String tmp = express.get(i);

            if (isDigital.matcher(tmp).matches()) {
                // 遇到数字直接入栈
                stack.push(Integer.parseInt(tmp));
            } else {
                // 符号则直接出栈两个数，先出的数是右边，后出的数是左边
                Integer i2 = stack.pop();
                Integer i1 = stack.pop();
                Integer res = 0;
                switch (tmp) {
                    case "+":
                        res = i1 + i2;
                        break;
                    case "-":
                        res = i1 - i2;
                        break;
                    case "*":
                        res = i1 * i2;
                        break;
                    case "/":
                        res = i1 / i2;
                        break;
                    default:
                        break;
                }
                stack.push(res);
            }
        }
        return stack.pop();
    }


    /**
     * 中缀表达式转后缀表达式
     *
     * @param express
     * @return
     */
    public static List<String> mid2Posix(String express) {
        Stack<Character> stack = new Stack<>();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < express.length(); i++) {
            char tmp = express.charAt(i);
            // 针对数字直接输出
            if (tmp >= '0' && tmp <= '9') {
                // 考虑多位的情况
                StringBuilder sb = new StringBuilder();
                sb.append(tmp);
                while (i + 1 < express.length() && express.charAt(i + 1) >= '0' && express.charAt(i + 1) <= '9') {
                    i++;
                    tmp = express.charAt(i);
                    sb.append(tmp);
                }
                res.add(sb.toString());
            } else if (stack.isEmpty() || tmp == '(') {
                stack.push(tmp);
            } else if (tmp == ')') {
                while (stack.peek() != '(') {
                    res.add(stack.pop() + "");
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && !compareRank(tmp, stack.peek())) {
                    res.add(stack.pop() + "");
                }
                stack.push(tmp);
            }
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop() + "");
        }
        return res;
    }

    /**
     * 优先级比较
     *
     * @param c
     * @return
     */
    public static boolean compareRank(char c1, char c2) {
        if (c2 == '(') {
            return true;
        }
        // 加减遇到加减是同优先级
        // 加减遇到乘除是低优先级
        // 遇到乘除默认是同优先级
        if (c1 == '+' || c1 == '-') {
            return false;
        }
        return true;
    }

}