算数表达式求值 栈吉林大学数据结构

对于算术表达式求值，可以采用栈的数据结构来实现。下面是一个基于栈的算术表达式求值的示例代码：

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)


def evaluate_expression(expression):
    operators = {
        '+': lambda x, y: x + y,
        '-': lambda x, y: x - y,
        '*': lambda x, y: x * y,
        '/': lambda x, y: x / y
    }

    operand_stack = Stack()
    operator_stack = Stack()

    for char in expression:
        if char.isdigit():
            operand_stack.push(int(char))
        elif char in operators:
            operator_stack.push(char)
        elif char == ')':
            second_operand = operand_stack.pop()
            first_operand = operand_stack.pop()
            operator = operator_stack.pop()
            result = operators[operator](first_operand, second_operand)
            operand_stack.push(result)

    return operand_stack.pop()


expression = "((2+3)*(5-4)/2)"
result = evaluate_expression(expression)
print(f"The result of {expression} is: {result}")

这段代码中，我们使用两个栈，一个存储操作数（operand_stack），一个存储操作符（operator_stack）。遍历表达式中的每个字符，如果是数字，则将其作为操作数压入操作数栈中；如果是操作符，则将其压入操作符栈中；如果是右括号，则从操作数栈和操作符栈分别弹出两个操作数和一个操作符，进行计算并将结果压入操作数栈中。

以上是一个基本的算术表达式求