应用栈实现四则运算

实现四则运算的应用栈可以使用后缀表达式来计算。步骤如下：

1. 将中缀表达式转换为后缀表达式，例如将 "3 + 4 * 2 / (1 - 5) ^ 2" 转换为 "3 4 2 * 1 5 - 2 ^ / +"
2. 创建一个栈来存储数字和运算符。
3. 从左到右扫描后缀表达式的每个元素，如果是数字则入栈，如果是运算符则取出栈顶的两个数字进行运算并将结果入栈。
4. 扫描完后缀表达式后，栈顶即为最终结果。

以下是一个简单的 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):
        if not self.is_empty():
            return self.items.pop()

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

def calculate_postfix(expression):
    stack = Stack()
    for token in expression:
        if token.isdigit():
            stack.push(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                result = operand1 + operand2
            elif token == '-':
                result = operand1 - operand2
            elif token == '*':
                result = operand1 * operand2
            elif token == '/':
                result = operand1 / operand2
            elif token == '^':
                result = operand1 ** operand2
            stack.push(result)
    return stack.pop()

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = Stack()
    postfix = []
    for token in expression:
        if token.isdigit():
            postfix.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.top() != '(':
                postfix.append(stack.pop())
            stack.pop()
        else:
            while not stack.is_empty() and stack.top() != '(' and precedence[stack.top()] >= precedence[token]:
                postfix.append(stack.pop())
            stack.push(token)
    while not stack.is_empty():
        postfix.append(stack.pop())
    return postfix

expression = "3 + 4 * 2 / (1 - 5) ^ 2"
postfix = infix_to_postfix(expression.split())
result = calculate_postfix(postfix)
print(result)  # 输出 -3.5