### 中缀表达式转后缀表达式 中缀表达式是人们习惯使用的表达式形式，但由于操作符的优先级和括号的存在，编程实现其计算较为复杂。因此，通常会将中缀表达式转换为后缀表达式（也称为逆波兰表达式），以便更方便地进行计算。转换过程中，需要使用两个栈：一个用于存储操作符，另一个用于存储中间结果或最终的后缀表达式。 #### 转换步骤 1. 遇到数字时，直接将其添加到后缀表达式中。 2. 遇到左括号时，将其压入操作符栈。 3. 遇到操作符时，将其与操作符栈顶的操作符进行优先级比较。如果操作符栈为空，或者栈顶是左括号，则直接将当前操作符压入栈中；如果当前操作符的优先级高于栈顶操作符，则直接压入栈中；否则，将栈顶操作符弹出并添加到后缀表达式中，然后再次比较栈顶操作符的优先级，重复该过程，直到当前操作符可以压入栈中。 4. 遇到右括号时，将操作符栈中的操作符依次弹出并添加到后缀表达式中，直到遇到左括号为止。左括号不添加到后缀表达式中，而是从栈中弹出。 5. 当整个中缀表达式扫描结束后，将操作符栈中剩余的所有操作符依次弹出并添加到后缀表达式中。 #### 代码实现 以下是一个用 Python 实现的中缀表达式转后缀表达式的程序： ```python def infix_to_postfix(expression): precedence = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 } def higher_precedence(op1, op2): return precedence[op1] > precedence[op2] if op2 in precedence else False output = [] operators = [] for token in expression.split(): if token.isalnum(): output.append(token) elif token == '(': operators.append(token) elif token == ')': while operators and operators[-1] != '(': output.append(operators.pop()) operators.pop() # Remove '(' else: while operators and higher_precedence(operators[-1], token): output.append(operators.pop()) operators.append(token) while operators: output.append(operators.pop()) return ' '.join(output) # 示例输入 infix_expression = "1 - ( 2 - 3 * ( 4 - 6 / 3 ) * 2 )" postfix_expression = infix_to_postfix(infix_expression) print(postfix_expression) # 输出: 1 2 3 4 6 3 / - * 2 * - - ``` #### 代码说明 - `precedence` 字典定义了操作符的优先级。 - `higher_precedence` 函数用于比较两个操作符的优先级。 - `output` 列表用于存储后缀表达式。 - `operators` 栈用于存储操作符。 - 程序根据每个 token 的类型执行不同的操作：数字直接添加到 `output`，左括号压入栈，右括号弹出栈内操作符直到遇到左括号，操作符则与栈顶操作符比较优先级后处理。 #### 注意事项 - 输入的中缀表达式需要以空格分隔每个 token，例如 `"1 - ( 2 - 3 * ( 4 - 6 / 3 ) * 2 )"`。 - 操作符仅支持基本的四则运算（`+`, `-`, `*`, `/`）和幂运算（`^`），可以根据需要扩展。 ---