数据结构实现表达式求值

数据结构中栈可以用来实现表达式求值。具体实现方法如下：
1. 从左到右遍历中缀表达式，遇到数字直接入栈。
2. 遇到运算符，判断其与栈顶运算符的优先级，如果栈顶运算符优先级高于或等于该运算符，则取出栈顶运算符和两个数字进行运算，并将结果入栈；否则将该运算符入栈。
3. 当表达式遍历完后，依次取出栈中运算符和数字进行运算，直到栈为空，得到最终结果。

代码实现如下（Python）：

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):
        return self.items.pop()

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

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

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):
    operator_stack = Stack()
    operand_stack = Stack()
    priority = {'+': 1, '-': 1, '*': 2, '/': 2}

    for char in expression:
        if char.isdigit():
            operand_stack.push(int(char))
        elif char in priority:
            while not operator_stack.is_empty() and priority[char] <= priority[operator_stack.peek()]:
                op = operator_stack.pop()
                num2 = operand_stack.pop()
                num1 = operand_stack.pop()
                result = calculate(op, num1, num2)
                operand_stack.push(result)
            operator_stack.push(char)
        elif char == '(':
            operator_stack.push(char)
        elif char == ')':
            while operator_stack.peek() != '(':
                op = operator_stack.pop()
                num2 = operand_stack.pop()
                num1 = operand_stack.pop()
                result = calculate(op, num1, num2)
                operand_stack.push(result)
            operator_stack.pop()

    while not operator_stack.is_empty():
        op = operator_stack.pop()
        num2 = operand_stack.pop()
        num1 = operand_stack.pop()
        result = calculate(op, num1, num2)
        operand_stack.push(result)

    return operand_stack.pop()