题解 | #四则运算#

package org.example.test.practice;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Scanner scanner = new Scanner(System.in);
        String line = "(7+5*4*3+6)";
        line = line.replace('{', '(');
        line = line.replace('}', ')');
        line = line.replace('[', '(');
        line = line.replace(']', ')');
        List<String> list = new ArrayList<>();
        int num = 0;
        int count = 0;
        char last = '+';
        for (int i = 0; i < line.length(); i++) { // 转换为字符串list
            if (Character.isDigit(line.charAt(i))) {
                num = num * 10 + (line.charAt(i) - '0');
                count = 0;
                if (i == line.length() - 1) {
                    list.add(String.valueOf(num));
                }
            } else {
                if (i == 0 && line.charAt(i) != '(') { //第一个字符是符号的情况
                    last = line.charAt(i);
                    continue;
                }
                if (count == 0) { // 当前是字符，前面已经累加数字
                    if (last == '+') {
                        list.add(String.valueOf(num)); // 添加数字
                    } else {
                        list.add('-' + String.valueOf(num));
                    }
                    num = 0;
                    count++; // 只能添加一次，如果遇到连续符号字符。
                    last = '+';
                }
                if (i != 0 && line.charAt(i - 1) == '(' && (line.charAt(i) == '+' || line.charAt(i) == '-')) { // 遇到数字带符号
                    last = line.charAt(i);
                    continue;
                }
                list.add(String.valueOf(line.charAt(i))); // 添加一般运算符

            }
        }
        System.out.println(line);
        System.out.println(JSONObject.toJSONString(list));
        List<String> ans = new ArrayList<>();
        Deque<String> stack = new LinkedList<>();
        for (int i = 0; i < list.size(); i++) { // 转换为后缀表达式
            String s = list.get(i);
            if (Character.isDigit(s.charAt(s.length() - 1))) {
                ans.add(s); // 如果是数字，则直接添加到后缀表达式。
            } else if (s.equals("(")) {
                stack.push(s); // 如果是(，则直接入栈。
            } else if (s.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) { // 当当前字符是)，则需要弹出栈内，直到遇到(，最后弹出(.
                    ans.add(stack.pop());
                }
                stack.pop();
            } else {
                if (stack.isEmpty()) {
                    stack.push(s);
                } else {
                    if (stack.peek().equals("(")) { // 如果栈顶是(，则直接入栈、
                        stack.push(s);
                    } else {
                        boolean flag = false;
                        while (!stack.isEmpty() && !stack.peek().equals("(")) { // 当当前运符号优先级小于等于栈顶优先级，一直弹出，直到大于栈内优先级，并且遇到(停止。
                            String c = stack.peek();
                            if ((c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/")) && (s.equals("+") || s.equals("-"))) {
                                ans.add(stack.pop());
                                flag = true;
                            } else {
                                stack.push(s);
                                break;
                            }
                        }
                        if (flag) { // 如果大于栈内优先级，直接入栈。
                            stack.push(s);
                        }
                    }
                }
            }
        }
        while (!stack.isEmpty()) {
            ans.add(stack.pop());
        }
        System.out.println(JSONObject.toJSONString(ans));
        Deque<Integer> stack1 = new LinkedList<>();
        for (int i = 0; i < ans.size(); i++) {// 后缀表达式直接计算
            String c = ans.get(i);
            if (!Character.isDigit(c.charAt(c.length() - 1))) {
                int a = stack1.pop();
                int b = stack1.pop();
                int d = 0;
                if (c.equals("+")) {
                    d = a + b;
                } else if (c.equals("-")) {
                    d = b - a;
                } else if (c.equals("/")) {
                    d = b / a;
                } else {
                    d = b * a;
                }
                stack1.push(d);
            } else {
                stack1.push(Integer.parseInt(c));
            }
        }
        System.out.println(stack1.pop());
    }
}