Python中的中缀到后缀转换

Question

我已经开始用Python解决数据结构问题。我正在实现中缀到后缀，但无法调试程序中的错误。我执行join操作的最后一个返回语句的输入类型是NONE。

当我开始调试时，我发现在这部分代码中，第一个push操作（for*）之后出现了问题。之后，当我对它执行pop（）时，它将不返回任何值，而不是返回*。有人能指出，这里有什么错吗？

    *else:
        while (not s.isEmpty()) and (prec[s.peek()] >= prec[token]):
            #print token
            outlst.append(s.pop())
            #print outlst

        s.push(token)
        print (s.peek())*

中缀到后缀转换：

from StackClass import StackClass

def infixtopostfix(infixexpr):

    s=StackClass()
    outlst=[]
    prec={}
    prec['/']=3
    prec['*']=3
    prec['+']=2
    prec['-']=2
    prec['(']=1
    oplst=['/','*','+','-']

    tokenlst=infixexpr.split()
    for token in tokenlst:
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
            outlst.append(token)

        elif token == '(':
            s.push(token)

        elif token == ')':
            topToken=s.pop()
            while topToken != '(':
                outlst.append(topToken)
                topToken=s.pop()
        else:
            while (not s.isEmpty()) and (prec[s.peek()] >= prec[token]):
                #print token
                outlst.append(s.pop())
                #print outlst

            s.push(token)
            print (s.peek())

    while not s.isEmpty():
        opToken=s.pop()
        outlst.append(opToken)
        #print outlst
    return outlst
    #return " ".join(outlst)

print (infixtopostfix("A * B + C * D"))

Answer 1

你的代码适合我，有我自己的堆栈实现。

我得到['A', 'B', '*', 'C', 'D', '*', '+']的输出。

我怀疑问题可能出在堆栈实现中。那是什么样子？

这是我的（我肯定是次优的！）以下内容：

class StackClass:

    def __init__(self, itemlist=[]):
        self.items = itemlist

    def isEmpty(self):
        if self.items == []:
            return True
        else:
            return False

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

    def pop(self):
        return self.items.pop()

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