逆波兰表达式计算

一、前言

• 刚好公司业务需要，需要分析一个语法表达式转成一个业务需要的结果
• 所以接触到 逆波兰表达式。刚好可以满足我想要的结果。

二、逆波兰表达式

• 逆波兰表达式又叫做后缀表达式，跟 波兰表达式（前缀表达式）相对应
• 波兰逻辑学家 J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。
• 我们习惯将表达式写成( 1 + 2 ) * ( 3 + 4)，加减乘除等运算符写在中间，因此称呼为 中缀表达式。
• 而波兰表达式的写法为 (* (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。
• 逆波兰表达式的写法为((1 2 +) (3 4 +) *)，将运算符写在后面，因而也称为后缀表达式。
• 波兰表达式和逆波兰表达式有个好处，就算将圆括号去掉也没有歧义。

三、表达式的原理

• 看了简单的概念，还是云里雾里，管它什么表达式呢，到底怎么计算的？
• 主要用到了 栈 结构,我们怎么把中缀表达式转成计算器更容易处理的后缀表达式呢？

1、转换流程

• 1、把字符串从左到右遍历解析成每项是 数字 或者 运算符 放到同一个List中
• 2、然后初始化2个栈，一个是数字栈，一个是符号栈
• 3、遍历第一步生成的List
  • 如果是数字，直接放入到 数字栈中
  • 如果是左括号，直接放入到 符号栈中
  • 如果是右括号，就需要把和它对应的左括号中间的所有符号，从符号栈出栈放到数字栈中
    • 其中，右括号和左括号不入数字栈，直接舍弃
  • 如果是符号
  • • 如果当前符号栈为空或比符号栈顶的符号优先级高则直接入符号栈
  • • 如果优先级小于等于符号栈顶则把栈顶的符号取出放到数字栈
  • • 重复上面的操作，直到栈顶符号优先级小于它，把它放入符号栈中
• 4、当遍历结束之后，遍历符号栈数据，把它们取出放到数字栈中
• 5、最终数字栈的数据就是我们想得到的后缀表达式顺序了。

四、代码实现

• 其实看那么多文字，还不如看代码理解得快

public class Main {
    public static void main(String[] args) {
//        String str ="6+8*(2*4.5)+9/3";
        String str ="(1+2)*(3+4)";
        //将字符串转成list
        List<String> list = toExpressionList(str);
        System.out.println("拆分成项："+list);
        //中缀表达式转后缀表达式
        List<String> suffixList = infixToSuffix(list);
        System.out.println("后缀表达式："+suffixList);
        System.out.println("后缀表达式的计算结果为："+toCalculation(suffixList));
    }

    /**
     * 将表达式每一个部分转换成list
     * @param str 计算表达式
     * @return List
     */
    public static List<String> toExpressionList(String str) {
        List<String> list = new ArrayList<>(str.length());
        int i = 0;//用于遍历表达式的指针
        char c;
        StringBuilder tempStr = new StringBuilder();
        while (i < str.length()) {
            c = str.charAt(i);
            if (isSymbol(c)) {
                //如果是 符号，直接加入到list
                if (addItem(list, tempStr.toString())) {
                    // 如果添加成功，则重置
                    tempStr = new StringBuilder();
                }
                list.add("" + c);
            } else {
                tempStr.append(c);
            }
            i++;
        }
        // 最后一下
        addItem(list, tempStr.toString());
        return list;
    }


    private static boolean addItem(List<String> list, String item) {
        if (StringUtils.isNoneBlank(item)) {
            list.add(item.trim());
            return true;
        }
        return false;
    }

    /**
     * 判断是否是符号
     * @param c char
     * @return boolean
     */
    private static boolean isSymbol(Object c) {
        if (c instanceof Character) {
            char value = ((Character) c).charValue();
            return value == '+' || value == '-' || value == '*' || value == '/' || value == '('|| value == ')';
        } else if (c instanceof String) {
            String value = c.toString();
            return "+".equals(value) || "-".equals(value) || "*".equals(value) || "/".equals(value) || "(".equals(value)|| ")".equals(value);
        }
        return false;
    }

    /**
     * 计算后缀表达式 
     * @return 计算结果
     */
    public static String toCalculation(List<String> list){
        Deque<String> stack = new LinkedList<>();
        for(String item: list){
            if(isNumber(item)){
                stack.push(item);
            }else {
                BigDecimal x = new BigDecimal(stack.pop());
                BigDecimal y = new BigDecimal(stack.pop());
                switch (item){
                    case "+":
                        stack.push(x.add(y).toPlainString());
                        break;
                    case "-":
                        stack.push(y.subtract(x).toPlainString());
                        break;
                    case "*":
                        stack.push(x.multiply(y).toPlainString());
                        break;
                    case "/":
                        stack.push(y.divide(x,BigDecimal.ROUND_DOWN).toPlainString());
                        break;
                    default:
                        throw new RuntimeException("输入错误！");
                }
            }
        }
        return stack.pop();
    }

    /**
     * 中缀表达式转后缀表达式
     * @return List
     */
    private static List<String> infixToSuffix(List<String> list) {
        //初始化两个栈,dataStack 为数栈，symbolStack 为操作符栈
        List<String> dataStack = new ArrayList<>();
        Deque<String> symbolStack = new LinkedList<>();
        for (String item : list) {
            if (!isSymbol(item)) {
                //项直接入栈
                dataStack.add(item);
            } else if (item.equals("(")) {
                //左括号或者空直接入栈
                symbolStack.push(item);
            } else if (item.equals(")")) {
                //右括号将符号栈中左括号前的所有符号入数栈
                while (!symbolStack.peek().equals("(")) {
                    dataStack.add(symbolStack.pop());
                }
                symbolStack.pop();//清除括号
            } else if (symbolStack.peek() == null || judgePriority(item) > judgePriority(symbolStack.peek())) {
                //优先级比栈顶元素高，直接入栈
                symbolStack.push(item);
            } else {
                //优先级比栈顶元素低或者相等，将栈顶优先级高的入数栈
                while (symbolStack.peek() != null && judgePriority(item) <= judgePriority(symbolStack.peek())) {
                    dataStack.add(symbolStack.pop());
                }
                symbolStack.push(item);
            }
        }
        while (symbolStack.peek() != null) {
            dataStack.add(symbolStack.pop());
        }
        return dataStack;
    }

    /**
     * 返回运算符优先级，加减为1，乘除为2
     * @param str 运算符
     * @return 优先级
     */
    public static int judgePriority(String str){
        switch (str){
            case "*":
            case "/":
                return 2;
            case "+":
            case "-":
                return 1;
            case "(":
            case ")":
                return 0;
            default:
                throw new RuntimeException("输入有误！"+str);
        }
    }

    private static Pattern pattern = Pattern.compile("[+-]?[0-9]+(\\.[0-9]{1,4})?");
    /**
     * 是否是整数或小数
     */
    public static boolean isNumber(String str) {
        Matcher m = pattern.matcher(str);
        return m.matches();
    }

}

• 运行结果如下：

拆分成项：[(, 1, +, 2, ), *, (, 3, +, 4, )]
后缀表达式：[1, 2, +, 3, 4, +, *]
后缀表达式的计算结果为：21

• 这个代码其实就相当与一个计算器了。