Me encontré con this post, es bastante elegante.¿Cómo convertir infix a postfix en erlang?
Pero no está teniendo en cuenta la prioridad de los diferentes operadores.
p. Ej. * tiene una prioridad más alta que +.
Así 1+2*(3+2) deben convertirse en 1 2 3 2 + * +
Como hacerlo en Erlang tomando el tema prioritario en cuenta?
Aquí hay una manera de hacerlo que abusa del analizador incorporado para los términos de Erlang. Podrías escribir tu propio analizador mediante yecc o descenso recursivo, pero por simplicidad, me quedaré con el analizador de Erlang.
-module(foo).
-compile(export_all).
Declarar un módulo, exportar todo de él. Esta es una mala forma si quieres usar esto. Más bien, minimice la exportación a p/1.
parse(Str) ->
{ok, Tokens, _} = erl_scan:string(Str ++ "."),
{ok, [E]} = erl_parse:parse_exprs(Tokens),
E.
Esta función abusa del analizador de Erlang para que podamos obtener un árbol de análisis sintáctico de los tokens de Erlang.
rpn({op, _, What, LS, RS}) ->
rpn(LS),
rpn(RS),
io:format(" ~s ", [atom_to_list(What)]);
rpn({integer, _, N}) ->
io:format(" ~B ", [N]).
La salida RPN es para hacer un recorrido de caminata de árbol posterior a la orden. Así que, básicamente, caminamos por el lado izquierdo y el lado derecho del árbol y luego hacemos una salida a nosotros mismos como un nodo. El orden de "paréntesis" se almacena de forma abstracta en el árbol mismo. La prioridad es manejada por el analizador de Erlang. Usted puede hacer esto fácilmente a través de un analizador de bajadas recursivo si lo desea. Pero esa es una pregunta diferente al punto de "¿Cómo puedo escribir analizadores en Erlang?" La respuesta es doble: o usa leex + yecc o usa un analizador basado en los combinadores de analizador y/o el descenso recursivo. Especialmente para una gramática así de simple.
p(Str) ->
Tree = parse(Str),
rpn(Tree),
io:format("~n").
Esto es solo formateo.
Puede inspirarse en la mina Erlang Programming Exercise 3-8 solution. Hay todo lexer manuscrito, analizador y "compilador" de código postfix.
Edit: Lo siento, veo que el ejercicio 3-8 tiene un horquillado explícito, por lo que no resuelve la prioridad del operador. Tendría que modificar el analizador para manejarlo.
No veo la lógica de tratar con la prioridad allí .. –
Como indiqué, la prioridad es manejada por un analizador. Está realmente separado de la pregunta "¿Cómo formateo un árbol de análisis sintáctico en notación RPN?", Que es lo que hace el párrafo anterior. Puede buscar el descenso recursivo, que es una forma de hacerlo para una gramática LL (1) que son sus expresiones. –
Necesito tener muchos operadores adicionales que no existen en erlang, así que debo especificar la prioridad manualmente, no la configuración predeterminada de erlang. –