实现对输入的中缀表达式、前缀表达式、后缀表达式分别求值

### 中缀表达式、前缀表达式和后缀表达式的求值 对于中缀表达式、前缀表达式以及后缀表达式的求值，可以采用不同的策略。针对每种类型的表达式，存在特定的方法来进行解析和计算。 #### 中缀表达式的求值 由于直接评估中缀表达式较为复杂，通常先将其转换成更容易处理的形式——如后缀表达式（也称为逆波兰表示），再进行求值。此过程涉及到了调度场算法的应用[^1]： ```python def infix_to_postfix(expression): precedence = {'+':1, '-':1, '*':2, '/':2} stack = [] # only pop when encounter an operator or end of expression output = [] tokens = expression.split() for token in tokens: if token.isnumeric(): output.append(token) elif token == '(': stack.append(token) elif token == ')': top_token = stack.pop() while top_token != '(': output += top_token, top_token = stack.pop() else: while (stack and stack[-1]]): output += stack.pop(), stack.append(token) while stack: output += stack.pop(), return " ".join(output) def evaluate_postfix(postfix_expr): operand_stack = [] for token in postfix_expr.split(): if token.isdigit(): operand_stack.append(int(token)) else: op2 = operand_stack.pop() op1 = operand_stack.pop() result = do_math(op1, op2, token) operand_stack.append(result) return operand_stack.pop() def do_math(operand1, operand2, operator): if operator == "*": return operand1 * operand2 elif operator == "/": return operand1 / operand2 elif operator == "+": return operand1 + operand2 else: return operand1 - operand2 infix_expression = '7 + 3 * (4 - 2)' postfix_expression = infix_to_postfix(infix_expression.replace(' ', '')) print(f'Postfix Expression: {postfix_expression}') result = evaluate_postfix(postfix_expression) print(f'Result: {result}') ``` 上述代码展示了如何通过Python实现从给定的中缀表达式`7 + 3 * (4 - 2)`转化为对应的后缀形式并最终得到其数值结果的过程。 #### 前缀表达式的求值 前缀表达式的求值可以通过递归的方式解决，在遇到操作数时压入栈内；当碰到运算符，则弹出相应数量的操作数执行对应运算，并把结果重新推回栈顶作为新的操作数继续参与后续可能存在的其他运算之中。 ```python def prefix_evaluation(prefix_exp_str): operators = set(['+', '-', '*', '/', '^']) stack = [] elements_list = prefix_exp_str.strip().split()[::-1] for element in elements_list: if element not in operators: try: stack.append(float(element)) except ValueError: raise ValueError("Invalid Prefix Expression") else: str1 = stack.pop() str2 = stack.pop() res = apply_operation(str1,str2,element) stack.append(res) return stack.pop() def apply_operation(a,b,operator): match operator: case '+': return a+b case '-': return b-a case '*': return a*b case '/': return b/a case '^': return pow(b,a) prefix_expression = "- + * 8 9 / 6 3" evaluated_result = prefix_evaluation(prefix_expression) print(f"The evaluated value is :{evaluated_result}") ``` 这段程序实现了从前缀字符串读取输入直到返回最后的结果整个流程[^2]。 #### 后缀表达式的求值 后缀表达式的求值相对简单得多，因为不需要考虑括号优先级等问题。只需要按照顺序扫描每一个token，若是数字就存入堆栈里等待进一步处理；一旦发现是算术符号就可以立即取出最近两次存储的数据做相应的四则运算并将所得答案再次放入堆栈顶部准备下一轮迭代使用。 ```python from collections import deque def evalRPN(tokens): operations = { "+": lambda a, b: a + b, "-": lambda a, b: b - a, "*": lambda a, b: a * b, "/": lambda a, b: int(b / a), } nums = deque([]) for i in range(len(tokens)): numOrOp = tokens[i] if numOrOp.lstrip('-').isdigit(): nums.appendleft(int(numOrOp)) else: operation = operations[numOrOp] firstNum = nums.popleft() secondNum = nums.popleft() newNumber = operation(firstNum,secondNum) nums.appendleft(newNumber) return nums[0] rpn_tokens = ["2", "1", "+", "3", "*"] evaluation_outcome = evalRPN(rpn_tokens) print(f"Evaluation outcome:{evaluation_outcome}") ``` 该片段提供了一个简洁明了的例子说明怎样利用队列结构高效地完成对逆波兰记法所描述公式的即时演算工作。