Как конвертировать инфикс в постфикс в эрланге?

Question

Я только что натолкнулся на этот пост , он довольно элегантный.

Но он не учитывает приоритет различных операторов.

Например, * имеет болееприоритет чем +.

Так что 1+2*(3+2) следует преобразовать в 1 2 3 2 + * +

Как это сделать в erlang с учетом вопроса о приоритете?

Answer 1

Вот способ сделать это, который использует встроенный парсер для терминов Эрланга.Вы можете написать свой собственный синтаксический анализатор с помощью yecc или рекурсивного спуска, но для простоты я остановлюсь на Erlang-parser.

  -module(foo).
  -compile(export_all).

Объявите модуль, экспортируйте все из него.Это плохая форма, если вы хотите использовать это.Скорее минимизируйте экспорт в p/1.

 parse(Str) ->    
     {ok, Tokens, _} = erl_scan:string(Str ++ "."),
     {ok, [E]} = erl_parse:parse_exprs(Tokens),
     E.

Эта функция использует синтаксический анализатор Erlang, поэтому мы можем получить дерево синтаксического анализа токенов Erlang.

 rpn({op, _, What, LS, RS}) ->
     rpn(LS),
     rpn(RS),
     io:format(" ~s ", [atom_to_list(What)]);
 rpn({integer, _, N}) ->
     io:format(" ~B ", [N]).

RPN-выход должен выполнитьобход дерева после заказа.Таким образом, мы в основном обходим левую и правую стороны дерева и затем выводим себя как узел.Порядок «круглых скобок» хранится абстрактно в самом дереве.Приоритет обрабатывается парсером Erlang.Вы можете легко сделать это через парсер рекурсивного спуска, если хотите.Но это другой вопрос, касающийся вопроса «Как писать парсеры на Erlang?»Ответ двоякий: либо вы используете leex + yecc, либо вы используете парсер, основанный на комбинаторах парсера и / или рекурсивном спуске.Особенно для грамматики это просто.

 p(Str) ->
      Tree = parse(Str),
      rpn(Tree),
      io:format("~n").

Это просто форматирование.

Answer 2

Вы можете вдохновиться моим решением Erlang Programming Exercise 3-8 .В постфиксном коде есть весь рукописный лексер, парсер и «компилятор».

Редактировать: Извините, я вижу, что упражнение 3-8 имеет явные скобки, поэтому оно не решает приоритет оператора.Вам придется изменить парсер, чтобы справиться с этим.