I have been meaning for some time to tackle the RubyQuiz problems in Python.

The one from yesterday (#148) is quite interesting, taking postfix notated expressions and returning an infix version.

For example

2 3 5 +


goes to

2 * (3 + 5)


I spoilt it a bit by reading Reverse Polish Notation on Wikipedia, which gave away how to evaluate the postfix expressions.

Here is my python code to evaluate postfix expressions

ops = ["+","*","/","-"]

def evaluate(inputpfs):
numstack =[]
opstack = []
for i in inputpfs.split():
if i not in ops:
numstack.append(i)
else:
right = numstack.pop()
left = numstack.pop()
#print (left + i +  right)
numstack.append(str(eval(left + i +  right)))
assert len(numstack) == 1
return eval(numstack[0])


Then I realised all I needed to do was remove eval, add brackets and I would have what I needed.

def bracket(somestring):
return "(" + somestring + ")"

def post2infix(inputpfs):
numstack = []
opstack = []
resultstr = ""
for i in inputpfs.split():
if i not in ops:
numstack.append(i)
else:
right = numstack.pop()
left = numstack.pop()
newresult = " ".join([left, i, right])
newresult = bracket(newresult)
numstack.append(newresult)
return numstack[0]


Then only printing brackets when you must. If the operation is - or /; you always need them around the right hand expression, unless is is a plain number as they are not associative. If the operation is +, you never need them. If the operation is * then you need them if you have + or - in the right hand expression. Note that left is always a plain number as only the top element of the stack is a compound expression

def isnum (somestring):
return all([i not in somestring for i in ops])

def post2infixpp(inputpfs):
numstack = []
opstack = []
resultstr = ""
for i in inputpfs.split():
if i not in ops:
numstack.append(i)
else:
right = numstack.pop()
left = numstack.pop()
if not isnum(right):
#if (not all([i not in right for i in ops])):
if i in ["/", "-"]:
right = bracket(right)
elif i=="*" and ("-" in right or "+" in right):
right = bracket(right)
newresult = " ".join([left, i, right])
numstack.append(newresult)
return numstack[0]


A subtle bug means I could not do isnum inline (commented out, line 15 here), I had to add an auxiliary function. Though this way is more comprehensible, I cannot figure out why swapping lines 14 and 15 breaks the code.

Testing: I know I should have done a bit more error checking in the above functions, but here is the little test sequence I wrote.

eg1 = "2 3 +"
eg2 = "2 3 5 + *"
eg3 = "56 34 213.7 + * 678 -"
egs = [eg1,eg2,eg3]

for i in egs:
print "*********"
print i
print evaluate(i)
print post2infix(i)
print post2infixpp(i)
assert (#evaluate(i) ==
eval(post2infix(i)) ==
eval(post2infixpp(i))
)


I had to comment out the evaluate(i) part of the assertion as it failed on eg3 due to some sort of floating point rounding error. I will try and track down why tomorrow.

evaluate(eg3) == 13193.200000000001
eval(post2infixpp(eg3)) == eval(post2infix(eg3)) == 13193.199999999999


Get the file Here