# RubyQuiz 148 - Postfix to Infix

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