本文旨在帮助开发者调试和修复后缀表达式（也称为逆波兰表示法）的解析器。通过分析一个存在问题的 Python 实现，我们将深入了解如何正确地进行词法分析、语法解析，并最终得到正确的计算结果。文章将提供修改后的代码示例，并详细解释了修正的思路和关键步骤，确保读者能够理解并应用到自己的项目中。
后缀表达式的解析需要特别注意运算符和操作数的处理顺序。在提供的原始代码中，parse_expression 函数存在逻辑错误，导致解析顺序不正确，从而产生错误的解析结果和计算结果。关键问题在于后缀表达式的解析是从左到右读取，遇到操作符时，需要将之前的两个操作数取出进行计算。原始代码中 right 和 left 的赋值顺序反了。
下面是修正后的代码：
import re
token_patterns = [
('OPERATOR', r'[+\-*/]'),
('NUMBER', r'\d+'),
('WHITESPACE', r'\s+'),
]
def tokenize(source_code):
tokens = []
source_code = source_code.strip()
while source_code:
matched = False
for token_type, pattern in token_patterns:
match = re.match(pattern, source_code)
if match:
value = match.group(0)
tokens.append((token_type, value))
source_code = source_code[len(value):].lstrip()
matched = True
break
if not matched:
raise ValueError(f"Invalid character in source code: {source_code[0]}")
return tokens
def parse_expression(tokens):
stack = []
for token_type, value in tokens:
if token_type == 'NUMBER':
stack.append(int(value))
elif token_type == 'OPERATOR':
if len(stack) < 2:
raise ValueError("Not enough operands for operator")
right = stack.pop()
left = stack.pop()
stack.append((value, left, right))
else:
raise ValueError(f"Unexpected token: {token_type}")
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack[0]
def evaluate_expression(expression):
if isinstance(expression, int):
return expression
elif isinstance(expression, tuple):
operator, left, right = expression
if operator == '+':
return evaluate_expression(left) + evaluate_expression(right)
elif operator == '-':
return evaluate_expression(left) - evaluate_expression(right)
elif operator == '*':
return evaluate_expression(left) * evaluate_expression(right)
elif operator == '/':
return evaluate_expression(left) / evaluate_expression(right)
else:
raise ValueError(f"Invalid expression: {expression}")
def main():
source_code = "2 3 4 * +"
tokens = tokenize(source_code)
parsed_expression = parse_expression(tokens)
print(f"Source code: {source_code}")
print(f"Parsed expression: {parsed_expression}")
result = evaluate_expression(parsed_expression)
print(f"Result: {result}")
if __name__ == "__main__":
main()主要修改说明：
- parse_expression 函数的实现： 使用栈来存储操作数，当遇到运算符时，从栈中弹出两个操作数，然后将运算结果压入栈中。这样确保了正确的计算顺序。
- 错误处理： 添加了对操作数不足和表达式无效情况的错误处理，使代码更加健壮。
- 移除递归： 原始代码使用递归的方式进行解析，这在处理复杂表达式时可能会导致栈溢出。修改后的代码使用循环和栈，避免了递归，提高了代码的效率和稳定性。
运行结果
Source code: 2 3 4 * +
Parsed expression: ('+', 2, ('*', 3, 4))
Result: 14总结
正确解析后缀表达式的关键在于理解其从左到右的计算顺序，并使用合适的数据结构（如栈）来存储操作数。通过仔细分析和调试，可以修复解析器中的逻辑错误，确保得到正确的计算结果。 此外，良好的错误处理机制能够提高代码的健壮性，使其能够应对各种异常情况。
