使用递归下降解析器正确解析后缀表达式-Python教程-PHP中文网

使用递归下降解析器正确解析后缀表达式

花韻仙語

发布： 2025-07-29 16:32:01

原创

777人浏览过

使用递归下降解析器正确解析后缀表达式

本文旨在帮助读者理解并解决在使用递归下降解析器解析后缀表达式时可能遇到的问题。我们将通过分析一个具体的错误案例，深入探讨问题的原因，并提供详细的修改方案，确保解析器能够正确处理后缀表达式，并返回预期的结果。此外，我们还将介绍如何构建表达式树，以便更好地理解和操作解析后的表达式。

问题分析

提供的代码尝试使用递归下降解析器来解析后缀表达式。然而，在 parse_expression 函数中，运算符的处理顺序是错误的。对于后缀表达式，正确的处理顺序应该是先解析右操作数，再解析左操作数。当前的实现中，right 和 left 的解析顺序颠倒了，导致解析结果错误。此外，parse_expression 从 tokens 列表中弹出元素，这会改变列表本身，导致后续的解析出错。

解决方案

要解决这个问题，需要调整 parse_expression 函数中操作数的解析顺序，并确保不修改原始的 tokens 列表。以下是修改后的代码：

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):
    def _parse(tokens, index):
        if index >= len(tokens):
            return None, index

        token_type, value = tokens[index]

        if token_type == 'NUMBER':
            return int(value), index + 1
        elif token_type == 'OPERATOR':
            if value in ('+', '-', '*', '/'):
                right, next_index = _parse(tokens, index + 1)
                if right is None:
                    return None, index
                left, next_index = _parse(tokens, next_index)
                if left is None:
                    return None, index
                return (value, left, right), next_index
            else:
                raise ValueError(f"Unexpected operator: {value}")
        else:
            raise ValueError(f"Unexpected token: {token_type}")

    parsed_expression, _ = _parse(tokens, 0)
    return parsed_expression


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()

登录后复制

关键修改：