利用栈实现简单表达式求值: (56-20)/(4+2) 解析

在计算机科学中，栈是一种常用的数据结构，可用于解决各种问题，包括表达式求值。本文将介绍如何使用栈来计算简单数学表达式的值，例如 (56-20)/(4+2)。

算法步骤

创建两个栈: 一个用于存储操作数，另一个用于存储操作符。2. 从左到右遍历表达式: - 如果遇到数字，则将其解析为操作数并压入操作数栈。 - 如果遇到操作符，则将其与操作符栈的栈顶元素进行比较： - 如果操作符栈为空或栈顶元素是左括号'('，则将当前操作符直接压入操作符栈。 - 如果当前操作符的优先级高于栈顶操作符，则将当前操作符压入操作符栈。 - 否则，弹出操作符栈栈顶元素，从操作数栈中弹出两个操作数进行运算，将运算结果压入操作数栈，然后将当前操作符压入操作符栈。 - 如果遇到左括号'(', 则将其直接压入操作符栈。 - 如果遇到右括号')', 则从操作符栈中弹出操作符，从操作数栈中弹出两个操作数进行运算，将运算结果压入操作数栈，直到遇到左括号'('为止，并将左括号弹出丢弃。3. 表达式遍历完成后，操作数栈中剩下的唯一元素即为表达式的值。

Python 代码示例pythondef is_operator(char): return char in ['+', '-', '*', '/']

def calculate(op, num1, num2): if op == '+': return num1 + num2 elif op == '-': return num1 - num2 elif op == '*': return num1 * num2 elif op == '/': return num1 / num2

def evaluate_expression(expression): operand_stack = [] operator_stack = [] precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

for char in expression:        if char.isdigit():            operand_stack.append(int(char))        elif is_operator(char):            while (len(operator_stack) > 0 and                   is_operator(operator_stack[-1]) and                   precedence[char] <= precedence[operator_stack[-1]]):                operand2 = operand_stack.pop()                operand1 = operand_stack.pop()                operator = operator_stack.pop()                result = calculate(operator, operand1, operand2)                operand_stack.append(result)            operator_stack.append(char)        elif char == '(':            operator_stack.append(char)        elif char == ')':            while len(operator_stack) > 0 and operator_stack[-1] != '(':                operand2 = operand_stack.pop()                operand1 = operand_stack.pop()                operator = operator_stack.pop()                result = calculate(operator, operand1, operand2)                operand_stack.append(result)            if len(operator_stack) > 0 and operator_stack[-1] == '(':                operator_stack.pop()

while len(operator_stack) > 0:        operand2 = operand_stack.pop()        operand1 = operand_stack.pop()        operator = operator_stack.pop()        result = calculate(operator, operand1, operand2)        operand_stack.append(result)

return operand_stack[-1]

expression = '(56-20)/(4+2)'result = evaluate_expression(expression)print(f'表达式 {expression} 的值为: {result}')

示例解析

在本例中，我们使用 Python 实现了一个栈来计算给定的简单表达式 (56-20)/(4+2)。is_operator 函数用于判断字符是否为操作符，calculate 函数用于执行运算，evaluate_expression 函数对表达式进行求值。通过调用 evaluate_expression 函数，我们可以获得给定表达式的值，即 6.0。

希望本文能够帮助你理解如何使用栈来计算简单数学表达式的值。