数据结构例题及参考答案详解

本篇文章旨在为大家提供一些数据结构例题及参考答案，并且对其中涉及的概念和知识点进行详尽的解释。希望能对大家的数据结构学习有所帮助。

一、栈和队列

1. 栈的顺序存储结构

题目描述：使用栈实现表达式求值。

代码示例：

def calc(exp):
    nums = []
    operators = []
    for c in exp:
        if c.isdigit():
            nums.append(int(c))
        elif c == '+' or c == '-':
            while operators and operators[-1] != '(':
                operand2 = nums.pop()
                operand1 = nums.pop()
                operator = operators.pop()
                nums.append(evaluate(operand1, operator, operand2))
            operators.append(c)
        elif c == '*' or c == '/':
            while operators and operators[-1] in '*/':
                operand2 = nums.pop()
                operand1 = nums.pop()
                operator = operators.pop()
                nums.append(evaluate(operand1, operator, operand2))
            operators.append(c)
        elif c == '(':
            operators.append(c)
        elif c == ')':
            while operators[-1] != '(':
                operand2 = nums.pop()
                operand1 = nums.pop()
                operator = operators.pop()
                nums.append(evaluate(operand1, operator, operand2))
            operators.pop()
    while operators:
        operand2 = nums.pop()
        operand1 = nums.pop()
        operator = operators.pop()
        nums.append(evaluate(operand1, operator, operand2))
    return nums[0]


def evaluate(a, operator, b):
    if operator == '+':
        return a + b
    elif operator == '-':
        return a - b
    elif operator == '*':
        return a * b
    elif operator == '/':
        return a // b