如何将二进制表达式树从字符串转换为嵌套列表？

Question

我最初的问题是理解我什至想做什么。我真的不知道 如何 寻求帮助，因为我真的不明白这就是我想做的事情。我已经在我的回答中详细解释了 我做了什么，以及我是怎么做到的。我也发布了我的代码。

在用 C# 构建它之前，我花了一段时间在 PowerShell 中制作原型。我希望这对其他人有帮助。

问题：

如何将 "(Foo1 && Bar1 && (Foo2 || Bar2) && (Foo3 || Foo4))" 这样的字符串转换成这样的列表：

[
   ["Foo1", "Bar1", "Foo2", "Foo3"],
   ["Foo1", "Bar1", "Foo2", "Foo4"],
   ["Foo1", "Bar1", "Bar2", "Foo3"],
   ["Foo1", "Bar1", "Bar2", "Foo4"]
]

Answer 1

将二进制表达式树的字符串表示形式转换为所有可能组合的嵌套字符串列表

我正在尝试构建一个 class，它允许我将字符串格式的二进制表达式树（请参阅下面的输入示例）转换为所有可能的值组合的嵌套列表。一开始，我并不知道这是一个二叉表达式树，因此也不知道如何找到我要找的东西。

Note : I'm not formally trained in CS nor did I receive a formal education in programming. I came up in IT as a Systems Admin who, aside from a brief period of programming in C++ as a teen, and years of HTML/CSS had never really messed with compiled software. I wrote a lot of scripts and spent about five years master PowerShell -- which is still where I'm the most comfortable. Most of my prototyping for this was done in PowerShell (7.1.3).

您可以在 github 上看到 My Code。

输入示例

示例 1

"(param_1 && param_2 && (param_3 || param_4) && (param_5 || param_6 || param_7))"

示例 2

"((param1 && (param2 || param3 || param4)) && param5)"

示例 3

"(param1 || (param2 && param3 && param4 && (param5 || param6 || param7)))"

预期产出

示例 1

[
    ["param_1","param_2","param_3","param_5"],
    ["param_1","param_2","param_3","param_6"],
    ["param_1","param_2","param_3","param_7"],
    ["param_1","param_2","param_4","param_5"],
    ["param_1","param_2","param_4","param_6"],
    ["param_1","param_2","param_4","param_7"]
]

示例 2

[
    [
        ["param1", "param2", "param5"],
        ["param1", "param3", "param5"], 
        ["param1", "param4", "param5"]
    ]
]

示例 3

[
    [
        ["param1"],
        ["param2", "param3", "param4", "param5"],
        ["param2", "param3", "param4", "param6"],
        ["param2", "param3", "param4", "param7"]
    ]
]

一路上有一些痛点——我在尝试解决问题时遇到了困难并最终重复工作。

将字符串转换为二进制表达式树

在我在库中找到我要找的东西之前，我花了相当多的时间构建一个解析器来将字符串转换成二进制表达式树。

解决方案

最终我找到了 NRECO 的 LambdaParser library (github)，这消除了很多这样做的压力（尽管我很确定我构建的东西在这个意义上是完整的）。

意外的边缘案例

虽然这看起来微不足道且显而易见，但我在遍历树构建列表时一直 运行 遇到问题。

左成员中有多个赞

最初我没有考虑到左侧成员包含多个类似表达式（ie“this AND that AND that too”）的情况，这导致构建了不完整的列表。

节点不包含成员表达式 (?)

我以为我已经完成了这个工具。我得到了一个可能的表达式列表（超出了我测试过的少数表达式），然后......它崩溃了。我发现我没有考虑当前处理节点包含两个二进制表达式的情况。 （而到目前为止，我构建它的印象是一侧或另一侧总是 总是 成员表达式）

一旦我遇到这个问题，我就意识到出了什么问题，并且已经花了很多时间在这件事上我知道 什么 需要完成，只是不太清楚我打算怎么做。

解决方案

当出现这些节点之一时，我必须根据与下一个成员表达式最接近 的表达式创建两条发散路径。从那里它将创建两条路径，在相反的节点上向下处理，直到到达“底部”。我们可以将每条路径的每次迭代添加到主要输出。鉴于此函数是递归的，不应该不管它发生了多少次

NOTE : In my solution, when it encounters a Binary Expression containing no Member Expressions it does currently still assume that one of the two expressions will be a Member Expression. That said, if I understand the nature of this type of expression, I don't think this should be an issue

Note : I had found a few references, including this regarding doing something similar F#, but I couldn't seem to apply this to my problem.

要点

对我来说，这是一次非常有用的学习经历，我遇到了涉及核心数据结构的现实世界问题。由于我没有（编程）算法或数据结构的真正背景，这教会了我很多东西，尽管它是一个巨大的 PITA，但它教会了我很多关于如何在未来解决这些类型的问题。如果你有时间，我会鼓励任何人尝试自己构建它。感谢阅读。