import re
 
def toTree(infixStr):
    # divide string into tokens, and reverse so I can get them in order with pop()
    tokens = re.split(r' *([\+\-\*\^/]) *', infixStr)
    tokens = [t for t in reversed(tokens) if t!='']
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2}
 
    #convert infix expression tokens to a tree, processing only
    #operators above a given precedence
    def toTree2(tokens, minprec):
        node = tokens.pop()
        while len(tokens)>0:
            prec = precs[tokens[-1]]
            if prec<minprec:
                break
            op=tokens.pop()
 
            # get the argument on the operator's right
            # this will go to the end, or stop at an operator
            # with precedence <= prec
            arg2 = toTree2(tokens,prec+1)
            node = (op, node, arg2)
        return node
 
    return toTree2(tokens,0)
 
print toTree("5+3*4^2+1")
 

aW1wb3J0IHJlCgpkZWYgdG9UcmVlKGluZml4U3RyKToKICAgICMgZGl2aWRlIHN0cmluZyBpbnRvIHRva2VucywgYW5kIHJldmVyc2Ugc28gSSBjYW4gZ2V0IHRoZW0gaW4gb3JkZXIgd2l0aCBwb3AoKQogICAgdG9rZW5zID0gcmUuc3BsaXQocicgKihbXCtcLVwqXF4vXSkgKicsIGluZml4U3RyKQogICAgdG9rZW5zID0gW3QgZm9yIHQgaW4gcmV2ZXJzZWQodG9rZW5zKSBpZiB0IT0nJ10KICAgIHByZWNzID0geycrJzowICwgJy0nOjAsICcvJzoxLCAnKic6MSwgJ14nOjJ9CgogICAgI2NvbnZlcnQgaW5maXggZXhwcmVzc2lvbiB0b2tlbnMgdG8gYSB0cmVlLCBwcm9jZXNzaW5nIG9ubHkKICAgICNvcGVyYXRvcnMgYWJvdmUgYSBnaXZlbiBwcmVjZWRlbmNlCiAgICBkZWYgdG9UcmVlMih0b2tlbnMsIG1pbnByZWMpOgogICAgICAgIG5vZGUgPSB0b2tlbnMucG9wKCkKICAgICAgICB3aGlsZSBsZW4odG9rZW5zKT4wOgogICAgICAgICAgICBwcmVjID0gcHJlY3NbdG9rZW5zWy0xXV0KICAgICAgICAgICAgaWYgcHJlYzxtaW5wcmVjOgogICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgb3A9dG9rZW5zLnBvcCgpCgogICAgICAgICAgICAjIGdldCB0aGUgYXJndW1lbnQgb24gdGhlIG9wZXJhdG9yJ3MgcmlnaHQKICAgICAgICAgICAgIyB0aGlzIHdpbGwgZ28gdG8gdGhlIGVuZCwgb3Igc3RvcCBhdCBhbiBvcGVyYXRvcgogICAgICAgICAgICAjIHdpdGggcHJlY2VkZW5jZSA8PSBwcmVjCiAgICAgICAgICAgIGFyZzIgPSB0b1RyZWUyKHRva2VucyxwcmVjKzEpCiAgICAgICAgICAgIG5vZGUgPSAob3AsIG5vZGUsIGFyZzIpCiAgICAgICAgcmV0dXJuIG5vZGUKCiAgICByZXR1cm4gdG9UcmVlMih0b2tlbnMsMCkKCnByaW50IHRvVHJlZSgiNSszKjReMisxIikK