在 Racket 中使用关联属性重新排序括号

Question

我在实现一个给出如下内容的函数时遇到了问题：

'((+(d + e) + f) + (a + (a + c))

Returns 这个：

'(d + (e + (f + (a + (a + c)))))

现在问题是我必须使用关联性来得到答案所以我只想使用这个属性:

'((a + b) + c) = '(a + (b + c))

得到正确的输出。我知道如何实现这个案例的功能：

'((a + b) + c) -> '(a + (b + c))

但是我似乎无法弄清楚如何为上面的第一种情况（或任何其他大于三项的情况）实施它。我不是在寻找答案，只是在寻找一些指导。如果您想查看代码片段，请告诉我，我可以 post 一些。此外，我创建了一个函数，从列表中删除了 '+ 以使其更易于处理。

我认为这定义了语法：

var ::=  a | b | c | d | e | f | g
fpip ::= var | (fpip + fpip)

有效的 fpip 可以是：

fpip = '((a + b) + c)

或

fpip = '((a + b) + (c + d))

在最原子的层面上：

fpip = '(a + b)

编辑：是的，应该删除初始的 '+。无论初始输入中有多少个加号，输出中都应该只有 (amount-of-vars - 1) '+。例如：

'(+ + + + (a + b) + + c) -> '(a + (b + c)

Answer 1

我认为这些是需要考虑的情况。我们将递归重写器称为 REWRITE。

var                               -> var
(var + var)                       -> (var + var)
(var + (fip1 + fpip2))            -> (var + (REWRITE (fip1 + fpip2))
((fip1 + fpip2) + var)            -> (REWRITE (fip1 + (fip2 + var))
((fip1 + fpip2) + (fip3 + fpip4)) -> (REWRITE (fip1 + (fip2 + (fip3 + fip4))))

在 Racket 中使用关联属性重新排序括号

Reordering parentheses using associative property in Racket

parentheses

associativity

racket

在 Racket 中使用关联 属性 重新排序括号

Reordering parentheses using associative property in Racket

parentheses

associativity

racket

在 Racket 中使用关联属性重新排序括号