rpn.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import re

OPERADORES = (u'√^', '*/', '+-')
RE_OPS = '([\\' + '\\'.join(''.join(OPERADORES)) + '])'


def separar_operandos_e_operadores(expressao):
    "Separa a expressão sem parenteses em lista de operandos e operadores"
    return re.sub(RE_OPS, r'|\1|', expressao).split('|')


def rpn_sem_parenteses(expressao):
    "Retorna o formato RPN para a expressão sem parenteses"
    e = separar_operandos_e_operadores(expressao)
    for op in OPERADORES:
        while op[0] in e or op[1] in e:
            if op[0] in e and op[1] in e:
                i = min(e.index(op[0]), e.index(op[1]))
            else:
                i = e.index(op[0]) if op[0] in e else e.index(op[1])
            e[i-1] += e[i+1] + e[i]
            del e[i+1]
            del e[i]
    return e[0]


def rpn(expressao):
    "Retorna o formato RPN para a expressão dada"
    # Delta vai receber o rpn de cada parte da expressão sem parenteses
    delta = []
    d = 0
    while ')' in expressao:
        i = expressao.index(')')
        j = expressao[:i].rindex('(')
        delta.append(rpn_sem_parenteses(expressao[j+1:i]))
        # Substitui por delta numerado o conteúdo entre parenteses
        expressao = expressao[:j] + 'ð%03i' % d + expressao[i + 1:]
        d += 1
    # RPN do resto da expressão sem parenteses e com deltas
    expressao = rpn_sem_parenteses(expressao)
    # Substitui o delta numerado pelo conteúdo RPN calculado anteriormente
    while 'ð' in expressao:
        i = expressao.index('ð')
        d = int(expressao[i+2:i+5])
        expressao = expressao[:i] + delta[d] + expressao[i+5:]
    # Retorna a expressão RPN final
    return expressao

expressao = raw_input('Digite a expressão: ')

print "%s => %s" % (expressao, rpn(expressao))