当前位置：首页 > 文章列表 > 文章 > python教程 > 后缀表达式递归解析方法全解

后缀表达式递归解析方法全解

2025-08-03 12:21:31 0浏览收藏

推广推荐

支持 PC / 移动端，安全直达

对于一个文章开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《后缀表达式递归解析方法详解》，主要介绍了，希望对大家的知识积累有所帮助，快点收藏起来吧，否则需要时就找不到了！

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

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

问题分析

提供的代码尝试使用递归下降解析器来解析后缀表达式。然而，在 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()

关键修改：