文章目录
- 前言
- 一、认识前缀、中缀、后缀表达式
- 二、中缀表达式求值
- 2.1、中缀转后缀计算（Java题解）
- 2.2、封装计算接口（接2.1）
- 2.3、leetcode—150. 逆波兰表达式求值（中等）
- 参考资料
前言
所有博客文件目录索引：博客目录索引(持续更新)
一、认识前缀、中缀、后缀表达式
在现实生活中我们计算的数学公式表达式就是中缀表达式，例如：(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;
}
}