@[toc]

前言

所有博客文件目录索引：博客目录索引(持续更新)

一、认识前缀、中缀、后缀表达式

在现实生活中我们计算的数学公式表达式就是中缀表达式，例如：(1 + 5) * 4 + 3 * 5

后缀表达式是什么呢，就是将中缀表达式转换成计算机能够看得懂的式子（后缀表达式），接着让计算机来根据这个后缀表达式来进行快速计算。

中缀表达式：(1 + 5) * 4 + 3 * 5
转为后缀表达式：1, 5, +, 4, *, 3, 5, *, +

怎么计算后缀表达式呢？可借助于栈这个数据结构来实现快速计算，主要逻辑是遍历一遍，遇到数字就入栈，遇到符号就出栈两个，进行运算后入栈即可。
1    入栈                  s = [1]
5    入栈                  s = [1, 5]
+   出栈计算和，入栈和       s=[6]
4    入栈                  s=[6, 4]
*   出栈计算乘，入栈乘       s=[24]
3    入栈       			 s=[24, 3]
5    入栈       			 s=[24, 3, 5]
*    出栈计算乘，入栈乘  	s=[24, 15]
+    出栈计算和，入栈和  	s=[39]
最后结果就是39。

前缀表达式的话就不怎么常用，其特点就是运算符在操作数之前，其被称为波兰表达式。

• 而后缀表达式是数字在前，符号在后，也就是逆波兰表达式。

中缀表达式：a+b*c-(d+e)
前缀表达式：-+a*bc+de

二、中缀表达式求值

2.1、中缀转后缀计算（Java题解）

中缀表达式求值过程：中缀表达式(字符串) => 中缀表达式(List集合) => 后缀表达式(List集合) => 根据后缀表达式求值。

规则：

1、中缀表达式(字符串) => 中缀表达式(List集合)
速记流程：扫描一遍，非字符直接添加到集合，若是数字需要考虑多位数情况取到存储到集合。

2、中缀表达式(List集合) => 后缀表达式(List集合)
所需结构：栈(存储中间符号)、List集合(存储后缀表达式)
额外：符号权重，+、-、*、/、(、)【1, 1, 2, 2, 0, 0】
速记流程：遍历一遍
	1) 若是匹配到数：直接添加到集合。
	2) 若是匹配到(，入栈。
	3) 若是匹配到)，开始出栈直至匹配到(，整个出栈过程中将符号添加到集合中
	4) 若是匹配到符号，先找到所有栈中栈顶元素权重>=该符号的符号，若是有就出栈添加到集合，最后将当前符号入栈。
	5) 遍历一遍结束后，若是栈中还有符号那么就出栈添加到集合。
	
3、 后缀表达式(List集合) => 根据后缀表达式求值
速记流程：遍历一遍集合
    1) 若是碰到数，入栈
    2) 若是碰到符号，根据对应的符号出栈两个元素值 pop(num2)、pop(num1)。注意出栈时，是先出栈的num2
		若是+：num1 + num2；若是-：num1 - num2；若是*：num1 * num2；若是/：num1 / num2
		
测试：
"1+((2+3)*4)-5" => [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] => [1, 2, 3, +, 4, *, +, 5, -] => 16

代码：

public class Calculator {
    //后缀表达式(List集合) => 根据后缀表达式求值
    private static Integer calculateSuffix(List<String> suffixList) {
        //栈中临时存储元素值
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < suffixList.size(); i++) {
            String s = suffixList.get(i);
            if (!isOper(s)) {
                //若是数字直接存储到栈中
                stack.push(Integer.valueOf(s));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                int result = 0;
                switch (s) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num1 - num2;
                        break;
                    case "*":
                        result = num1 * num2;
                        break;
                    case "/":
                        result = num1 / num2;
                        break;
                    default:
                        break;
                }
                stack.push(result);
            }
        }
        return stack.isEmpty() ? 0 : stack.pop();
    }

    //中缀表达式(List集合) => 后缀表达式(List集合)
    private static List<String> infixToSuffixExpr(List<String> infixList) {
        //栈：存储符号
        Stack<String> stack = new Stack<>();
        //结果集
        List<String> result = new ArrayList<>();
        for (int i = 0; i < infixList.size(); i++) {
            String s = infixList.get(i);
            //若是当前是数字：直接添加到集合
            if (!isOper(s)) {
                result.add(s);
            }else if ("(".equals(s)){
                //若是(，直接入栈
                stack.push(s);
            }else if(")".equals(s)) {
                //若是)，匹配到栈中的(，过程中的所有符号添加到集合
                while (!stack.isEmpty() && !"(".equals(stack.peek())) {
                    result.add(stack.pop());
                }
                //将(从栈中移除
                stack.pop();
            }else {
                //若是符号，首先将栈中所有权重>=当前符号的添加到集合
                while (!stack.isEmpty() && Operation.getWeight(stack.peek()) >= Operation.getWeight(s)) {
                    result.add(stack.pop());
                }
                //当前符号入栈
                stack.add(s);
            }
        }
        //若是当前栈中还有符号，全部添加到集合中
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    //中缀表达式(字符串) => 中缀表达式(List集合)
    private static List<String> toInfixList(String infixExpr) {
        char[] chs = infixExpr.toCharArray();
        List<String> result = new ArrayList<>();
        for (int i = 0; i < chs.length;) {
            char ch = chs[i];
            //若是字符
            if (isOper(ch)) {
                result.add("" + ch);
                i++;
            }else {
                //若是数字(考虑多种情况)
                StringBuilder numStr = new StringBuilder();
                while (i < chs.length && !isOper(chs[i])) {
                    numStr.append(chs[i++]);
                }
                result.add(numStr.toString());
            }
        }
        return result;
    }

    private static boolean isOper(String str) {
        if (str.length() == 1 && (str.charAt(0) >= '0' && str.charAt(0) <= '9')) return false;
        return true;
    }

    private static boolean isOper(char ch) {
        if (ch >= '0' && ch <= '9') return false;
        return true;
    }

}

//运算符号权重
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    public static int getWeight(String expr) {
        if (expr == null) return 0;
        int val = 0;
        switch (expr) {
            case "+":
                val = ADD;
                break;
            case "-":
                val = SUB;
                break;
            case "*":
                val = MUL;
                break;
            case "/":
                val = DIV;
                break;
            default:
                break;
        }
        return val;
    }
}

接着我们来测试下其中的一些计算过程：

public class Calculator {
    public static void main(String[] args) {
        //测试三个转换
        test();
    }

    public static void test() {
        //中缀表达式
        //        String infixExpr = "1+((2+3)*4)-5";
        String infixExpr = "(1+5)*4+3*5";
        System.out.println("中缀表达式为：" + infixExpr);
        //中缀表达式(字符串) => 中缀表达式(List集合)
        List<String> infixList = toInfixList(infixExpr);
        System.out.println("中缀表达式（List集合）：" + infixList);
        //中缀表达式(List集合) => 后缀表达式(List集合)
        List<String> suffixList = infixToSuffixExpr(infixList);
        System.out.println("后缀表达式（List集合）：" + suffixList);
        //后缀表达式(List集合) => 根据后缀表达式求值
        Integer result = calculateSuffix(suffixList);
        System.out.println("最终值：" + result);
    }
}

2.2、封装计算接口（接2.1）

接着在上面的Calculator类中添加公共方法接口：

public class Calculator {
    
	/**
     * 对外暴露计算数学式子
     * @param expr 中缀表达式
     */
    public static int calculate(String expr) {
        //去除空字符串
        int index = 0;
        char[] chs = expr.toCharArray();
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (c != ' ') chs[index++] = c;
        }
        expr = new String(chs, 0, index);
        //中缀(字符串)=>中缀(集合)
        List<String> infixList = toInfixList(expr);
        //中缀表达式(List集合) => 后缀表达式(List集合)
        List<String> suffixList = infixToSuffixExpr(infixList);
        //后缀表达式(List集合) => 根据后缀表达式求值
        Integer result = calculateSuffix(suffixList);
        return result;
    }
	
    //...上面代码
}

测试代码：

class Test1{
    public static void main(String[] args) {
        //调用计算的接口方法
        System.out.println(Calculator.calculate("(1 + 5) * 4 + 3 * 5"));
    }
}

2.3、leetcode—150. 逆波兰表达式求值（中等）

题目链接：150. 逆波兰表达式求值

题解：实际上就是在2.1中的求后缀表达式

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (!isOper(token)) {
                stack.push(Integer.valueOf(token));
            }else if ("+".equals(token)) {
                stack.push(stack.pop() + stack.pop());
            }else if ("-".equals(token)) {
                stack.push(-stack.pop() + stack.pop());
            }else if ("*".equals(token)) {
                stack.push(stack.pop() * stack.pop());
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 / num2);
            }
        }
        return stack.pop();
    }

    public boolean isOper(String token) {
        if (token.length() == 1 && (token.charAt(0) < '0' || token.charAt(0) > '9')) return true;
        return false;
    }

}

参考资料

[1]. 中缀表达式转换为后缀表达式（Java）