3

我正在玩 Erlang 并尝试编写一个 S 表达式解析器。我发现在 Python 中使用堆栈和循环是一项简单的任务，但对于不可变变量和 Erlang 数据结构的初学者来说，这并非易事。

我需要像这样在 Erlang 中转换一个列表：

X = ["0", "(", "1", "2", "3", ")"],
Res = transform(X). % ["0", ["1", "2", "3"]]

到目前为止，我已经做到了：

transform(List) ->
    lists:map(fun(X)->
                      case string:equal("(", X) of
                          %% recursive call with sublist of List from "(" to ")" as argument
                          true -> transform_to_list(Lack) 
                      end
              end, List).

不知道如何获取子列表Lack并将其作为参数传递。我是否朝着正确的方向前进？

4

2 回答 2

5

You can solve this using an accumulator and pattern matching:

-module(t).
-export([transform/1]).

transform(List) ->
    transform(List, []).

transform([], Acc) ->
    lists:reverse(Acc);
transform(["("|T], Acc) ->
    transform(T, {[],Acc});
transform([")"|T], {L,{L2,Acc}}) ->
    transform(T, {[lists:reverse(L)|L2],Acc});
transform([")"|T], {L,Acc}) ->
    transform(T, [lists:reverse(L)|Acc]);
transform([H|T], {L,Acc}) ->
    transform(T, {[H|L],Acc});
transform([H|T], Acc) ->
    transform(T, [H|Acc]).

The transform/1 function just sets up an empty accumulator for transform/2, where all the work is done.

The transform/2 function is separated into multiple pattern-matching recursive clauses:

  • The first clause handles the case where we've exhausted the input list, and it simply returns the reversed accumulator. Reversal is needed because items are pushed into the accumulator, so it ends up in reverse order. This is a common pattern in Erlang and other functional languages.

  • The second clause recognizes a "(", which starts a new sublist. To handle it, it changes the accumulator to a 2-tuple, where the first item is a sublist accumulator and the second item is the old accumulator.

  • The third and fourth clauses handle ")", which ends a sublist. The third clause is for the case where the accumulator is a tuple holding a second element which is also a tuple; it adds the new sublist as an item to the previous sublist and pops one level from the accumulator tuple. The fourth clause handles the case where the original accumulator in the tuple is a list, adding the new sublist to the head of the original accumulator to form a new accumulator list.

  • The fifth and sixth clauses handle input items that are not grouping operators. The fifth clause handles the case when the accumulator is a tuple, while the sixth clause handles the case when the accumulator is a list.

Running this on your original example shows the correct answer:

1> c(t).
{ok,t}
2> t:transform(["0", "(", "1", "2", "3", ")"]).
["0",["1","2","3"]]

But it can also handle nested groups:

3> t:transform(["0", "(", "11", "22", "(", "333", "444",
                "(", "5555", ")", "666", ")", "77", "88", ")", "9"]).
["0",["11","22",["333","444",["5555"],"666"],"77","88"],"9"]
于 2016-09-16T13:19:17.723 回答
3

我知道你已经得到了答案，但我昨天去海滩之前读了你的问题，我在看风筝冲浪“芭蕾舞”时想象了这个问题，所以我给了它，它和史蒂夫的有点不同，所以可能很有趣。

在此分析的情况下不能使用 lists:map 函数，因为它仅将给定函数应用于列表的每个元素以构建具有相同长度的新列表。没有办法建立嵌套列表。正如@Steve 所说，您需要一个累加器来逐步构建结果。

列表库提供了一个在遍历列表时累积术语的功能：lists:foldl/3（它也存在 foldr、mapfoldl 和 mapfoldr），在这种情况下，问题是定义将帮助我们构建预期结果的累加器。

  • 要分析的最简单的列表没有括号，因此累加器应该包含一个列表，用于累积条目列表的所有元素。

  • 但是如果我们遇到一个“（”，我们应该开始一个新的列表，它将包含我们必须嵌套在结果中的子列表。在这种情况下，我们需要一个包含列表的术语，我们可以将新的子列表用于构建，并且当我们遇到“（”时正在处理的列表。

可以以单一形式满足 2 个需求的最简单结构是列表列表：[SublistInProgress|PreviousWork]

现在我们知道了累加器的形式，我们可以定义负责构建它的函数，3种情况：

  • 我们找到一个“（”：开始一个新的子列表，并“存储”之前的累加器
  • 我们找到一个“）”：将子列表添加到前一个累加器中
  • 任何其他情况将元素添加到正在进行的子列表中。

在外壳中：

1>  F = fun("(",Acc)-> [[],Acc];                                               
1>         (")",[SubList,[Hacc|Tacc]]) -> [[lists:reverse(SubList)|Hacc]|Tacc];
1>         (X,[Hacc|Tacc]) -> [[X|Hacc]|Tacc] end.                             
#Fun<erl_eval.12.52032458>

注意：我使用构造[X|Hacc]而不是在列表中累积元素Hacc ++ [X]，这是一个好习惯，因为它避免在每一步都创建一个全新的列表（这样做我会避免我的朋友@Hynek-Pichi-Vychodil 的评论:o)。所以当我想存储它时，我必须反转列表。

在函数中使用 Flists:foldl(F,[[]],L)我们将得到一个元素的列表，该元素与预期结果相反。所以我们必须将这个对库的调用嵌入到一个特定的函数中：

2> Transform = fun(L) -> [R] = lists:foldl(F,[[]],L),
2>                       lists:reverse(R) end.
#Fun<erl_eval.6.52032458>

我们可以测试它：

3> L1 = ["0", "(", "1", "2", "3", ")"].
["0","(","1","2","3",")"]
4> L2 = ["0", "(", "11", "22", "(", "333", "444","(", "5555", ")", "666", ")", "77", "88", ")", "9"].
["0","(","11","22","(","333","444","(","5555",")","666",")",
 "77","88",")","9"]
5> Transform(L1).
["0",["1","2","3"]]
6> Transform(L2).
["0",["11","22",["333","444",["5555"],"666"],"77","88"],"9"]
于 2016-09-17T13:37:42.750 回答