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和其他函数语言中的常见模式.

• 第二个子句识别a "(",它启动一个新的子列表.为了处理它,它将累加器更改为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"]