前缀转换在 prolog 中与 sin cos tan 等的一元运算符

Question

我是Prolog的新手。我正在努力学习这个。我正在构建一个前缀转换谓词的后缀。我搜索了很多谷歌和github等，prolog递归语法非常混乱。通过大量搜索，我刚刚在堆栈溢出上找到了这个链接。我完全在处理相同的问题，但指定的解决方案非常混乱。我脑海中没有出现 append/2 函数实现，那么一元运算符呢？现在已经超过 3 天了，我一直在解决这个问题，只是被吸住了。任何人请帮助我实现此逻辑或任何书籍参考或某些链接，以更好地了解同一问题。谢谢

我想用这种方式解决它

    post2pre([A,B,C|Rem],Pre) :- Pre=[C,A,B], isop(C).

但问题是如何处理 Rem？如果我列表中只有一两个项目怎么办我想这样解决它

   post2pre([A|[]],Pre) :- Pre=[A].
   post2pre([A,B|[]) :- Pre=[A,B]. 

对于 isOp（），我将它们定义为

   isop(+). isop(-). isop(*). isop(/). isop(sin). isop(cos). isop(exp).

但我不知道如何处理单一运算符？

Answer 1

好吧，正如我在那个答案中所建议的，pos2pre/2 这只是一个草图，由学生完成。但这也是一个棘手的解决方案，恕我直言，相当声明性。因此，它很容易扩展以处理一元运算符（我将 isop/1 重命名为 is_binary_op/1，以清理代码）：

pos2pre(Pos, Pre) :-
    append([A, B, [O]], Pos), is_binary_op(O), A = [], B = [],
    pos2pre(A, APre),
    pos2pre(B, BPre),
    !, append([[O], APre, BPre], Pre).
pos2pre(Pos, Pre) :-
    append([A, [O]], Pos), is_unary_op(O), A = [],
    pos2pre(A, APre),
    !, append([[O], APre], Pre).
pos2pre([P], [P]).
is_binary_op(O) :- memberchk(O,[+,*]).
is_unary_op(O) :- memberchk(O,[sin,tan]).

测试

?- pos2pre([1,2,3,+,*,sin],Pre)   .
Pre = [sin, *, 1, +, 2, 3].

我尝试遵循的另一种方法是使用完全不同的方案，构建一个中缀表达式解析器（DCG），然后让树的后缀/前缀访问在格式之间转换。

编辑这里是从SWI-Prolog库中窃取的append/2谓词（列表）：

append(ListOfLists, List) :-
    must_be(list, ListOfLists),
    append_(ListOfLists, List).
append_([], []).
append_([L|Ls], As) :-
    append(L, Ws, As),
    append_(Ls, Ws).

！ 符号名为 cut，它不是运算符，而是系统谓词（更准确地说，是控制谓词）。它总是成功，并修剪可能在执行点挂起的替代方案，从而承诺到目前为止所做的选择。您应该阅读有关此主题的一些在线文档...

Answer 2

这是一个替代版本。这个首先从后缀列表中构建前缀结构，作为 2 元素或 3 元素列表（每个一元或二进制操作）的嵌套列表结构，然后在末尾展平嵌套列表：

post2pre(Post, Pre) :-
    post2pre(Post, [], Pre).
post2pre([E|T], PreNest, Pre) :-
    (   unary_op(E)
    ->  PreNest = [Term|PNT],
        post2pre(T, [[E,Term]|PNT], Pre)
    ;   binary_op(E)
    ->  PreNest = [Term2,Term1|PNT],
        post2pre(T, [[E,Term1,Term2]|AP], Pre)
    ;   post2pre(T, [E|PreNest], Pre)
    ).
post2pre([], PreNest, Pre) :-
    flatten(PreNest, Pre).
unary_op(X) :-
    memberchk(X, [sin, cos, tan]).
binary_op(X) :-
    memberchk(X, [+, -, /, *]).

在上面的代码中，"原子项"被隐式定义为任何不是运算符的东西。

根据示例：

| ?- post2pre([1,2,3,+,*,sin],Pre).
Pre = [sin,*,1,+,2,3]
yes

在这种情况下，在flatten发生之前，"中间"嵌套形式将是：

[sin, [*, 1, [+, 2, 3]]]

上述代码的非 if-then-else 版本可以编写如下。我选择了上面的 if-then-else 结构，因为它避免了冗余检查运算符：

post2pre(Post, Pre) :-
    post2pre(Post, [], Pre).
post2pre([E|T], PreNest, Pre) :-
    atomic_term(E),
    post2pre(T, [E|PreNest], Pre).
post2pre([E|T], [Term|PNT], Pre) :-
    unary_op(E)
    post2pre(T, [[E,Term]|PNT], Pre).
post2pre([E|T], [Term2,Term1|PNT], Pre) :-
    binary_op(E)
    post2pre(T, [[E,Term1,Term2]|AP], Pre).
post2pre([], PreNest, Pre) :-
    flatten(PreNest, Pre).
atomic_term(X) :-  % This defines a term explicitly as anything but an operator
    + unary_op(X),
    + binary_op(X).
unary_op(X) :-
    memberchk(X, [sin, cos, tan]).
binary_op(X) :-
    memberchk(X, [+, -, /, *]).