Java如何使用逆波蘭式(后綴表達(dá)式)計算表達(dá)式的值

更新時間：2024年06月17日 10:30:11 作者：編程經(jīng)驗分享

這篇文章主要介紹了Java如何使用逆波蘭式(后綴表達(dá)式)計算表達(dá)式的值,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

問題

實(shí)際項目中需要對接口的返回結(jié)果做處理，按照配置中的返回結(jié)果字段和算術(shù)運(yùn)算符（+ - * /）和左右括號組合得到一個算術(shù)表達(dá)式，并計算得到值返回。

如何解決

獲取到接口的返回值后，便可以得到一個具體的中綴表達(dá)式
將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式（逆波蘭式）
計算后綴表達(dá)式的值

代碼

操作符枚舉類

public enum Operator {

    ADD(30, '+'),
    SUB(30, '-'),
    MUL(40, '*'),
    DIV(40, '/'),
    LEFT(0, '('),
    RIGHT(0, ')');

    static {
        map = Arrays.stream(values()).collect(toMap(ExprUtils.Operator::getSymbol, e -> e));
    }

    private final int priority;
    private final char symbol;

    private static final Map<Character, ExprUtils.Operator> map;

    Operator(Integer priority, Character symbol) {
        this.priority = priority;
        this.symbol = symbol;
    }

    public Character getSymbol() {
        return this.symbol;
    }

    //返回對應(yīng)的優(yōu)先級數(shù)字
    public static int getPriority(Character symbol) {
        ExprUtils.Operator operator = map.get(symbol);
        assert Objects.nonNull(operator);
        return operator.priority;
    }

    public static boolean notRightBracket(Character symbol) {
        ExprUtils.Operator operator = map.get(symbol);
        if (Objects.isNull(operator)) {
            return false;
        }
        return !operator.equals(RIGHT);
    }

    public static boolean isOperator(Character symbol) {
        ExprUtils.Operator operator = map.get(symbol);
        if (Objects.isNull(operator)) {
            return false;
        }
        switch (operator) {
            case ADD:
            case SUB:
            case MUL:
            case DIV: return true;
            default: return false;
        }
    }
}

表達(dá)式工具類

public class ExprUtils {

    /*判斷中綴表達(dá)式是否合法*/
    public static boolean expressionCheck(String str) {
        Deque<Character> stack = new LinkedList<>();
        //不合法情況1:括號不匹配
        for(char ch : str.toCharArray()) {
            if(ch == '(') {
                stack.push(ch);
            }

            if(ch == ')') {
                if(stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }

        //不合法情況2:操作符左右元素不合法
        for(int i = 0 ; i < str.length() ; i++) {
            //先判斷 '-' 是不是負(fù)數(shù)符號
            if('-' == str.charAt(i)) {
                if( 0 == i || Operator.notRightBracket(str.charAt(i - 1))) //如果 - 在第一位或者前面有+-*/(,一定是作為負(fù)數(shù)符號而非操作符
                    i++;
            }
            if(Operator.isOperator(str.charAt(i))) {
                if( 0 == i || str.length() - 1 == i)
                    return false;
                if( Operator.isOperator(str.charAt(i - 1)) || Operator.isOperator(str.charAt(i + 1)) )
                    return false;
                if( '(' == str.charAt(i - 1) || ')' == str.charAt(i + 1) )
                    return false;
            }
        }

        //不合法情況3:左括號和右括號相鄰,例：a+()和(a+b)(a+b)
        for(int i = 0 ; i < str.length() ; i++) {
            if(str.charAt(i) =='(' && i + 1 < str.length() && str.charAt(i + 1) == ')')
                return false;
            if(str.charAt(i) == ')' && i + 1 < str.length() && str.charAt(i + 1) == '(')
                return false;
        }
        return true;
    }

    /**
     * 將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
     *
     * @param exp 中綴表達(dá)式
     * @return 后綴表達(dá)式
     */
    public static List<String> parseExpression(String exp) {

        Deque<Character> operation = new LinkedList<>();
        List<String> target = new ArrayList<>();

        for (int i = 0; i < exp.length(); i++) {
            if(((exp.charAt(i) == '-' || exp.charAt(i) == '+') && (i == 0 || Operator.notRightBracket(exp.charAt(i - 1))))
                    || Character.isDigit(exp.charAt(i)) ) {
                // 如果是正號就不用加入，負(fù)號或者數(shù)字本身都要加入
                StringBuilder tempStr = new StringBuilder(exp.charAt(i) != '+' ? exp.substring(i, i + 1) : "");
                while (i + 1 <  exp.length() && Character.isDigit(exp.charAt(i + 1))) {
                    tempStr.append(exp.charAt(++i));
                }
                target.add(tempStr.toString());
            } else {
                if ('(' == exp.charAt(i)) {
                    operation.push(exp.charAt(i));
                } else if (')' == exp.charAt(i)) {
                    while ('(' != operation.peek()) {
                        target.add(operation.pop().toString());
                    }
                    operation.pop();
                } else {
                    while (!operation.isEmpty()
                            && Operator.getPriority(operation.peek()) >= Operator.getPriority(exp.charAt(i))) {
                        target.add(operation.pop().toString());
                    }

                    operation.push(exp.charAt(i));
                }
            }
        }

        while (!operation.isEmpty()) {
            target.add(operation.pop().toString());
        }

        return target;
    }

    /**
     * 計算后綴表達(dá)式
     *
     * @param list 后綴表達(dá)式
     * @return 計算結(jié)果
     */
    public static int calculate(List<String> list) {
        Stack<Integer> stack = new Stack<>();// 創(chuàng)建棧
        for (String item : list) {
            if (item.matches("^-?\\d+(\\.\\d+)?$")) { //使用正則表達(dá)式匹配多位數(shù)
                stack.push(Integer.parseInt(item));
            } else {
                int num2 = stack.pop();	// pop出兩個數(shù)，并運(yùn)算， 再入棧
                int num1 = stack.pop();
                int res;
                switch (item) {
                    case "+": res = num1 + num2; break;
                    case "-": res = num1 - num2; break;
                    case "*": res = num1 * num2; break;
                    case "/": res = num1 / num2; break;
                    default: throw new RuntimeException("運(yùn)算符有誤");
                }
                stack.push(res);
            }

        }

        return stack.pop();
    }
}

測試類

class ExprUtilsTest {

    @Test
    void calculate() {
        String infixExpression = "-6+((-2)+(2+4))";
        if (!ExprUtils.expressionCheck(infixExpression)) {
            System.out.println("表達(dá)式不合法");
        } else {
            System.out.println("中綴表達(dá)式為：" + infixExpression);
            List<String> calculateExpression = ExprUtils.parseExpression(infixExpression);
            System.out.println("后綴表達(dá)式為：" + calculateExpression);
            System.out.printf("Answer=%d", ExprUtils.calculate(calculateExpression));
        }
    }
}