题解 | #表达式求值#

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);
        int resolve = resolve(res);
        System.out.println("resolve = " + resolve);
//        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 s
     * @return
     */
    public static int resolve(String s) {
        Stack<Integer> integerStack = new Stack<>();
        Stack<Character> characterStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            // 针对数字直接输出
            if (tmp >= '0' && tmp <= '9') {
                // 考虑多位的情况
                StringBuilder sb = new StringBuilder();
                sb.append(tmp);
                while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
                    i++;
                    tmp = s.charAt(i);
                    sb.append(tmp);
                }
                integerStack.add(Integer.parseInt(sb.toString()));
            } else if (characterStack.isEmpty() || tmp == '(') {
                characterStack.push(tmp);
            } else if (tmp == ')') {
                while (characterStack.peek() != '(') {
                    // 获取符号
                    Character 符号 = characterStack.pop();
                    // 获取数字
                    Integer 右边 = integerStack.pop();
                    Integer 左边 = integerStack.pop();
                    int resInt = calculate(符号, 左边, 右边);
                    integerStack.push(resInt);
                }
                characterStack.pop();
            } else {
                // 低优先级的情况
                while (!characterStack.isEmpty() && !compareRank(tmp, characterStack.peek())) {
                    // 获取符号
                    Character 符号 = characterStack.pop();
                    // 获取数字
                    Integer 右边 = integerStack.pop();
                    Integer 左边 = integerStack.pop();
                    int resInt = calculate(符号, 左边, 右边);
                    integerStack.push(resInt);
                }
                characterStack.push(tmp);
            }
        }
        while (!characterStack.isEmpty()) {
            // 获取符号
            Character 符号 = characterStack.pop();
            // 获取数字
            Integer 右边 = integerStack.pop();
            Integer 左边 = integerStack.pop();
            int resInt = calculate(符号, 左边, 右边);
            integerStack.push(resInt);
        }
        return integerStack.pop();
    }

    /**
     * @param 符号
     * @param 左边
     * @param 右边
     * @return
     */
    public static int calculate(char 符号, int 左边, int 右边) {
        int 结果 = 0;
        switch (符号) {
            case '+':
                结果 = 左边 + 右边;
                break;
            case '-':
                结果 = 左边 - 右边;
                break;
            case '*':
                结果 = 左边 * 右边;
                break;
            case '/':
                结果 = 左边 / 右边;
                break;
            default:
                break;
        }
        return 结果;
    }

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

}