Welcome, guest | Sign In | My Account | Store | Cart

Infix~Postfix (Python recipe) by Premshree Pillai
ActiveState Code (http://code.activestate.com/recipes/228915/)

Use this to convert an infix expression to postfix and vice-versa. You can also evaluate infix and postfix expressions.

Python, 205 lines
Download
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
##################################################################################
##
##	Author:		Premshree Pillai
##	Date:		14/07/03	
##	File Name:	infix-postfix.py
##	Description:	-Converts infix expressions to postfix and vice-versa
##			-You can also evaluate infix and postfix expressions
##	Website:	http://www.qiksearch.com
##
##################################################################################

def push_stack(stackArr,ele):
    stackArr.append(ele)

def pop_stack(stackArr):
    return stackArr.pop()

def isOperand(who):
    if(not(isOperator(who)) and (who != "(") and (who != ")")):
        return 1
    return 0

def isOperator(who):
    if(who == "+" or who == "-" or who == "*" or who == "/" or who == "^"):
        return 1
    return 0

def topStack(stackArr):
    return(stackArr[len(stackArr)-1])

def isEmpty(stackArr):
    if(len(stackArr) == 0):
        return 1
    return 0

def prcd(who):
    if(who == "^"):
	return(5)
    if((who == "*") or (who == "/")):
	return(4)
    if((who == "+") or (who == "-")):
	return(3)
    if(who == "("):
	return(2)
    if(who == ")"):
	return(1)

def ip(infixStr,postfixStr = [],retType = 0):
    postfixStr = []
    stackArr = []
    postfixPtr = 0
    tempStr = infixStr
    infixStr = []
    infixStr = strToTokens(tempStr)
    for x in infixStr:
	if(isOperand(x)):
            postfixStr.append(x)
            postfixPtr = postfixPtr+1
        if(isOperator(x)):
            if(x != "^"):
                while((not(isEmpty(stackArr))) and (prcd(x) <= prcd(topStack(stackArr)))):
                    postfixStr.append(topStack(stackArr))
                    pop_stack(stackArr)
                    postfixPtr = postfixPtr+1
            else:
                while((not(isEmpty(stackArr))) and (prcd(x) < prcd(topStack(stackArr)))):
                    postfixStr.append(topStack(stackArr))
                    pop_stack(stackArr)
                    postfixPtr = postfixPtr+1
            push_stack(stackArr,x)
        if(x == "("):
                push_stack(stackArr,x)                
        if(x == ")"):
            while(topStack(stackArr) != "("):
                postfixStr.append(pop_stack(stackArr))
                postfixPtr = postfixPtr+1
            pop_stack(stackArr)
            
    while(not(isEmpty(stackArr))):
        if(topStack(stackArr) == "("):
            pop_stack(stackArr)
        else:
            postfixStr.append(pop_stack(stackArr))

    returnVal = ''
    for x in postfixStr:
        returnVal += x

    if(retType == 0):
        return(returnVal)
    else:
        return(postfixStr)

def pi(postfixStr):
    stackArr = []
    tempStr = postfixStr
    postfixStr = []
    postfixStr = tempStr
    for x in postfixStr:
	if(isOperand(x)):
            push_stack(stackArr,x)
	else:
            temp = topStack(stackArr)
	    pop_stack(stackArr)
	    pushVal = '(' + topStack(stackArr) + x + temp + ')'
	    pop_stack(stackArr)
	    push_stack(stackArr,pushVal)
    return(topStack(stackArr))

def strToTokens(str):
    strArr = []
    strArr = str
    tempStr = ''	
    tokens = []
    tokens_index = 0
    count = 0
    for x in strArr:
        count = count+1
        if(isOperand(x)):
            tempStr += x
        if(isOperator(x) or x == ")" or x == "("):
            if(tempStr != ""):
                tokens.append(tempStr)
                tokens_index = tokens_index+1
            tempStr = ''
            tokens.append(x)
            tokens_index = tokens_index+1 
        if(count == len(strArr)):
            if(tempStr != ''):
                tokens.append(tempStr)
    return(tokens)

def PostfixSubEval(num1,num2,sym):
    num1,num2 = float(num1),float(num2)
    if(sym == "+"):
        returnVal = num1 + num2
    if(sym == "-"):
        returnVal = num1 - num2
    if(sym == "*"):
        returnVal = num1 * num2
    if(sym == "/"):
        returnVal = num1 / num2
    if(sym == "^"):
        returnVal = pow(num1,num2)
    return returnVal

def PostfixEval(postfixStr):
    temp = postfixStr
    postfixStr = []
    postfixStr = temp
    stackArr = []
    for x in postfixStr:
        if(isOperand(x)):
            push_stack(stackArr,x)
        else:
            temp = topStack(stackArr)
            pop_stack(stackArr)
            pushVal = PostfixSubEval(topStack(stackArr),temp,x)
            pop_stack(stackArr)
            push_stack(stackArr,pushVal)
    return(topStack(stackArr))

def InfixEval(infixStr):
    return PostfixEval(ip(infixStr,[],1))

def menu():
    def again():
        flag = raw_input('Continue (y/n)?')
        if flag not in ('y','n'):
            again()
        if(flag == 'y'):
            menu()
        if(flag == 'n'):
            exit

    print '\n############################'
    print '# Infix-Postfix Calculator #'
    print '############################'    
    print '\n(1) Infix to Postfix'
    print '(2) Postfix to Infix'
    print '(3) Evaluate Infix'
    print '(4) Evaluate Postfix'
    print '(5) Exit'
    opt = raw_input("Enter option (1/2/3/4/5): ")
    if opt in ('1','2','3','4','5'):
        if(opt == '1'):
            what = raw_input('\nEnter Infix String: ')
            print 'Postfix String: ', ip(what)
        if(opt == '2'):
            what = raw_input('\nEnter Postfix String: ')
            print 'Infix String: ', pi(what)
        if(opt == '3'):
            what = raw_input('\nEnter Infix String: ')
            print 'Infix Value: ', InfixEval(what)
        if(opt == '4'):
            what = raw_input('\nEnter Infix String: ')
            print 'Postfix Value: ', PostfixEval(what)
        if(opt == '5'):
            exit
        if(opt != '5'):
            again()
    else:
        menu()

menu()

This Python script is basically an implementation of converting an infix expression to postfix and vice-versa. Though, it may not be directly useful considering that you wouldn't actually use it to evaluate expressions, but the script illustrates the implementation of the algorithm; i.e. how expressions are actually evaluated.

Thus, the script would be useful in understanding the implementation of the algorithm.

References: * Infix to Postfix conversion algorithm: http://premshree.resource-locator.com/articles/cs/infix-postfix/index.htm * Postfix evaluation algorithm: http://premshree.resource-locator.com/articles/cs/postfix-evaluation/index.htm

Tags: algorithms

1 comment

aspn 19 years, 3 months ago  # | flag

Shortification. Boiling down to the essentials I get this from your script

prio = {'^':5, '*':4,'/':4,'+':3,'-':3,'(':2,')':1}

def topostfix(infix_src):
    postfix = list()
    stack = list()
    for x in shlex.shlex( infix_src ):
    if x.isdigit():
            postfix.append(x)
        if x in '+-*/^':
            while len( stack ) and prio[x] &lt;= prio[ stack[-1]]:
                postfix.append( stack.pop() )
            stack.append(x)
        if x == '(':
            stack.append(x)
        if x == ')':
            while stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()

    while len(stack):
        if(stack[-1] == "("):
            stack.pop()
        else:
            postfix.append( stack.pop() )

    return postfix

Your algorithm works so far, but not for expressions like -1-2 or 3*-1

any idea how to fix this?

Created by Premshree Pillai on Wed, 15 Oct 2003 (PSF)
◄ Python recipes (4591) ►
◄ Premshree Pillai's recipes (11) ►

Required Modules

  • (none specified)

Other Information and Tasks