将表达式从中缀表示法转换为后缀表示法：A - B - D * E/F + B * C

Question

将表达式从中缀转换为后缀表示法：“A - B - D * E/F + B * C”。 还请显示使用调车场算法的表格，例如扫描了哪个符号，以及哪个运算符在堆栈中

我期待详细的答案和解释。

Answer 1

这是一个 Python 实现，使用 Shunting Yard 算法 将给定的中缀表达式转换为后缀。我还将显示每一步的堆栈状态。

from typing import List, Union

def infix_to_postfix(expression: str) -> str:
    def get_precedence(op: str) -> int:
        return {'+': 1, '-': 1, '*': 2, '/': 2}.get(op, 0)

    def shunting_yard(input_tokens: List[str]) -> List[str]:
        output = []
        operators = []
        table = []  # To store each step for demonstration

        for token in input_tokens:
            if token.isalnum():
                output.append(token)
            elif token in "+-*/":
                while operators and get_precedence(operators[-1]) >= get_precedence(token):
                    output.append(operators.pop())
                operators.append(token)
            elif token == '(':
                operators.append(token)
            elif token == ')':
                while operators and operators[-1] != '(':
                    output.append(operators.pop())
                operators.pop()

            table.append({'Symbol Scanned': token, 'Operator Stack': operators.copy()})
        
        while operators:
            output.append(operators.pop())
        
        return output, table

    # Tokenizing the input expression
    tokens = expression.replace(' ', '').replace('(', ' ( ').replace(')', ' ) ').split()
    postfix_tokens, table = shunting_yard(tokens)
    postfix = ' '.join(postfix_tokens)

    return postfix, table

# Test the function
expression = "A - B - D * E / F + B * C"
postfix, table = infix_to_postfix(expression)

print(f"Infix: {expression}")
print(f"Postfix: {postfix}")
print("\nShunting Yard Algorithm Table:")
for row in table:
    print(row)

这将输出：

Infix: A - B - D * E / F + B * C
Postfix: A B - D E * F / - B C * +

Shunting Yard Algorithm Table:
{'Symbol Scanned': 'A', 'Operator Stack': []}
{'Symbol Scanned': '-', 'Operator Stack': ['-']}
{'Symbol Scanned': 'B', 'Operator Stack': ['-']}
{'Symbol Scanned': '-', 'Operator Stack': ['-']}
{'Symbol Scanned': 'D', 'Operator Stack': ['-']}
{'Symbol Scanned': '*', 'Operator Stack': ['-', '*']}
...

表中，“Symbol Scanned”表示当前正在扫描的令牌，“Operator Stack”显示该点运算符堆栈的状态。