I wrote this originally some time ago. Mostly for my own amusement. It converts from infix to postfix notation.

I expect most of our readers know what these are but for the benefits of completeness infix is a functional notation we humans use for instance in mathematics where the operator sits in between the operands. Example:

`(8 * 5) / 4`

Postfix is a functional notation that machines like to use because it lacks the ambiguity of infix. Example:

`8 5 * 4 /`

As a machine reads this it sees term `8` and stores it. It sees term `5` and stores it. It sees operator `*` which it knows is a binary operator and uses the two stored terms and stores the value internally. It then sees `4` and stores that. It then sees `/` which is a binary operator and uses the stored value from the first operation with the last term `4` and applies the operation to get a result.

As a result of this approach postfix has no need of parenthesis to clarify the order of operations in an expression.

The following code makes use of the Shunting yard algorithm invented to convert infix to postfix by our good friend in computer science, Edsger Dijkstra.

The code is a little verbose so people can see what is going on. You can download this code at http://neverfear.org/files/view/65

```#!/usr/bin/python
# author: doug@neverfear.org
# date: 09/04/2007
# date: 02/03/2010: Cleaned code up a bit, added some syntactical checks.
#
# Implementation of infix to postfix conversation.
# based around the shunting yard algorithm
# see http://en.wikipedia.org/wiki/Shunting_yard_algorithm
#
# Long code because of all the verbose prints
#
# Example usage
# \$ ./infixtopostfix.py "(8 * 5) / 4"
#
# Ultra verbose usage with multiple expressions:
# \$ ./infixtopostfix.py -v -v -v "(8 * 5) / 4" "1+(42 +31)+1" "5+1"
#

import sys

formattingops    = ['(', ')']
associative      = ["*", "+"]
leftassociative  = ["-", "/"]
rightassociative = ["^"]
operators        = formattingops + associative + leftassociative + rightassociative
arithmeticops    = associative + leftassociative + rightassociative
precedence       = {} # high value == high precedence
precedence["^"]  = 3
precedence["+"]  = 1
precedence["-"]  = 1
precedence["*"]  = 2
precedence["/"]  = 2
precedence["%"]  = 3
precedence["("]  = 4
precedence[")"]  = 4

simplestack      = [] # ordered list

input            = [] # input list
verbose          = 0  # if 0 just output is printed
# if 1 just the summary is printed.
# if 2, token, output string, and stack are printed.
# if 3, verbose information is printed

def push(what):
simplestack.append(what)

def pop():
if len(simplestack):
return simplestack.pop(-1) # remove the last
return None

def peek():
if len(simplestack):
return simplestack[-1]
return None

def getprecedence(op):
if op == None:
return op
return precedence[op]

def stacktostring(stack):
if not stack:
return "Empty"
out = ""
for i in reversed(stack):
out = out + str(i) + " "
return out[:-1]

def beVerbose(level, text):
global verbose
if verbose >= level:
print text,

def concatsymbol(current, token):
return current + token

def infixtopostfix(input):
output = ""
lastwasspace = False
lasttoken = None
for token in input:

if not token.strip():
lastwasspace = True
continue

beVerbose(2, "Token='%c'" % (token))

if not token in operators:

if lastwasspace and not lasttoken in operators:
# Catch terms that were delimited by whitespace
# but then the next token is a non-operator
# Example string that would cause this "123 4+1"
# since this doesn't make sense.
print "ERROR: Unexpected token '%c'" % (token)
sys.exit(1)

output = output + token

lastwasspace = False

else: # operators

if lasttoken in arithmeticops and token in arithmeticops:
# Catch duplication of operators. An example would
# be "4 // 2" or "823 + - / 2" which makes no sense in infix.
# The only operators allowed next to one another are
# the formatting operators '(' and ')' used to group operations.
print "ERROR: Unexpected token '%c'" % (token)
sys.exit(1)

if token == '(':
push(token)

beVerbose(3, "pushed onto stack")

elif token == ')':
tok = pop()

beVerbose(3, "'%s' popped off stack" % (tok))

while tok != "(":
if tok == None: #stack is empty
print
print "ERROR: Parenthesis mismatch"
sys.exit(1)

output = output + " " + tok

tok = pop()

beVerbose(3, "'%s' popped off stack" % (tok))

else: # mathematical operators

tok = peek()

while tok and tok != '(':

beVerbose(3, "'%s' is on the top of the stack" % (tok))

if ((
(token in associative or token in leftassociative) and
(getprecedence(token) <= getprecedence(tok))
) or (
token in rightassociative and
getprecedence(token) < getprecedence(tok)
)):

tok = pop()
output = output + " " + tok

beVerbose(3, "'%s' popped off the stack and added to output" % (tok))

else:
break

tok = peek()

push(token)

beVerbose(3, "'%s' pushed onto stack" % (token))
output = output + " "

lastwasspace = False
lasttoken = token

if verbose == 2:
format = "Output=% -40s Stack: % -30s"
elif verbose >= 3:
format = "Output=%s Stack: %s" # no field justification
if verbose >= 2:
print format % (output, stacktostring(simplestack))

beVerbose(2, "Token=end")

tok = peek()

while tok:
if tok == "(":
print
print "ERROR: Parenthesis mismatch"
sys.exit(1)

tok = pop()

output = output + " " + tok

beVerbose(3, "%s popped and added to output" % (tok))

tok = peek()

if verbose >= 3:
print
if verbose >= 2:
print
if verbose >= 1:
print "Infix input =", input
print
print "Postfix output =", output

return output

if (len(sys.argv) < 2):
print "Please provide infix input string or use --help for help"
sys.exit(1)

# I should have really used getopts but I was young and naive when I wrote this!
for v in sys.argv[1:]:
if v == "-v" or v == "--verbose":
verbose = verbose + 1
elif v == "-h" or v == "--help":
print "usage: infixtopostfix [-v|-h] infix_input ..."
print "-v, --verbose be verbose. use twice or thrice for more output"
print "-h, --help show this help"
sys.exit(0)
else:
input.append(v)

if not len(input):
print "Please provide infix input string"
else:
# Print all input strings
for i in input:
if verbose:
print "Processing:", i
print infixtopostfix(i.strip())```