算术表达式求值法（表达式求值）之前序表示法求值

概念

前序表示法，也称为前缀表示法或波兰表示法（Polish notation），是一种用于表示数学表达式和算术运算的方法。这种表示法的特点是将运算符置于操作数之前，而不是像传统的中缀表示法（例如，2 + 3）将运算符置于操作数之间。前序表示法具有一些优点，尤其在计算机科学和计算器设计中非常有用。下面详细解释前序表示法的特点和优点：

1. 运算符在前：在前序表示法中，运算符出现在操作数之前。例如，加法操作符“+”写在两个操作数之前，如+ 2 3。这种顺序让解析器或计算机可以更容易地理解和处理表达式，因为它不需要像中缀表示法那样考虑运算符的优先级和括号的嵌套。

2. 没有括号：前序表示法不需要括号来明确指定运算的顺序，因为运算符的位置已经清晰地表明了运算的顺序。这减少了编写和解析表达式时的复杂性，并避免了由于错误的括号使用而导致的问题。

3. 一致性：前序表示法在整个表达式中保持了一致的结构，每个运算符都紧随在其操作数之前。这种一致性有助于编写计算机程序来处理这种类型的表达式，因为解析过程可以更容易地建立递归结构。

4. 简化计算：前序表示法使得计算机程序可以使用堆栈（stack）数据结构来轻松地执行计算。解析器可以按顺序读取表达式中的符号，将操作数推入堆栈，并在遇到运算符时从堆栈中弹出操作数执行计算。这种方法非常高效，尤其对于计算器和编程语言中的表达式求值非常有用。

5. 避免二义性：前序表示法消除了中缀表示法中由于运算符优先级和括号嵌套而导致的二义性。每个操作符都有一个明确定义的位置，使得表达式的含义变得清晰。

虽然前序表示法在计算机科学和计算器设计中有一些优点，但它在人类用户之间的广泛使用相对较少，因为它需要人们更多地适应非传统的表达方式。然而，它在某些领域，如计算机编程、逆波兰表示法的计算器和某些计算机科学应用中非常有用。

python示例

 1 def evaluate_prefix(expression):
 2     stack = []  # 创建一个空栈用于辅助计算
 3 
 4     # 遍历表达式的每个元素（从右到左）第1个元素是4，第2个是2，第3个是3，第4个*，第5个+
 5     for element in reversed(expression):  # 通过reversed函数让列表反序
 6         if element.isdigit() or (element[0] == '-' and element[1:].isdigit()):
 7             # 如果元素是数字或负数，将其转换为整数并入栈
 8             stack.append(int(element))
 9         else:
10             # 如果元素是运算符，则从栈中弹出两个操作数进行计算
11             operand1 = stack.pop()
12             operand2 = stack.pop()
13 
14             if element == '+':
15                 result = operand1 + operand2
16             elif element == '-':
17                 result = operand1 - operand2
18             elif element == '*':
19                 result = operand1 * operand2
20             elif element == '/':
21                 result = operand1 / operand2
22 
23             # 将计算结果入栈
24             stack.append(result)
25 
26     # 最终栈中剩下的元素就是表达式的计算结果
27     return stack[0]
28 
29 
30 expression = ['+', '*', '3', '2', '4']  # 对应表达式为 3 * 2 + 4
31 result = evaluate_prefix(expression)
32 print("表达式结果:", result)  # 10

中序表示法转前序表示法

 1 def infix_to_prefix(expression):
 2     # 定义操作符优先级，数字越大越优先
 3     precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
 4     operators = "+-*/^"
 5     stack = []
 6     output = []  # 结果
 7 
 8     # 判断是否是操纵符
 9     def is_operator(char):
10         return char in operators
11 
12     # 判断操作符的优先级
13     def has_higher_precedence(op1, op2):
14         return precedence[op1] > precedence[op2]
15 
16     for char in reversed(expression):
17         if char.isalnum():
18             output.append(char)
19         elif char == ')':
20             stack.append(char)
21         elif char == '(':
22             while stack and stack[-1] != ')':
23                 output.append(stack.pop())
24             stack.pop()
25         elif is_operator(char):
26             # 当前字符没有栈顶字符优先大
27             while stack and stack[-1] != ')' and has_higher_precedence(stack[-1], char):
28                 output.append(stack.pop())
29             stack.append(char)
30 
31     while stack:
32         output.append(stack.pop())
33 
34     return ''.join(reversed(output))  # 顺序要反过来
35 
36 
37 # 测试
38 infix_expression = "2 + 3 * 4"
39 prefix_expression = infix_to_prefix(infix_expression)
40 print("前序表示法:", prefix_expression)  # 前序表示法: +2*34