# Infix to postfix implementation using a stack

I have implemented a "infix-to-postfix" function that takes as input a list representing the parsed expression, resulted from applying a certain regular expression to an expression, and I would like to have your opinion regarding its correctness and efficiency. Good suggestions are of course more than well-accepted!

For making you able also to test directly my algorithm, I decided to include also the regular expression and other important details.

import re

# higher number => higher precedence
OPERATORS  = {
"+": 1,
"-": 1,
"*": 2,
"/": 2,
"%": 2,
"^": 3
}

PARENTHESIS = set(["(", ")"])

REGEX = "(\d+|\w+|[()\-+*/^%])"

def parse(e):
"""Parses a string expression e to a infix represation list."""
return re.findall(REGEX, e)

def infix_to_postfix(infix):
stack = []
postfix = []

for c in infix:
if c in OPERATORS:

if len(stack) > 0:
top = stack[-1]

if top in OPERATORS.keys():
if OPERATORS[c] > OPERATORS[top]:
stack.append(c)
else:
while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
op = stack.pop()
postfix.append(op)

if len(stack) > 0:
top = stack[-1]
else:
break
stack.append(c)
else:
stack.append(c)
else:
stack.append(c)

elif c in PARENTHESIS:

if c == ")":
if len(stack) > 0:
top = stack[-1]

while top != "(":
try:
# pop throws an IndexError if the list is empty
r = stack.pop()
postfix.append(r)  # Adding what's in between ( ) to the postfix list
top = stack[-1]
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes ( from the top of the stack
else:
raise ValueError("')' cannot be added to the stack if it is empty")
else:
stack.append(c)  # c == '('
else:

postfix.append(c)

#print("Stack:", stack)
#print("Postfix:", postfix)

while len(stack) > 0:
top = stack.pop()

if top in OPERATORS.keys():
postfix.append(top)

return postfix


Please, don't tell me anything about the docstrings, because I actually removed them from my code to make it clearer.

In general, I prefer efficiency to clarity, so I am not so interested in list or generator comprehensions if they don't make the code more efficient. Anyway, you could also suggest them, if you feel that they would turn the code more "pythonic".

## 2 Answers

The first thing I notice is the deep nesting in infix_to_postfix. Deep nesting like that is generally undesirable. We'll get to that later.

Second, for the parenthesis, my instinct would be to say: "Use frozenset instead of set.". But after some benchmarking: set is actually fastest on my machine, so probably also on yours. (I also checked using a tuple instead, again slower than using a set). However, a more Pythonic declaration of the set would be PARENTHESIS = {"(", ")"}.

Regarding the regular expression and the method parse: it could be faster by using a compiled regex instead of using re.findall. Also, convention has it that you use raw strings for regular expressions.

REGEX = re.compile(r"(\d+|\w+|[-+*/^%()])")
def parse(e, REGEX=REGEX):
return REGEX.findall(e)


The REGEX=REGEX trick is an optimization trick preventing a lookup to the global dictionary. Using compiled regular expressions also gains a bit of speed. (On the other hand: I don't see parse being used, so that's probably ok).

Since it's not documented, I'm going to assume the calling convention will be

postfix_tokens = infix_to_postfix(parse(infix_tokens)


Now, let's start analysing the large method infix_to_postfix. First of all, we could apply the same trick as we did for REGEX to speed up the lookup for OPERATORS. That's going to make your code a bit more efficient.

It's a tad large, so let's first talk about the if c in OPERATORS branch.

if len(stack) > 0:
top = stack[-1]

if top in OPERATORS.keys():
if OPERATORS[c] > OPERATORS[top]:
stack.append(c)
else:
while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
op = stack.pop()
postfix.append(op)

if len(stack) > 0:
top = stack[-1]
else:
break
stack.append(c)
else:
stack.append(c)
else:
stack.append(c)


All these else conditions look the same. Let's see if we can simplify it a bit. Let's start by flipping the if and else branch in if OPERATORS[c] > OPERATORS[top]. (> becomes <=).

if len(stack) > 0:
top = stack[-1]

if top in OPERATORS.keys():
if OPERATORS[c] <= OPERATORS[top]:
while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
op = stack.pop()
postfix.append(op)

if len(stack) > 0:
top = stack[-1]
else:
break
stack.append(c)
else:
stack.append(c)
else:
stack.append(c)
else:
stack.append(c)


Now, we have the following construct:

if cond:
A()
B()
else:
B()


Which we can rewrite to

if cond:
A()
B()


Applying that several times we get

if len(stack) > 0:
top = stack[-1]

if top in OPERATORS.keys():
if OPERATORS[c] <= OPERATORS[top]:
while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
op = stack.pop()
postfix.append(op)

if len(stack) > 0:
top = stack[-1]
else:
break

stack.append(c)


Wow, we saved a few lines of code. If we're lucky, it's also going to gain us some performance.

Next, you have top in OPERATORS.keys(). This can be replaced by top in OPERATORS (as that's how dict containment checking works). Furthermore, len(stack) > 0 can be replaced by stack.

Furthermore, you write op = stack.pop() followed by postfix.append(op). You can simplify this to postfix.append(stack.pop()).

if stack:
top = stack[-1]

if top in OPERATORS:
if OPERATORS[c] <= OPERATORS[top]:
while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
postfix.append(stack.pop())

if stack > 0:
top = stack[-1]
else:
break

stack.append(c)


Let's continue our focus on the nested if top in OPERATORS. Now, for symmetry, we replace OPERATORS[c] <= OPERATORS[top] with OPERATORS[TOP] >= OPERATORS[C]. (I'm not showing the if stack: and stack.append(c) anymore).

if top in OPERATORS:
if OPERATORS[top] >= OPERATORS[c]:
while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
postfix.append(stack.pop())

if stack > 0:
top = stack[-1]
else:
break


We can merge the first two conditionals, because there are no else branches, using

if cond_a:
if cond_b:
...


to

if cond_a and cond_b:
...


We get

if top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
postfix.append(stack.pop())

if stack > 0:
top = stack[-1]
else:
break


Now the similarity should be obvious, we can drop the if.

Zooming out again:

def infix_to_postfix(infix):
stack = []
postfix = []

for c in infix:
if c in OPERATORS:

if stack:
top = stack[-1]

while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
postfix.append(stack.pop())

if stack:
top = stack[-1]
else:
break

stack.append(c)

elif c in PARENTHESIS:

if c == ")":
if len(stack) > 0:
top = stack[-1]

while top != "(":
try:
# pop throws an IndexError if the list is empty
r = stack.pop()
postfix.append(r)  # Adding what's in between ( ) to the postfix list
top = stack[-1]
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes ( from the top of the stack
else:
raise ValueError("')' cannot be added to the stack if it is empty")
else:
stack.append(c)  # c == '('
else:

postfix.append(c)

#print("Stack:", stack)
#print("Postfix:", postfix)

while len(stack) > 0:
top = stack.pop()

if top in OPERATORS.keys():
postfix.append(top)

return postfix


The first branch of the conditional is cleaned up nicely. Let's consider the second branch, most specifically the handling of ")".

You're checking if len(stack) > 0, and throwing a ValueError otherwise because of an empty stack. What you actually mean is "')' cannot be added to the stack if there is no '(' in the stack". That's already checked by the other branch, so this condition is superfluous. However, we can't just remove it just yet, because top = stack[-1] might then throw an IndexError. So, let's continue and see if we get another opportunity to fix it later.

In the while loop, we see a try/except. The except has a raise, so we might as well move it outside the loop. (I took the liberty to also remove the temporary variable r).

top = stack[-1]
try:
while top != "(":
postfix.append(stack.pop())
top = stack[-1]
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes the ( from the top of the stack


Looking at efficiency: you're storing stack[-1] in a temporary variable, and then loading it again for the while condition. We can fix that

try:
while stack[-1] != "(":
postfix.append(stack.pop())
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes the ( from the top of the stack


Remember the if we wanted to remove? We can actually do that now!

        ...
elif c in PARENTHESIS:

if c == ")":
try:
while stack[-1] != "(":
postfix.append(stack.pop())
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes ( from the top of the stack
else:
stack.append(c)  # c == '('
else:
...


The code is now shaping up nicely. Let's consider the final while loop. Here you're poping until it's empty. Why not just loop over it in reverse? (The stack is going to be destructed anyway). Iteration is probably cheaper than mutation.

    for token in reversed(stack):
if token in OPERATORS.keys():
postfix.append(token)


In fact, it would probably be more efficient to use a generator comprehension here.

     postfix.extend(token for token in reversed(stack) if token in OPERATORS)


In the end, we end up with

def infix_to_postfix(infix):
stack = []
postfix = []

for c in infix:
if c in OPERATORS:

if stack:
top = stack[-1]

while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
postfix.append(stack.pop())

if stack:
top = stack[-1]
else:
break

stack.append(c)

elif c in PARENTHESIS:

if c == ")":
try:
while stack[-1] != "(":
postfix.append(stack.pop())
except IndexError:
raise ValueError("'(' not found when popping")

stack.pop()  # Removes ( from the top of the stack
else:
stack.append(c)  # c == '('
else:

postfix.append(c)

#print("Stack:", stack)
#print("Postfix:", postfix)

postfix.extend(token for token in reversed(stack) if token in OPERATORS)

return postfix


And we can probably shave some extra lines off it even more, but I don't think that's necessary because now it is a bit more understandable.

As for the points @GarethRees mentioned: those should also be taken care of, as it does not make much sense like this. Probably best to ask for a new code-review after you made these changes.

• I forgot: a good thing to look up is the Shunting Yard algorithm by Edsger W. Dijkstra. – Sjoerd Job Postmus Jan 16 '16 at 21:15

This code doesn't detect syntax errors in the expression. It accepts two numbers with no operator:

>>> infix_to_postfix(['1', '2'])
['1', '2']


It accepts two operators with no number:

>>> infix_to_postfix(['+', '*'])
['*', '+']


It accepts unbalanced parentheses:

>>> infix_to_postfix(['(', '('])
[]


These cases should all be rejected as syntax errors.