Python栈类异常：入栈'*'被转为'('问题排查求助

问题概述 #

实现自定义Stack类时，出现Push字符*后执行peek操作返回(的异常。输入表达式(10+2*1.5)*3时，生成的后缀表达式错误混入(，预期结果应为[10.0, 2.0, 1.5, '*', '+', 3.0, '*']。

相关代码实现 #

Stack类及核心函数 #

class Stack:
    def __init__(self):
        self.data = []
        self.top = -1
        self.max = 10

    def isFull(self):
        return self.top == (self.max-1)

    def isEmpty(self):
        return self.top == -1

    def push(self, input):
        if self.isFull():
            print(f"Push({input}) : Stack is full")
        else:
            self.top += 1
            self.data.append(input)

    def pop(self):
        if self.isEmpty():
            print("Pop : Stack is empty")
        else:
            temp = self.data[self.top]
            self.top -= 1
            return temp

    def peek(self):
        if self.isEmpty():
            print("Peek : Stack is empty")
        else:
            return self.data[self.top]
        
    def printStack(self):
        if self.isEmpty():
            print("Print : Stack is empty")
        else:
            print("Stack : ", end="")
            for i in range(0,self.top+1):
                print(self.data[i], end=" ")
            print()

def stringToList(input):
    input = input.replace(' ', '')
    result = []
    temp = ''
    i = 0
    while i < len(input):
        char = input[i]
        if char.isdigit() or char == '.':
            temp += str(char)
        else:
            if temp != "":
                result.append(float(temp))
                temp = ''
            if char == '*' and i + 1 < len(input) and input[i + 1] == '*' :
                result.append('**')
                i += 1
            else:
                result.append(char)
        i += 1
    if temp != "":
        result.append(float(temp))
    return result

def infixToPostfix(input):
    stack = Stack()
    result = []
    for i in input:
        print(f"i = '{i}'")
        if type(i) == float:
            result.append(i)
        elif i == '(':
            stack.push(i)
        elif i == ')':
            while not stack.isEmpty() and stack.peek() != '(':
                result.append(stack.pop())
            stack.pop()
        else:
            while not stack.isEmpty() and stack.peek() != '(' and priority(i) <= priority(stack.peek()):   
                result.append(stack.pop())
            stack.push(i)

            print(f"stack.peek() = '{stack.peek()}'")

        print(f"result = {result}")
        stack.printStack()
        print()

    while not stack.isEmpty():
        result.append(stack.pop())
    return result

def priority(char):
    if char == '+' or char == '-':
        return 1
    elif char == '*' or char == '/':
        return 2
    elif char == '**':
        return 3
    else:
        return -1

输入执行代码 #

input = input("expression : ")
postfix = infixToPostfix(stringToList(input))
print(f"postfix : {postfix}")

错误现象 #

输入(10+2*1.5)*3后，关键输出片段如下：

i = ')'
result = [10.0, 2.0, 1.5, '*', '+']       
Print : Stack is empty

i = '*'
stack.peek() = '('
result = [10.0, 2.0, 1.5, '*', '+']       
Stack : (

Push*后，peek返回(，最终后缀表达式错误包含(。

问题根源 #

自定义Stack类的pop方法实现错误：仅通过self.top -=1移动栈顶指针，未从self.data列表中移除对应元素。导致self.data中堆积了之前的栈元素（如(），后续Push新元素时，self.top从-1变为0，指向的是self.data中残留的旧元素(，而非新Push的*。

修复方案 #

修改Stack类的pop方法，同步移除self.data列表的最后一个元素：

def pop(self):
    if self.isEmpty():
        print("Pop : Stack is empty")
    else:
        temp = self.data.pop()  # 移除列表末尾元素，同步栈的实际内容
        self.top -= 1
        return temp

可选优化：去掉单独维护的self.top变量，直接用len(self.data)-1表示栈顶索引，避免指针与实际数据不同步的问题，简化实现：

class Stack:
    def __init__(self):
        self.data = []
        self.max = 10

    def isFull(self):
        return len(self.data) == self.max

    def isEmpty(self):
        return len(self.data) == 0

    def push(self, input):
        if self.isFull():
            print(f"Push({input}) : Stack is full")
        else:
            self.data.append(input)

    def pop(self):
        if self.isEmpty():
            print("Pop : Stack is empty")
        else:
            return self.data.pop()

    def peek(self):
        if self.isEmpty():
            print("Peek : Stack is empty")
        else:
            return self.data[-1]
        
    def printStack(self):
        if self.isEmpty():
            print("Print : Stack is empty")
        else:
            print("Stack : ", end="")
            print(" ".join(map(str, self.data)))

验证结果 #

修复后，输入(10+2*1.5)*3的关键输出变为：

i = '*'
stack.peek() = '*'
result = [10.0, 2.0, 1.5, '*', '+']       
Stack : *

最终生成的后缀表达式符合预期：[10.0, 2.0, 1.5, '*', '+', 3.0, '*']

内容的提问来源于stack exchange，提问作者Sanghyun Na