Infix to Postfix

infix-to-postfix.py

#
# Program to convert infix expressions to postfix.
# It supports the following operators:
# - Addition ("+")
# - Multiplication ("*")
# - Logarithm ("L")
#
# Single digit values are supported.
# Lower-case alphabets are considered as variables.
# 
# Examples:
#
# python infix-to-postfix.py '3+4*5'
# POSTFIX: 345*+
#
# python infix-to-postfix.py '(3+4)*5'
# POSTFIX: 34+5*
# 
# python infix-to-postfix.py 'L(3*x+4)'
# POSTFIX: 3x*4+L
#
# python infix-to-postfix.py 'L(L(3*x+4)+5)'
# POSTFIX: 3x*4+L5+L
#
# python infix-to-postfix.py 'L(3*x+4)+L(L(3*x+4)+5)'
# POSTFIX: 3x*4+L3x*4+L5+L+
#

import sys

# operators in precedence order
OPERATORS = "+*L"

def is_operator(x) :
    return x in OPERATORS

def precedence(x) :
    assert x in OPERATORS
    return OPERATORS.index(x)

def main() :
    if len(sys.argv) != 2 :
        print "USAGE: python infix-to-postfix.py <infix-expr>"
        return

    infix = list(sys.argv[1])
    stack = ["("]
    infix = list(sys.argv[1] + ")")
    postfix = []

    while len(stack) > 0 :
        assert len(infix) > 0
        if infix[0] == '(' :
            stack.append(infix.pop(0))
        elif infix[0] == ')' :
            if stack[-1] == '(' :
                infix.pop(0)
                stack.pop(-1)
            else :
                postfix.append(stack.pop(-1))
        elif is_operator(infix[0]) :
            if stack[-1] == '(' :
                stack.append(infix.pop(0))
            else :
                assert is_operator(stack[-1])
                if precedence(stack[-1]) > precedence(infix[0]) :
                    postfix.append(stack.pop(-1))
                else :
                    stack.append(infix.pop(0))
        else :
            value = infix.pop(0)
            assert value.isdigit() or value.isalpha()
            assert value.lower() == value
            postfix.append(value)

    print "POSTFIX: %s" % ("".join(postfix),)

main()