Error creating postfix expression

Question

I am changing infix to postfix and then evaluating it.

#!/usr/bin/python

import sys
import fileinput
import operator

operator_functions = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': operator.div,
    '%': operator.mod
}

def tokenise( line ) :
    '''generator, serves up one token at a time
    input - a valid, openo file handle (object)
    output - next token (as a string)
    side-effects - input pointer is moved'''

    for tok in line.split() :
        yield tok

#Define types with corresponding ID numbers to distinguish them.
OPERATOR = 1
OPERAND = 2
LEFT_PARENTHESES = 3
RIGHT_PARENTHESES = 4

def precedence(s): #Returns the precedence of the operators
    if s == '(':
    return 3
elif s == '+' or s == '-':
    return 2
elif s == '*' or s == '/' or s == '%':
    return 1
else:
    return 0

def typeof(s): #Returns the type of the symbol
    if s == '(':
    return LEFT_PARENTHESES
elif s == ')':
    return RIGHT_PARENTHESES
elif s == '+' or s == '-' or s == '*' or s == '%' or s == '/':
    return OPERATOR  
else :
    return OPERAND                          

def infix2postfix(infix):
    postfix = []
    stack = []
    for i in infix:
        symbol_type = typeof(i)
        if symbol_type == LEFT_PARENTHESES :
            #If it is a left paren, push it onto the stack
            stack.append(i)
        elif symbol_type == RIGHT_PARENTHESES :
            #If it is a right paren, pop operators from the stack and append to the postfix expression,
            #until a left paren is encountered on the stack. Remove and discard the left paren                
            next = stack.pop()
            while next != '(':
                postfix.append(next)
                next = stack.pop()
        elif symbol_type == OPERAND:
            #If it is an operand, append it to the postfix expression
            postfix.append(i) 
        elif symbol_type == OPERATOR:
            #If it is an operator, then pop operators from the stack and append to the postfix expression
            #while the operators have equal or higher precedence than the current token. Push current
            #token (operator) onto the stack
            p = precedence(i)
            #print i
            while len(stack) != 0 and p <= precedence(stack[-1]) :
                print stack
                postfix.append(stack.pop())
            stack.append(i)

    while len(stack) > 0 : #Add to postfix
        postfix.append(stack.pop())
    evalPostfix(postfix) #Call evalPostFix to get result

def evalPostfix(postfix_expression):
    stack = []
    for token in postfix_expression :
        if token in operator_functions:
            no1 = int(stack.pop()) #First Number
            no2 = int(stack.pop()) #Second Number
            stack.append(operator_functions[token](no2, no1))
        else :
            stack.append(token)
    print ' '.join(postfix_expression),'=',stack.pop() #The Result

##########
#Main Code
##########
if len(sys.argv) == 2: #Read from file
    f = open( sys.argv[1] )
elif len(sys.argv) == 1: #Read from stdin
    f = sys.stdin
else:
    print 'Invalid Number of arguments. Supply either no arguments or an input file.'
    sys.exit(0)


lines = [line.strip() for line in f]

for i in lines:
    arr=[] #Array containing all infix expressions
    tokens = tokenise( i )
    for t in tokens :
        #print t
        arr.append(t)
    infix2postfix(arr) #Call infix2postfix

Input example: 1 + 2 - 3 Output example: 1 2 + 3 - = 0

That works as desired, but when I try this: Input: 13 + 23 - 42 * 2

I get Output: 13 23 + 42 - 2 * = -12

Instead of: 13 23 + 42 2 * - = -48

I am not sure what is going wrong. Any ideas?

And don't use `is` operator for comparing strings, use `==`. — Ashwini Chaudhary, Feb 20 '14 at 17:39
It's also worth noting that you could just use a `dict` for precedence and typeof... — Jon Clements, Feb 20 '14 at 17:44
you're right, i should use ==, but that doesnt change the functionality of the code. I am still not getting my desired output — JonStanley91, Feb 20 '14 at 17:53

score 1 · Answer 1 · answered Feb 20 '14 at 17:40

1

Use == instead of is operator , there is difference between is and ==, is check returns True when both objects are same == returns true if value are equal.

additionally, Condition:

s is '+' or '-':

Should be:

s == '+' or  s == '-':

Note an non-empty string is always true e.g.

>>> bool('')
False
>>> bool('+')
True

answered Feb 20 '14 at 17:40

Grijesh Chauhan

57,103
20
141
208

While I do agree with you and have made modifications, it does not change the fact that evaluating the expression does not work – JonStanley91 Feb 20 '14 at 17:49

Error creating postfix expression

1 Answers1