概念
后序表示法（Postfix Notation）又称为逆波兰表示法（Reverse Polish Notation，RPN），是一种用于表示数学表达式的方法，其中运算符位于它们的操作数之后。
这种表示法非常适合用栈来计算表达式的值，因为它消除了括号的需求，使计算机能够轻松地理解和求解表达式。
例如，表达式 "3 + 4" 在后序表示法中表示为 "3 4 +"。后序表示法对于计算表达式非常有用，因为它无需括
后序表示法的计算步骤
- 创建一个空栈，用于存储操作数。
- 从左到右遍历后序表达式中的每个元素。
- 如果遇到操作数（数字），将其推入栈中。
- 如果遇到操作符（+、-、*、/等），则从栈中弹出两个操作数，执行相应的操作，然后将结果推回栈中。
- 继续遍历表达式，重复步骤3和步骤4，直到处理完整个表达式。
- 最终，栈中将只剩下一个值，这个值就是表达式的结果。
示例
1 def evaluate_postfix(expression):
2 stack = [] # 用于存放操作数
3 operators = set(['+', '-', '*', '/'])
4
5 for token in expression.split():
6 if token not in operators:
7 # 如果是操作数，将其压入栈
8 stack.append(float(token))
9 else:
10 # 如果是操作符，弹出栈顶的两个操作数，并执行相应的操作
11 operand2 = stack.pop()
12 operand1 = stack.pop()
13
14 if token == '+':
15 result = operand1 + operand2
16 elif token == '-':
17 result = operand1 - operand2
18 elif token == '*':
19 result = operand1 * operand2
20 elif token == '/':
21 result = operand1 / operand2
22
23 # 将结果压入栈
24 stack.append(result)
25
26 # 最终栈中剩下的元素即为表达式的结果
27 return stack[0]
28
29
30 # 后续表示法表达式
31 expression = "3 4 + 2 * 7 /"
32 result = evaluate_postfix(expression)
33 print("后序表达式的结果:", result) # 后序表达式的结果: 2.0
输出结果：
后序表达式的结果: 2.0
最佳实践和注意事项
- 确保后序表达式的格式正确，每个元素之间使用空格分隔。
- 对于操作符，确保在计算之前检查栈是否有足够的操作数。
- 如果表达式中包含负数，可以使用单独的字符来表示，例如"5 -3 +"表示5 - (-3)。
- 考虑添加错误处理机制，以处理不合法的表达式或除零错误。
中序表示法转后续表示
1 # 中序表示法转后续表示法
2 def infix_to_postfix(infix_expression):
3 precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3} # value越大，key的优先级越大
4 output = [] # 输出列表
5 operator_stack = [] # 操作符栈
6
7 # 判断优先级:当前操作符与栈顶操作符
8 def has_higher_precedence(op1, op2):
9 return precedence[op1] >= precedence[op2]
10
11 for token in infix_expression.split():
12 if token.isnumeric():
13 output.append(token)
14 elif token in precedence:
15 while (operator_stack and operator_stack[-1] != '(' and
16 has_higher_precedence(operator_stack[-1], token)): # 栈顶优先级高，则出栈
17 output.append(operator_stack.pop())
18 operator_stack.append(token)
19 elif token == '(': # 直接入栈
20 operator_stack.append(token)
21 elif token == ')': # 直接出栈，一直到(
22 while operator_stack and operator_stack[-1] != '(':
23 output.append(operator_stack.pop())
24 if operator_stack and operator_stack[-1] == '(': # (出栈
25 operator_stack.pop()
26
27 while operator_stack: # 不为空，则出栈
28 output.append(operator_stack.pop())
29
30 return ' '.join(output) # 拼接后续表达式:其实操作数顺序从左向右排序，操作符的顺序是按照优先级来的。
31
32
33 # 中序表示法示例
34 infix_expression = "3 + 4 * ( 2 - 1 ) / 5"
35 postfix_expression = infix_to_postfix(infix_expression)
36 print("中序表达式:", infix_expression) # 中序表达式: 3 + 4 * ( 2 - 1 ) / 5
37 print("后序表达式:", postfix_expression) # 后序表达式: 3 4 2 1 - * 5 / +
定义了一个infix_to_postfix函数，它接受一个中序表达式作为输入并返回后序表达式。该函数使用了一个输出列表output和一个操作符栈operator_stack来完成转换。
主要思路是遍历中序表达式的每个元素，根据运算符的优先级和括号来决定操作符的入栈和出栈。具体步骤如下：
- 如果遇到操作数（数字），直接添加到输出列表中。
- 如果遇到操作符，根据其优先级和栈顶操作符的优先级来决定是否出栈，并将当前操作符入栈。
- 如果遇到左括号
(，直接入栈。 - 如果遇到右括号
)，将操作符栈中的操作符出栈直到遇到左括号，并将左括号出栈。 - 最后，将操作符栈中的剩余操作符全部出栈并添加到输出列表中。