File information
Filename: infixtopostfix.py Uploaded: Tue, 2nd Mar 2010 19:41:14
Size (bytes): 6.97 KiB md5 checksum: bf74140203ea73df95ea3317f46372df
Description:

Implementation of infix to postfix conversation. Based around the shunting yard algorithm see http://en.wikipedia.org/wiki/Shunting_yard_algorithm for more information.

#!/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())