逆波兰表达式算法

摘要：将中缀表达式转化为后缀表达式，以及计算后缀表达式的算法。

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author YaoQi
 * Date: 2019/1/5 15:45
 * Modified:
 * Description: 中缀表达式转后缀表达式
 */
public class InfixToSuffixHandler {

    private static final Logger logger = LoggerFactory.getLogger(InfixToSuffixHandler.class);

    private static HashSet<Character> opStr = new HashSet<>();

    static {
        logger.info("Initialization operator");
        opStr.add('+');
        opStr.add('-');
        opStr.add('*');
        opStr.add('/');
        logger.info("Initialization finished");
    }

    /**
     * 判断字符是否为操作符
     *
     * @param c 字符
     * @return
     */
    private static boolean isOpStr(char c) {
        return opStr.contains(c);
    }

    /**
     * 判断字符是否为操作数
     *
     * @param c 字符
     * @return
     */
    private static boolean isOperand(char c) {
        return c >= '0' && c <= '9';
    }

    /**
     * 得到当前操作符的优先级
     *
     * @param c 操作符
     * @return
     */
    private static int priority(char c) {
        switch (c) {
            case '*':
            case '/':
                return 3;
            case '+':
            case '-':
                return 2;
            case '(':
                return 1;
            default: {
                logger.error("c: {} is not operator marks", c);
                return 0;
            }
        }
    }

    /**
     * 用后缀表达式求值
     *
     * @param suffixExpr 后缀表达式
     * @return
     */
    public static int numberCalculate(String suffixExpr) {
        Stack<Integer> count = new Stack<>();
        char c;
        int number1, number2;
        for (int i = 0; i < suffixExpr.length(); i++) {
            if (isOperand(c = suffixExpr.charAt(i))) {
                count.push(c - '0');
            } else {
                number2 = count.pop();
                number1 = count.pop();
                switch (c) {
                    case '+':
                        count.push(number1 + number2);
                        break;
                    case '-':
                        count.push(number1 - number2);
                        break;
                    case '*':
                        count.push(number1 * number2);
                        break;
                    case '/':
                        count.push(number1 / number2);
                        break;
                    default:
                        break;
                }
            }
        }
        return count.pop();
    }


    /**
     * 将中缀表达式转化为后缀表达式
     *
     * @param expression 中缀表达式
     * @return 返回后缀表达式
     */
    public static StringBuilder getSuffixExpression(String expression) {
        //保存已将建立的后缀表达式
        StringBuilder suffixExpr = new StringBuilder();
        //操作符栈
        Stack<Character> opStr = new Stack<>();
        //输入表达式某个位置的字符
        char c;
        //运算符栈中弹出的字符
        char pop;
        for (int i = 0; i < expression.length(); i++) {
            c = expression.charAt(i);
            //如果当前字符为操作数
            if (isOperand(c)) {
                suffixExpr.append(c);
            } else if (isOpStr(c)) {
                //如果当前字符为操作符
                if (opStr.isEmpty()) {
                    opStr.push(c);
                } else {
                    while (!opStr.isEmpty() && priority(opStr.peek()) >= priority(c)) {
                        pop = opStr.pop();
                        suffixExpr.append(pop);
                    }
                    opStr.push(c);
                }
            } else if ('(' == c) {
                //如果当前字符为‘(’
                opStr.push(c);
            } else if (')' == c) {
                //如果当前字符为‘)’
                while ((pop = opStr.pop()) != '(') {
                    suffixExpr.append(pop);
                }
            } else {
                logger.error("c: {} is not valid in {}", c, expression);
            }
        }
        while (!opStr.isEmpty()) {
            suffixExpr.append(opStr.pop());
        }
        System.out.println("转换后的后缀表达式为：" + suffixExpr);
        return suffixExpr;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in, "UTF-8");
        //输入的表达式
        String expression = scan.nextLine();
        // 生成后缀表达式
        StringBuilder suffixExpr = getSuffixExpression(expression);
        System.out.println("后缀表达式计算的结果为：" + numberCalculate(suffixExpr.toString()));

    }
}

tips

一般的代数表达式都是中缀表达式，也就是操作数在操作符两边，后缀表达式（逆波兰表达式）就是操作符在操作数后面。

例如：

a+b —> a,b,+

a+(b-c) —> a,b,c,-,+

a+(b-c)d —> a,b,c,-,d,,+

算法核心思想：将中缀表达式转为后缀表达式，再使用栈来对后缀表达式求值。 求值的过程就是遇到操作符就计算栈内的表达式，遇到操作数就入栈，最终栈中的元素就是最终的结果了。

该算法还可以扩展为逻辑运算符，例如: B and C not D 在处理类似于这种逻辑表达式转换的时候也能使用该算法，笔者曾在实践中使用过改造该算法进行ES查询语句的构建，支持逻辑表达式的搜索。