erlang - Erlang中的递归列表分析

Question

我正在使用 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 并将其作为参数传递。我的方向正确吗？

Answer 1

您可以使用累加器和模式匹配来解决这个问题:

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

transform/1 函数只是为 transform/2 设置了一个空的累加器，所有的工作都在这里完成。

transform/2 函数被分成多个模式匹配的递归子句:

• 第一个子句处理我们已经用尽输入列表的情况，它只是返回反转的累加器。需要反转，因为项目被插入累加器，所以它以相反的顺序结束。这是 Erlang 和其他函数式语言中的常见模式。

• 第二个子句识别一个 "("，它启动一个新的子列表。为了处理它，它将累加器更改为 2 元组，其中第一项是子列表累加器第二项是旧的累加器。

• 第三和第四个子句处理")"，它结束一个子列表。第三个条款适用于累加器是一个元组的情况，该元组包含第二个元素，该元素也是一个元组；它将新的子列表作为项目添加到前一个子列表中，并从累加器元组中弹出一个级别。第四个子句处理元组中的原始累加器是列表的情况，将新的子列表添加到原始累加器的头部以形成新的累加器列表。

• 第五个和第六个子句处理不是分组操作符的输入项。第五个子句处理累加器为元组的情况，第六个子句处理累加器为列表的情况。

在您的原始示例上运行它会显示正确答案:

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

但它也可以处理嵌套组:

3> t:transform(["0", "(", "11", "22", "(", "333", "444",
                "(", "5555", ")", "666", ")", "77", "88", ")", "9"]).
["0",["11","22",["333","444",["5555"],"666"],"77","88"],"9"]