parsing - 我试图弄清楚如何将带括号的布尔表达式展平为一组逻辑上相同的有序表达式

Question

所以假设我有这样的表达：

((((e1)或(e2))和(e3或(e5和e6))和(e7))或(e8))

我需要得到一个表达式列表（e1、e2、e3 等），然后是和/或运算符，以便从左到右评估列表会产生相同的逻辑布尔答案。

即e1 或e2 和e5 和e6 或e3 和e7 或e8。但这不是正确的答案，但这是我需要结束的事情。

我知道递归下降解析器会评估表达式，但这不是我需要的，我需要得到一个表达式列表，以后可以从左到右进行评估。

我想把它放在二叉树中，然后导航树后缀或类似的东西，但这似乎不对。

我曾经很聪明，可以弄清楚这样的事情，但现在我有了一个孩子，并且失去了我所有的高级认知能力。帮助？

Answer 1

首先，您要做的是将中缀表示法转换为后缀表示法。

您对解析器的想法是正确的，因为您确实需要解析（但不评估）原始表达式，然后以后缀表示法将其打印出来。

Answer 2

我的父亲拥有近乎无限的智慧（尽管有 2 个孩子），他指出了一个相当简单的解决方案：德摩根定律说你可以重写任何表达式以仅使用 AND 或 OR 以及 NOT 的各种用法。因此，只需将所有 AND 表达式转换为等效的 OR，删除括号，然后从左到右求值。非常可行的想法，除了在我的情况下 NOT 操作非常昂贵。