erlang - erlang中如何将中缀转换为后缀？

Question

我刚刚遇到this post ，相当优雅。

但是没有考虑到不同算子的优先级。

例如* 的优先级高于 +。

因此 1+2*(3+2) 应转换为 1 2 3 2 + * +

考虑到优先级问题，在erlang中如何做到这一点？

Answer 1

这里有一种方法，它滥用了 Erlang 术语的内置解析器。您可以通过 yecc 或递归下降编写自己的解析器，但为了简单起见，我将坚持使用 Erlang 解析器。

  -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").

这只是格式化。