题解 | #表达式求值#

package org.example.test;

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class SolveTest {
    public static void main(String[] args) {
        String s = "a/b+(c*d-e*f)/g";
//        System.out.println(getSuffix(s));
        String s1 = "3+2*3*4-1";
        System.out.println(solve(s1));
    }

    /**
     * 顺序扫描表达式的每一项，然后根据他的类型做如下相应操作：
     * 若该项是操作数，则将其压入栈中，
     * 若该项是操作符<op>，则连续从栈中退出两个操作数Y和X， 形成运算指令 X<op>Y,并将计算结果压入栈中。
     * 当表达式的所有项都扫描并处理万后，栈顶存放的就是最后计算的结果。
     *
     * @param s
     * @return
     */
    public static int solve(String s) {
        // write code here
        Set<String> ops = new HashSet<>();
        ops.add("+");
        ops.add("-");
        ops.add("*");
        ops.add("/");
        String suffix = getSuffix(s);
        System.out.println(suffix);
        Stack<Integer> stack = new Stack<>();
        String[] list = suffix.split(",");
        for (String c : list) {
            if (ops.contains(c)) {
                int a = stack.pop();
                int b = stack.pop();
                int sum = 0;
                if (c.equals("+")) {
                    sum = a + b;
                } else if (c.equals("-")) {
                    sum = b - a;
                } else if (c.equals("*")) {
                    sum = a * b;
                }
                stack.push(sum);
            } else {
                stack.push(Integer.valueOf(c));
            }
        }
        return stack.pop();
    }

    /**
     * 转换为后缀表达式，使用逗号把每个部分隔离，保证100等超过2位数的数字出现问题。
     * 将中缀表达式转换为后缀表达式的算法思想如下：
     * 从左向右开始扫描中缀表达式，
     * 遇到数字时，加入后缀表达式，
     * 遇到运算符时：
     * a. 若为'(', 入栈。
     * b. 若为')'，则以次把栈中的运算符加入后缀表达式，直到出现'(', 从占中删除'('。
     * c. 若为除括号以外的其他运算符，当其优先级高于除'('外的栈顶运算符时，直接入栈，否则从栈顶开始，以次弹出比当前处理的运算符
     * 优先级高或者相等的运算符，直到一个比它优先级低的或者遇到'('为止。
     *
     * @param s
     * @return
     */
    private static String getSuffix(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder buffer = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '+' || c == '-') {
                buffer.append(",");
                if (!stack.isEmpty() && (stack.peek() == '-' || stack.peek() == '*' || stack.peek() == '+' || stack.peek() == '/')) {
                    buffer.append(stack.pop());
                    buffer.append(",");
                }
                stack.push(c);
            } else if (c == '*' || c == '/') {
                buffer.append(",");
                if (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                    buffer.append(stack.pop());
                    buffer.append(",");
                }
                stack.push(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (stack.peek() != '(') {
                    buffer.append(",");
                    buffer.append(stack.pop());
                }
                stack.pop();
            } else {
                buffer.append(c);
            }
        }
        while (!stack.isEmpty()) {
            buffer.append(",");
            buffer.append(stack.pop());
        }
        return buffer.toString();
    }

}