solution for http://www.spoj.com/problems/ONP/

spoj_onp_pratice.py

STATE_OPEREND = 0
STATE_OPERATOR = 1

def to_rpn(expr):
    rpn = ['', '', '']
    state = STATE_OPEREND
    operend_i = 0
    while len(expr) > 0:
        ch = expr[0]
        
        if state == STATE_OPEREND:
            rpn[operend_i], expr = to_rpn(expr[1:]) if ch == '(' else (ch, expr[1:])
            if operend_i == 0:
                state = STATE_OPERATOR
                operend_i = 1
            else:
                expr = expr[1:] # for ')'
                break
            
        elif state == STATE_OPERATOR:
            rpn[2], expr = ch, expr[1:]
            state = STATE_OPEREND
                       
    return ''.join(rpn), expr
    
inputs = ['(a+(b*c))',
     '((a+b)*(z+x))',
     '((a+t)*((b+(a+c))^(c+d)))']

for expr in inputs:
    print to_rpn(expr)[0]