04.3 中缀转后缀
中缀表达式转后缀表达式与栈的妙用
1. 中缀表达式与后缀表达式
1.1 中缀表达式的特点
中缀表达式是日常最常见的数学表达形式，其中运算符位于两个操作数之间，例如：3 + 4 * 5。
1.2 后缀表达式的特点
后缀表达式是将运算符置于操作数之后的形式，例如：3 4 5 * +。
2. 中缀表达式转后缀表达式
2.1 转换规则
中缀表达式转后缀表达式的转换规则如下：
- 从左至右遍历中缀表达式的每个元素。
- 如果是操作数，直接输出到后缀表达式。
- 如果是运算符：
- 如果栈为空，或者栈顶元素是左括号 "("，直接将运算符压入栈。
- 如果运算符优先级高于栈顶运算符，直接将运算符压入栈。
- 否则，将栈顶运算符弹出并输出到后缀表达式，然后重复比较直到满足前两个条件。
- 如果是左括号 "("，将其压入栈。
- 如果是右括号 ")"，将栈中的运算符依次弹出并输出到后缀表达式，直到遇到左括号 "("。
1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压s2；
4) 遇到运算符时，比较其与s1栈顶运算符的优先级：1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5) 遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6) 重复步骤2至5，直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8) 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式2.2 转换实例
以中缀表达式 3 + 4 * 5 为例，转换过程如下：
1. 输入：3 + 4 * 5
2. 输出：3 4 5 * +3. 利用栈求值后缀表达式
3.1 求值规则
利用栈求值后缀表达式的规则如下：
- 从左至右遍历后缀表达式的每个元素。
- 如果是操作数，压入栈。
- 如果是运算符，从栈中弹出两个操作数，进行运算，并将结果压入栈。
3.2 求值实例
以后缀表达式 3 4 5 * + 为例，求值过程如下：
1. 输入：3 4 5 * +
2. 栈操作：
- 遇到 3，压入栈： [3]
- 遇到 4，压入栈： [3, 4]
- 遇到 5，压入栈： [3, 4, 5]
- 遇到 *，弹出 5 和 4，计算结果 20，压入栈： [3, 20]
- 遇到 +，弹出 20 和 3，计算结果 23，压入栈： [23]
3. 最终结果：234. 示例：Python 实现中缀转后缀与求值
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def size(self):
return len(self.items)
def infix_to_postfix(infix_expr):
stack = Stack()
postfix_expr = []
operators = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}
for token in infix_expr.split():
if token.isdigit():
postfix_expr.append(token)
elif token == '(':
stack.push(token)
elif token == ')':
while stack.peek() != '(':
postfix_expr.append(stack.pop())
stack.pop() # 弹出左括号
elif token in operators:
while stack.size()
> 0 and operators[token] <= operators.get(stack.peek(), 0):
postfix_expr.append(stack.pop())
stack.push(token)
while not stack.is_empty():
postfix_expr.append(stack.pop())
return ' '.join(postfix_expr)
def evaluate_postfix(postfix_expr):
stack = Stack()
operators = set(['+', '-', '*', '/'])
tokens = postfix_expr.split()
for token in tokens:
if token.isdigit():
stack.push(int(token))
elif token in operators:
operand2 = stack.pop()
operand1 = stack.pop()
if token == '+':
stack.push(operand1 + operand2)
elif token == '-':
stack.push(operand1 - operand2)
elif token == '*':
stack.push(operand1 * operand2)
elif token == '/':
stack.push(operand1 / operand2)
return stack.pop()
# 示例
infix_expression = "3 + 4 * 5"
postfix_expression = infix_to_postfix(infix_expression)
result = evaluate_postfix(postfix_expression)
print(f"中缀表达式：{infix_expression}")
print(f"后缀表达式：{postfix_expression}")
print(f"求值结果：{result}")4. 示例：Java 实现中缀转后缀与求值
package org.example;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;
import java.util.stream.Collectors;
public class PolandNotation {
// 1 + ( ( 2 + 3 )× 4) - 5转成中缀表达式，对字符串操作麻烦，所以先转成list
//操作list，转成后缀表达式
public static void main(String[] args) {
String expression = "1+((2+3)*4)-5";
System.out.println("中缀表达式是：" + toInfixExpressionList(expression));
System.out.println("后缀表达式是：" + parseSuffixExpressionList(toInfixExpressionList(expression)));
System.out.println("expression = " + calculate(parseSuffixExpressionList(toInfixExpressionList(expression))));
//定义逆波兰表达式（3+4）*5-6 3 4 + 5 * 6 -
String suffixExpression = "3 4 + 5 * 6 - ";
// suffixExpression放入arraylist中
// suffixExpression传递给一个方法，遍历ArrayList,配合栈，完成计算
List<String> rpnList = getListString(suffixExpression);
System.out.println("rpnlist = " + rpnList);
int res = calculate(rpnList);
System.out.println(res);
}
public static List<String> parseSuffixExpressionList(List<String> ls) {
Stack<String> s1 = new Stack<String>();
// Stack<String> s2 = new Stack<String>();//保存中间结果
List<String> s2 = new ArrayList<String>();
// 遍历ls,
for (String item : ls) {
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();//消除括号
} else {
//当item的运算符优先级小于等于s1栈顶运算符优先级，
//s1栈顶运算符弹栈 压入s2中，
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
s1.push(item);
}
}
// 将s1中剩余的运算符依次弹出并压入s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
public static List<String> toInfixExpressionList(String s) {
ArrayList<String> ls = new ArrayList<String>();
int i = 0;//用于遍历s
String str1;//对多位数进行拼接
char c;//每遍历一个字符就放入c
do {
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {//非数字
ls.add("" + c);
i++;
} else {
//是数字，考虑多位数，需要拼接
str1 = "";
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
//取出的仍然是数字
str1 += c;
i++;
}
ls.add(str1);
}
} while (i < s.length());
// for(String item :ls){
// if (item.equals(" ")){
// ls.remove(item);
// }
// }
// ls.removeIf(str -> str.isEmpty());
// ls.stream().map(s -> s.replaceAll("\n",",").trim()).collect(Collectors.toList());
// ls.stream().map(s1 -> s1.replaceAll("\n", ",").trim()).collect(Collectors.toList());
return ls;
}
//将逆波兰表达式，依次将数字和运算符放入Array List中
public static List<String> getListString(String suffixExpression) {
//分割suffixExpression
String[] s = suffixExpression.split(" ");
ArrayList<String> list = new ArrayList<>();
for (String ele : s) {
list.add(ele);
}
return list;
}
public static int calculate(List<String> ls) {
//创建一个栈
Stack<String> stack = new Stack<>();
// 遍历ls
for (String item : ls) {
// 正则表达式取数
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int res;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num2 - num1;
} else if (item.equals("*")) {
res = num2 * num1;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
stack.push(res + "");
}
}
return Integer.parseInt(stack.pop());
}
}
//返回运算符对应的优先级
class Operation {
public static int ADD = 1;
public static int SUB = 1;
public static int MUL = 2;
public static int DIV = 2;
public static int getValue(String operation) {
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
// throw new RuntimeException("不存在");
System.out.println("不存在");
break;
}
return result;
}
}5. 总结
通过栈的巧妙运用，可以高效地将中缀表达式转换为后缀表达式，并在后缀表达式上进行求值。这种方法简化了表达式的处理逻辑，使得程序更容易理解和实现。