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

Question

我刚刚看到这篇文章，相当优雅。

但它没有考虑到不同运营商的优先级。

例如，* 的优先级高于+。

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

这只是格式化。

Answer 2

您可以从我的 Erlang 编程练习 3-8 解决方案。有所有手写的词法分析器、解析器和后缀代码的“编译器”。

编辑：抱歉，我发现练习 3-8 有明确的括号，因此它无法解决运算符优先级问题。您必须修改解析器才能处理它。