Implementando el algoritmo de la playa de agujas

Ya he hablado de cómo funcionaba el algoritmo de la playa de agujas en una entrada anterior. Hoy voy a especificar el pseudocódigo para definir completamente el algoritmo.

Antes de entrar de lleno en materia, hemos de explicar las funciones y tipos auxiliares que vamos a usar.

• RESULTADO: El tipo del resultado del algoritmo. Será una expresión parentizada como 1+(2*3).
• TOKEN: El tipo de los elementos de la entrada podrán ser o bien operandos simples como 1, 2 o 3; o bien operadores como +, * o -.
• PrioridadDelOperador(t): Si t es un TOKEN de tipo operador, devuelve su prioridad. Los operadores con más prioridad se agrupan antes que los de menos prioridad. 
• ElSiguienteTokenEsOperador(): Devuelve cierto si el siguiente TOKEN a leer es un operador.
• LeeOperandoSimple(): Lee de la entrada un operando simple y lo consume quitándolo de la entrada. Falla (y el algoritmo termina con error) si el siguiente TOKEN es un operador.
• ConsultaSiguienteToken(): Lee sin consumir el siguiente TOKEN de la entrada.
• ConsumeToken(): Consume el siguiente TOKEN de la entrada quitándolo de la misma.
• CreaExpresion(operador, operando1, operando2): Crea una expresión parentizada con los operadores y operandos dados. Así, por ejemplo, CreaExpresion(+, 3, 7-2) crea la expresión 3+(7-2).  

Visto todo esto, podemos exponer el algoritmo que llamamos LeeExpresion().

RESULTADO LeeExpresion(int pri_anterior)
{
 RESULTADO a=LeeOperandoSimple();
 if(!ElSiguienteTokenEsOperador())
  return a;

 TOKEN t=ConsultaSiguienteToken();
 int pri_siguiente=PrioridadDelOperador(t);

 if(pri_siguiente<pri_anterior)
  return a;

 ConsumeToken();
 return CreaExpresion(t.data, a, LeeExpresion(prec));
}

Esta implementación funciona muy bien cuando todos los operadores son asociativos por la derecha. Es decir, tendremos que 1+2+3+4 se agrupa como 1+(2+(3+4)). Si queremos operadores que se asocien por la izquierda, necesitamos modificar ligeramente el algoritmo. También necesitamos saber si un operador es asociativo por la derecha o no. Esto lo conoceremos usando OperadorEsAsociativoDerecha(t) donde t es un TOKEN.

Este algoritmo mejorado es el siguiente:

RESULTADO LeeExpresion(int pri_anterior)
{
 RESULTADO a=LeeOperandoSimple();

 while(ElSiguienteTokenEsOperador())
 {
  TOKEN t=ConsultaSiguienteToken();
  int pri_siguiente=PrioridadDelOperador(t);

  if(OperadorEsAsociativoDerecha(t) ? pri_siguiente<pri_anterior : pri_siguiente<=pri_anterior)
   return a;

  ConsumeToken();
  a=CreaExpresion(t.data, a, LeeExpresion(prec));
 }

 return a;
}

Usando estos algoritmos es muy sencillo añadir operadores infijos a un reconocedor descendiente recursivo.