一、概述
后缀表达式（也称为逆波兰表达式）是一种数学表达式的表示方法，其中操作符位于操作数的后面。这种表示法消除了括号，并且在计算机科学和计算中非常有用，因为它更容易计算和解析。
与中缀表达式（通常我们使用的数学表达式，例如"a * (b + c)"）不同，后缀表达式的运算符放在操作数之后，例如：“a b c + *”。后缀表达式的计算方法是从左到右遍历表达式，遇到操作数时将其压入栈，遇到操作符时从栈中弹出所需数量的操作数进行计算，然后将结果重新压入栈。这个过程一直持续到整个表达式处理完毕，最终栈中只剩下一个结果，即表达式的计算结果。
后缀表达式具有以下优点：
- 不需要括号，因此消除了歧义。
- 更容易计算，因为遵循一定的计算顺序。
- 适用于计算机的堆栈操作，因此在编译器和计算器中经常使用。
转换中缀表达式为后缀表达式需要使用算法，通常是栈数据结构。
二、后缀表达式的运算顺序
后缀表达式的运算顺序是从左到右遍历表达式，遇到操作数时将其压入栈，遇到操作符时从栈中弹出所需数量的操作数进行计算，然后将计算结果重新压入栈。这个过程一直持续到整个表达式处理完毕，最终栈中只剩下一个结果，即表达式的计算结果。
后缀表达式的运算顺序是非常直观的，它遵循从左到右的顺序。当计算后缀表达式时，按照以下规则：
- 从左到右扫描后缀表达式中的每个元素（操作数或操作符）。
- 如果遇到操作数，将其推入栈。
- 如果遇到操作符，从栈中弹出所需数量的操作数进行计算，然后将计算结果推回栈中。
- 重复这个过程，直到遍历完整个后缀表达式。
三、常规表达式转化为后缀表达式
- 创建两个栈，一个用于操作符（操作符栈），另一个用于输出后缀表达式（输出栈）。
- 从左到右遍历中缀表达式的每个元素。
- 如果是操作数，将其添加到输出栈。
- 如果是操作符：
- 如果操作符栈为空，直接将该操作符推入操作符栈。
否则，比较该操作符与操作符栈栈顶的操作符的优先级。如果当前操作符的优先级较高，将其推入操作符栈。
如果当前操作符的优先级较低或相等，从操作符栈中弹出并添加到输出栈，然后重复比较直到可以推入操作符栈。
如果遇到左括号"(“，直接推入操作符栈。
如果遇到右括号”)“，将操作符栈中的操作符弹出并添加到输出栈，直到遇到匹配的左括号”("。
最后，将操作符栈中的剩余操作符全部弹出并添加到输出栈。
完成遍历后，输出栈中的内容就是中缀表达式转化为后缀表达式的结果。
四、代码实现
/**
* 定义操作符的优先级
*/
private Map<String, Integer> opList =
Map.of("(",3,")",3,"*",2,"/",2,"+",1,"-",1);
public List<String> getPostExp(List<String> source) {
// 数字栈
Stack<String> dataStack = new Stack<>();
// 操作数栈
Stack<String> opStack = new Stack<>();
// 操作数集合
for (int i = 0; i < source.size(); i++) {
String d = source.get(i).trim();
// 操作符的操作
if (opList.containsKey(d)) {
operHandler(d,opStack,dataStack);
} else {
// 操作数直接入栈
dataStack.push(d);
}
}
// 操作数栈中的数据，到压入到栈中
while (!opStack.isEmpty()) {
dataStack.push(opStack.pop());
}
List<String> result = new ArrayList<>();
while (!dataStack.isEmpty()) {
String pop = dataStack.pop();
result.add(pop);
}
// 对数组进行翻转
return CollUtil.reverse(result);
}
/**
* 对操作数栈的操作
* @param d，当前操作符
* @param opStack 操作数栈
*/
private void operHandler(String d, Stack<String> opStack,Stack<String> dataStack) {
// 操作数栈为空
if (opStack.isEmpty()) {
opStack.push(d);
return;
}
// 如果遇到左括号"(“，直接推入操作符栈。
if (d.equals("(")) {
opStack.push(d);
return;
}
// 如果遇到右括号”)“，将操作符栈中的操作符弹出并添加到输出栈，直到遇到匹配的左括号”("。
if (d.equals(")")) {
while (!opStack.isEmpty()) {
String pop = opStack.pop();
// 不是左括号
if (!pop.equals("(")) {
dataStack.push(pop);
} else {
return;
}
}
}
// 操作数栈不为空
while (!opStack.isEmpty()) {
// 获取栈顶元素和优先级
String peek = opStack.peek();
Integer v = opList.get(peek);
// 获取当前元素优先级
Integer c = opList.get(d);
// 如果当前操作符的优先级较低或相等，且不为（），从操作符栈中弹出并添加到输出栈，然后重复比较直到可以推入操作符栈
if (c < v && v != 3) {
// 出栈
opStack.pop();
// 压入结果集栈
dataStack.push(peek);
} else {
// 操作符与操作符栈栈顶的操作符的优先级。如果当前操作符的优先级较高，将其推入操作符栈。
opStack.push(d);
break;
}
}
}
测试代码如下：
PostfixExpre postfixExpre = new PostfixExpre();
List<String> postExp = postfixExpre.getPostExp(
Arrays.asList("9", "+", "(" , "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"));
System.out.println(postExp);
输出如下：
[9, 3, 1, -, 3, *, 10, 2, /, +, +]
五、求后缀表示值
使用栈来实现
/****
* 计算后缀表达式的值
* @param source
* @return
*/
public double calcPostfixExpe(List<String> source) {
Stack<String> data = new Stack<>();
for (int i = 0; i < source.size(); i++) {
String s = source.get(i);
// 如果是操作数
if (opList.containsKey(s)) {
String d2 = data.pop();
String d1 = data.pop();
Double i1 = Double.valueOf(d1);
Double i2 = Double.valueOf(d2);
Double result = null;
switch (s) {
case "+":
result = i1 + i2;break;
case "-":
result = i1 - i2;break;
case "*":
result = i1 * i2;break;
case "/":
result = i1 / i2;break;
}
data.push(String.valueOf(result));
} else {
// 如果是操作数，进栈操作
data.push(s);
}
}
// 获取结果
String pop = data.pop();
return Double.valueOf(pop);
}
测试
PostfixExpre postfixExpre = new PostfixExpre();
List<String> postExp = postfixExpre.getPostExp(
Arrays.asList("9", "+", "(" , "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"));
System.out.println(postExp);
double v = postfixExpre.calcPostfixExpe(postExp);
System.out.println(v);
结果如下：
[9, 3, 1, -, 3, *, 10, 2, /, +, +]
20.0
作者：小希爸爸
来源：juejin.cn/post/7330583100059762697
来源：juejin.cn/post/7330583100059762697
