评估中缀表达式python

Question

我的任务是使用堆栈评估一个完全带括号的中缀表达式。 Stack类已经为我编写了，我不能修改或修改Stack类。

下面是如何评价中缀表达式一步一步的方向：

只需扫描表达由左到右。如果它不是a），请将其推入堆栈。 当您遇到a）时，从堆栈中弹出4次，执行数学运算并将值推入堆栈。 最后你会在堆栈中有一个值，这将是答案。

这里是代码：

class Stack: 

    def __init__(self): 
     self.theStack=[] 

    def top(self): 

     if self.isEmpty(): 
      return "Empty Stack" 
     else: 
      return self.theStack[-1] 

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

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

    def pop(self): 
     if not self.isEmpty(): 
      temp=self.theStack[-1] 
      del(self.theStack[-1]) 
      return temp 

     else: 
      return "Empty Stack" 

这是到目前为止我的代码：

def evaluateInfix(Input): 

    xStack=Stack() 

    for n in Input: 
     if n!=")": 
      print "Pushing %s into the stack" %n 
      xStack.push(n) 

     if n==")": 
      math=xStack.pop()+xStack.pop()+xStack.pop() 

      last=xStack.pop() 

      for j in math: 

       print " Popping %s from stack" %j 

      print " Popping %s from stack" %last 

      evaluation=eval(math) 

      xStack.push(evaluation) 

      print "Pushing %d into stack" %evaluation 

这里是我的代码运行的例子：我觉得这个问题

Enter a fully parenthesized expression that has non-negative integer operands and using   only + - * and () 
Please enter the expression: ((9+9)+(9+9)) 
Pushing (into the stack 
Pushing (into the stack 
Pushing 9 into the stack 
Pushing + into the stack 
Pushing 9 into the stack 
    Popping 9 from stack 
    Popping + from stack 
    Popping 9 from stack 
    Popping (from stack 
    Pushing 18 into stack 
Pushing + into the stack 
Pushing (into the stack 
Pushing 9 into the stack 
Pushing + into the stack 
Pushing 9 into the stack 
    Popping 9 from stack 
    Popping + from stack 
    Popping 9 from stack 
    Popping (from stack 
Pushing 18 into stack 
Traceback (most recent call last): 
    File "project2.py", line 252, in <module> 
    main() 
    File "project2.py", line 246, in main 
    Infix=evaluateInfix(Input) 
    File "project2.py", line 164, in evaluateInfix 
    math=xStack.pop()+xStack.pop()+xStack.pop() 
TypeError: unsupported operand type(s) for +: 'int' and 'str' 

Answer 1

是你没有决定你想要放在你的堆栈上。有数字或字符串吗？我不认为这是最好的解决方案（你很明显正在做一些班级任务，我不想给你解决方案），但是如果你决定只输入字符串，那么你只需要替换：

xStack.push(evaluation) 

通过

xStack.push(str(evaluation)) 

但前面已经说过的评论，你可能不应该使用eval，并把整数和运营商在堆栈中。

Answer 2

的问题是，在你的代码，这两套“9 + 9”的作为在EVAL字符串进行评估，然后放回堆栈整数。 （见下文）

theStack=['(', 18, '+', 18] 

因此，在代码行：

math=xStack.pop()+xStack.pop()+xStack.pop() 

它试图连接两个整数（18和18）和一个串（ '+'），创建一个错误这些是不兼容的类型。 如果你改变了这一行：

math=str(xStack.pop())+str(xStack.pop())+str(xStack.pop()) 

因此迫使一切是一个类型，字符串，它应该工作的罚款。

Answer 3

我希望这将有助于你

see the gist