使用 Racket 中的关联属性重新排序括号 [英] Reordering parentheses using associative property in Racket

问题描述

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

I am having trouble implementing a function that given something like this:

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

返回:

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

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

Now the catch is that I have to use associativity to get the answer so I only want to use this property:

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

获得正确的输出.我知道如何为这种情况实现该功能:

To get the correct output. I know how to implement the function for this case:

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

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

However I cannot seem to figure out how to implement it for the first case above (or any other case larger than three items). I am not looking for answers only some guidance. If you would like to see code snippets let me know and I can post some. Also, I created a function that stripped the '+ from the list to make it easier to process.

我认为这定义了语法:

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

有效 fpip 的位置:

Where a valid fpip can be:

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

或

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

在最原子的层面上:

fpip = '(a + b)

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

edit: yes the initial '+ should be erased. Regardless of how many plus signs there are in the initial input there should only be (amount-of-vars - 1) '+ in the output. For example:

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

推荐答案

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

I think these are the cases to consider. Let's call the the recursive rewriter 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 中的关联属性重新排序括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！