通过解析文件构建逻辑语句

Question

我遇到了读取包含逻辑语句的输入文件的问题，我需要构造一个 Truth Table 来确定 ASK 是否与确定的 any/all 模型匹配。我可能希望读入的一些数据的示例是：

(p & z => x) => ((p | d) & z)

请不要太拘泥于这个例子，无论它是否真的有意义，我只是为了展示我可能会遇到的不同组合而编造的。多个这样的语句可以用分号分隔。

我已经解决了没有任何戏剧性的分号拆分，现在有一个包含每个单独语句的字符串向量，其中每个字符串如上所示。现在不涉及括号，我相信确定陈述将是相当直接的，但随着他们的参与，我现在需要在其他人之前计算不同的部分。例如：

(p | d) = result 然后 (result & x)

我看到有人在讨论使用堆栈来确定左括号是否正确关闭的概念，但我认为这不适合我的情况，因为这不允许我确定里面有什么语句什么括号。

我目前的想法是使用堆栈的想法，并尝试确定一个语句的"depth"（本质上是嵌套多远）然后在每个语句中标记这个数字，但我相信这听起来像是一个不优雅的解决方案。有没有人对我应该如何构建算法来正确解决问题有任何提示？

Answer 1

您需要构建一个表达式树，其中您的变量是叶子。

你的表情会变成：

        =>
       / \
      /   \
     /     \
    =>      &
   / \     / \
  &   X   |   Z
 / \     / \
p   z   P   D

一旦构建了这种表示，评估就很简单了。

具有相同结果的另一种方法是将你的表达式简化为类似 RPN 的东西（你可以在其中使用你的堆栈想法）：

P, Z, &, X, =>, P, D, |, Z, &, =>

按照评论里的建议，可以用调车场算法来做。

Construct logic statements through parsing a file