From infix notation to Reverse Polish notation using Shunting-yard algorithm

shunting_yard.py

#
# simplified version of http://en.wikipedia.org/wiki/Shunting-yard_algorithm
# no error checking for mismatched parentheses
# letters used instead of numbers
#
def shunting_yard(s):
    output_queue = []
    operator_stack = []
    
    operators = dict({
        "^": {"precedence": 4, "associativity": "right"},
        "*": {"precedence": 3, "associativity": "left"},
        "/": {"precedence": 3, "associativity": "left"},
        "+": {"precedence": 2, "associativity": "left"},
        "-": {"precedence": 2, "associativity": "left"}})
        
    def allow(o1, o2):
        if not o2 in operators:
            return False
        return (operators[o1]["associativity"] == "left" and \
            operators[o1]["precedence"] <= operators[o2]["precedence"]) or \
        (operators[o1]["associativity"] == "right" and \
            operators[o1]["precedence"] < operators[o2]["precedence"])

    for token in s:
        if token.isalpha():
            output_queue.append(token)
        elif token in operators:
            for index, x in enumerate(operator_stack[:]):
                if x not in operators:
                    break
                if allow(token, x):
                    output_queue.append(x)
                    operator_stack[index] = None
            operator_stack = [e for e in operator_stack if e != None]
            operator_stack.insert(0, token)
        elif token == "(":
            operator_stack.insert(0, token)
        elif token == ")":
            for index, stack_token in enumerate(operator_stack[:]):
                if stack_token == "(":
                    operator_stack[index] = None
                    break
                if stack_token in operators:
                    output_queue.append(stack_token)
                    operator_stack[index] = None
            operator_stack = [e for e in operator_stack if e != None]
        
    for stack_token in operator_stack:
        if stack_token in operators:
            output_queue.append(stack_token)
    
    return "".join(output_queue)
        
assert shunting_yard("a+b") == "ab+"
assert shunting_yard("(a+(b*c))") == "abc*+"
assert shunting_yard("((a+b)*(z+x))") == "ab+zx+*"
assert shunting_yard("((a+t)*((b+(a+c))^(c+d)))") == "at+bac++cd+^*"
assert shunting_yard("c+d*b/(a-e)^b^c") == "cdb*ae-bc^^/+"

print "All good"