Evaluating an infix expression python

问题:

My task is to evaluate a fully parenthesized infix expression using a stack. A Stack class has been written for me and I must not change or modify the Stack class.

Here are the step by step directions for how to evaluate the infix expression:

Just scan the expression from left to right. If it is anything other than a ), push it onto the stack. When you encounter a ), pop from the stack 4 times, do the math and push the value onto the stack. At the end you will have just one value in the stack and that will be the answer.

Here is that code:

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"

Here is my code so far:

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

Here is an example of my code running:

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'

回答1:

I think the problem is that you did't decide what you wan't to put on your stack. Are there number or strings ? I don't think it is the best solution (you are clearly doing some class assignment and I don't want to give you the solution), but if you decide to put only strings then, you just have to replace:

xStack.push(evaluation)

by

xStack.push(str(evaluation))

But as already said in the commentary, you should probably not use eval and put integers and operators on the stack.

回答2:

The issue is that in your code, the two sets of '9+9' are evaluated as strings in eval, then put back into the stack as integers. (see below)

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

Therefore, in the line of code:

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

it tries to concatenate two integers (18 and 18) and a string ('+'), creating an error as these are incompatible types. If you changed this line to:

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

Therefore forcing everything to be one type, string, it should work fine.

回答3:

I hope this would help to you

see the gist