概念
后序表示法（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来完成转换。
主要思路是遍历中序表达式的每个元素，根据运算符的优先级和括号来决定操作符的入栈和出栈。具体步骤如下：
- 如果遇到操作数（数字），直接添加到输出列表中。
- 如果遇到操作符，根据其优先级和栈顶操作符的优先级来决定是否出栈，并将当前操作符入栈。
- 如果遇到左括号
(，直接入栈。 - 如果遇到右括号
)，将操作符栈中的操作符出栈直到遇到左括号，并将左括号出栈。 - 最后，将操作符栈中的剩余操作符全部出栈并添加到输出列表中。