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.
More information on postfix and infix can be found at Postfix notation and Infix notation. See also Prefix notation.
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 # for more information # # 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 beVerbose(3, "added to output") 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 beVerbose(3, "and added to output") 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())
