0

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

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

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

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

(p | d) = result 接着 (result & x)

我见过人们讨论使用堆栈来确定开括号是否正确关闭的概念，但我认为这不适合我的情况，因为这不允许我确定哪些语句在括号内。

我目前的想法是使用堆栈的想法，并尝试确定语句的“深度”（基本上是嵌套多远），然后用每个语句标记这个数字，但我认为这听起来像一个不雅的解决方案。有人对我应该如何构建算法以正确解决问题有任何提示吗？

4

1 回答 1

1

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

你的表达将变成：

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

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

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

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

正如评论中所建议的，您可以使用调车场算法来做到这一点。

于 2015-05-12T08:24:02.440 回答