Ejercicio resuelto: evaluar expresiones con pila y recursión en Python

La solución separa el problema en cuatro piezas pequeñas: tokenizar produce la cola de tokens, a_posfija convierte con la pila de operadores, evaluar_posfija calcula con la pila de operandos y evaluar_recursivo resuelve lo mismo con tres funciones mutuamente recursivas. El main lee, imprime y verifica que las dos vías dan el mismo valor.

El detalle más traicionero es la división: Python usa // con redondeo hacia menos infinito, así que -7 // 2 da -4, mientras que el enunciado exige -3. La función auxiliar dividir calcula el cociente con valores absolutos y le restituye el signo. La división por cero se señala con una excepción propia que el main captura para escribir ERROR.

import sys
from collections import deque

PREC = {'+': 1, '-': 1, '*': 2, '/': 2}


class DivisionPorCero(Exception):
    pass


def tokenizar(linea):
    cola = deque()
    i = 0
    n = len(linea)
    while i < n:
        c = linea[i]
        if c.isspace():
            i += 1
        elif c.isdigit():
            j = i
            while j < n and linea[j].isdigit():
                j += 1
            cola.append(linea[i:j])
            i = j
        else:
            cola.append(c)
            i += 1
    return cola


def dividir(a, b):
    if b == 0:
        raise DivisionPorCero()
    q = abs(a) // abs(b)
    return q if (a >= 0) == (b >= 0) else -q


def aplicar(op, a, b):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    return dividir(a, b)


def a_posfija(tokens):
    cola = deque(tokens)
    salida = []
    pila = []
    while cola:
        t = cola.popleft()
        if t.isdigit():
            salida.append(t)
        elif t == '(':
            pila.append(t)
        elif t == ')':
            while pila[-1] != '(':
                salida.append(pila.pop())
            pila.pop()
        else:
            while pila and pila[-1] != '(' and PREC[pila[-1]] >= PREC[t]:
                salida.append(pila.pop())
            pila.append(t)
    while pila:
        salida.append(pila.pop())
    return salida


def evaluar_posfija(posfija):
    pila = []
    for t in posfija:
        if t.isdigit():
            pila.append(int(t))
        else:
            b = pila.pop()
            a = pila.pop()
            pila.append(aplicar(t, a, b))
    return pila[0]


def evaluar_recursivo(tokens):
    cola = deque(tokens)

    def expresion():
        valor = termino()
        while cola and cola[0] in ('+', '-'):
            op = cola.popleft()
            valor = aplicar(op, valor, termino())
        return valor

    def termino():
        valor = factor()
        while cola and cola[0] in ('*', '/'):
            op = cola.popleft()
            valor = aplicar(op, valor, factor())
        return valor

    def factor():
        t = cola.popleft()
        if t == '(':
            valor = expresion()
            cola.popleft()
            return valor
        return int(t)

    return expresion()


def main():
    lineas = sys.stdin.read().split('\n')
    n = int(lineas[0].strip())
    salida = []
    for k in range(1, n + 1):
        linea = lineas[k] if k < len(lineas) else ''
        tokens = list(tokenizar(linea))
        if not tokens:
            salida.append('VACIA')
            continue
        posfija = a_posfija(tokens)
        texto = ' '.join(posfija)
        try:
            valor = evaluar_posfija(posfija)
            if valor != evaluar_recursivo(tokens):
                raise RuntimeError('las dos evaluaciones no coinciden')
            salida.append(texto + ' = ' + str(valor))
        except DivisionPorCero:
            salida.append(texto + ' = ERROR')
    print('\n'.join(salida))


main()

tokenizar recorre la línea con el índice i. Los espacios se saltan; si encuentra un dígito, avanza j mientras siga habiendo dígitos y añade el trozo completo a la cola, de modo que 12 es un único token. Cualquier otro carácter (operador o paréntesis) es un token de un símbolo. Si la lista de tokens queda vacía, el main imprime VACIA, que es el caso de la prueba con línea en blanco.

a_posfija es el algoritmo clásico de la pila de operadores. Los números pasan directos a salida. Un ( se apila; un ) desapila hacia la salida hasta encontrar su pareja, que se descarta. Para un operador, el bucle while desapila mientras el tope tenga precedencia mayor o igual: esa igualdad es lo que da asociatividad por la izquierda. Por eso 8 - 3 - 2 se convierte en 8 3 - 2 - y vale 3, y no 7.

evaluar_posfija usa una segunda pila con los operandos. Cada operador saca primero b y después a (el orden importa en - y /) y apila aplicar(t, a, b). Al final queda un solo valor. La función dividir resuelve el truncamiento hacia cero y lanza DivisionPorCero, que main captura: en la prueba 4 / (2 - 2) se imprime la posfija 4 2 2 - / con ERROR.

evaluar_recursivo reproduce la precedencia con la estructura de las llamadas: expresion llama a termino, y este a factor. Un factor o es un número o abre un paréntesis y vuelve a llamar a expresion; ahí está la recursividad. Las funciones internas comparten la cola por cierre léxico, y consumir con popleft hace que cada llamada avance por la entrada sin necesidad de índices. El main compara ambos resultados como comprobación interna.

Los casos de prueba cubren: el ejemplo mixto del enunciado, un único número (posfija igual al propio número), paréntesis anidados con números de varias cifras, la asociatividad izquierda, la división truncada con un valor negativo obtenido mediante 0 - 7, la división por cero y la línea vacía.