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

Question

我遇到了读取包含逻辑语句的输入文件的问题，并且需要构建一个真值表来确定 ASK 是否与任何/所有已确定的模型匹配。我可能希望读入的一些数据的示例是:

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

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

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

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

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

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

Answer 1

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

你的表情会变成:

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

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

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

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

正如评论中所建议的，您可以使用调车场算法来完成。