堆栈和评估后缀

Question

我想知道是否有人能帮助解决这个堆栈问题，主函数中有两个例子，答案应该是1024和4096，但是我会得到100和144个，这个问题必须在evaluate_postfix定义中，因为我知道Stack类在工作。

class Stack:
 def __init__(self):
     self.items = []

 def is_empty(self):
     return self.items == []

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

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

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

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


def evaluate_postfix(text):
     s = Stack()
     for element in text:
          plus = None
          if element.isdigit():
               s.push(int(element))
          elif element == '^':
               plus = s.pop() ** s.pop()
          elif element == "+":
               plus = s.pop() + s.pop()
          elif element == "-":
               plus = s.pop() - s.pop()
          elif element == "*":
               plus = s.pop() * s.pop()
          elif element == "/":
               plus = s.pop() / s.pop()
          if plus is not None:
               s.push(plus)
     return s.pop()



def main():
     print(evaluate_postfix(['2', '10', '^']))
     print(evaluate_postfix(['2', '4', '3', '*', '^']))

main()

Answer 1

您的pop是正确的元素，但顺序不对：

s.pop() ** s.pop()

一旦您的程序到达这一行，在第一个示例中，堆栈将如下所示：['2', '10']。它是pop的10，然后是2，然后将10提高到2的幂。相反，您可以使用：

right = s.pop()
left = s.pop()
left ** right

你会得到想要的答案，1024。同样的原则也适用于其他操作者。