如何在Erlang中将中缀表达式转换为后缀表达式？

Question

我刚看到了这篇文章，它非常优雅。

但是它没有考虑不同运算符的优先级。

例如，*比+的优先级更高。

所以1+2*(3+2)应该转换为1 2 3 2 + * + 如何在erlang中解决优先级问题？

- Je Rog

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

这只是格式化文本。

- I GIVE CRAP ANSWERS

---

就像我之前提到的那样，优先级是由解析器处理的。这与“如何以逆波兰表示法格式化解析树”的问题完全无关，而这正是上文所做的。你可以查阅递归下降算法，它是一种针对LL(1)语法的表达式的方法。 - I GIVE CRAP ANSWERS

我需要有很多在erlang中不存在的额外运算符，因此我需要手动指定优先级，而不是使用erlang的默认设置。 - Je Rog

看看leex+yecc吧。它是为这种东西构建的。去拿一本关于解析的书，它会帮助你理解如何做到这一点。 - I GIVE CRAP ANSWERS

如果我要创建一个新的编程语言，我只会使用leex/yecc工具链...转换为后缀表达式并不像那么难，但也不是很容易。 - Je Rog

Answer 2

你可以参考我的Erlang编程练习3-8的解决方案来获得灵感。其中包含手写的词法分析器、语法分析器和将代码转换为后缀表达式的“编译器”。 编辑：抱歉，我看到练习3-8中有明确的括号，因此它不能解决运算符优先级。您需要修改解析器来处理它。

- Hynek -Pichi- Vychodil