13 - Ejemplo práctico 4: parser infijo → postfijo

13.1 Objetivo

Transformar expresiones infijas en postfijas usando una pila de operadores y luego evaluar el resultado con una pila de operandos.

13.2 Características

  • Admite operadores +, -, *, / y paréntesis.
  • Separación en tokens por espacios.
  • Dos fases: conversión y evaluación.

13.3 Conversión infijo → postfijo

Se sigue el algoritmo de Shunting-yard:

  1. Recorrer cada token.
  2. Si es operando, enviarlo a la salida.
  3. Si es operador, compararlo con el tope de la pila y desapilar operadores con mayor o igual precedencia.
  4. Manejar paréntesis apilando “(” y desapilando hasta encontrarlo cuando aparece “)”.

13.4 Evaluación postfija

  • Recorrer los tokens postfijos.
  • Apilar operandos.
  • Ante un operador, desapilar los dos últimos, aplicar la operación y apilar el resultado.
  • El último valor en la pila es el resultado final.

13.5 Implementación en Python

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


def es_operador(tok):
  return tok in PRECEDENCIA


def infijo_a_postfijo(expr):
  salida = []
  ops = []
  tokens = expr.split()

  for tok in tokens:
    if tok.isdigit():
      salida.append(tok)
    elif tok == '(':
      ops.append(tok)
    elif tok == ')':
      while ops and ops[-1] != '(':
        salida.append(ops.pop())
      ops.pop()
    elif es_operador(tok):
      while ops and ops[-1] != '(' and PRECEDENCIA.get(ops[-1], 0) >= PRECEDENCIA[tok]:
        salida.append(ops.pop())
      ops.append(tok)

  while ops:
    salida.append(ops.pop())
  return salida


def evaluar_postfija(tokens):
  pila = []
  for tok in tokens:
    if tok.isdigit():
      pila.append(float(tok))
    else:
      b = pila.pop()
      a = pila.pop()
      if tok == '+':
        pila.append(a + b)
      elif tok == '-':
        pila.append(a - b)
      elif tok == '*':
        pila.append(a * b)
      elif tok == '/':
        pila.append(a / b)
  return pila.pop()


if __name__ == "__main__":
  expr = "3 + 4 * 2 / ( 1 - 5 )"
  postfija = infijo_a_postfijo(expr)
  print("Postfija:", " ".join(postfija))
  print("Resultado:", round(evaluar_postfija(postfija), 2))

Con este ejemplo se cubre una aplicación clásica de pilas en compiladores y calculadoras, reforzando el dominio de la estructura.

Abrir editor online
Retornar