逻辑表达式的表达树

Question

我需要将这个: (a < b)∧(b < c)∨(c < d)表达式转化为表达式树 但我想不出一个看起来正确的方法。我得到的是这样的结果。

Answer 1

我预测这将是一个很长的答案，因为我将通过一般的思维过程来实现解决方案。对于住院病人来说，解决方案在最后。

你的解决方案正确吗？

嗯，这要看情况。如果你的图片是完全正确的 ∨ 先于 ∧在这种情况下，您需要应用 ∧ 才 (b < c) ∨ (c < d) 有一个结果。如果你像这样用小括号强制优先，也是正确的。

(a < b) ∧ ( (b < c) ∨ (c < d) )

话说回来，当谈论到 操作者优先，通常 ∧/and 先于 ∨/or. 当优先级相同时，评估从左到右进行，这意味着右侧取决于左侧的结果。

一个运算符的优先级越高，它在树中的位置越低。

其余的答案将假设通常的运算符优先级。

如何处理这个问题？

处理这类问题的最好方法是分解表达式。更好的办法是，如果我们使用以下方法分解 抛光前记号，以后建树会更自然。

鉴于。(a < b) ∧ (b < c) ∨ (c < d)

我们把它分解成几个部分。

x = (a < b), which translates to prefix: < a b
y = (b < c), which translates to prefix: < b c
z = (c < d), which translates to prefix: < c d

我们现在有三个不等式，分解为 x, y 和 z.

现在说说逻辑运算符。

i = x ∧ y, which translates to prefix: ∧ x y
j = i ∨ z, which translates to prefix: ∨ i z

我们现在有2个逻辑表达式分解为 i 和 j. 请注意它们如何取决于 x, y, z. 但是，也就是说 j 取决于 i. 依赖关系很重要，因为你知道树叶没有依赖关系。

如何构建树？

总结一下，这就是我们从原始表达式分解出来的东西。

x = < a b
y = < b c
z = < c d
i = ∧ x y
j = ∨ i z

让我们从下往上看

考虑到依赖关系，叶子显然是最独立的元素。a, b, c 和 d.

让我们考虑到这些独立元素在我们刚才的分解中的所有出现，来构建树的底部(b 和 c 出现两次，我们把它们放两次）。)

a   b   b   c   c   d

现在让我们建立 x, y 和 z 这只取决于 a, b, c 和 d. 我将使用 / 和 \ 用于构建我的ASCII艺术，相当于你的图片线。

  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

现在我们已经看到了。i 只取决于x和y，所以我们现在可以把它放在那里。我们不能添加 j 因为我们需要 i 要先到那里。

      i
      ∧
    /   \
  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

现在，我们只是缺少 j，这取决于 i 和 z.

           j
           ∨
         /   \      
        /     \
      i        \
      ∧         \
   /     \       \
  x       y       z
  <       <       <
 / \     / \     / \
a   b   b   c   c   d

而我们有一个完整的表达式树。正如你所看到的，每个依赖级别都会产生一个树级别。

为了完全准确，一个 广度优先搜索 在这棵树上，将不得不考虑 z 是在同一水平上的 i所以，树的正确表示方式是把 z 高一个层次。

            j
            ∨
         /     \      
        /       \
      i          z
      ∧          <
   /     \      / \
  x       y    c   d
  <       <       
 / \     / \     
a   b   b   c

还有一点，为了让大家完全明白，为了让大家清楚地知道... (a < b) ∧ ( (b < c) ∨ (c < d) )，分解的结果将是。

x = < a b
y = < b c
z = < c d
j = ∨ y z
i = ∧ x j

反过来，也就是你图中的树的结果。

希望这对你今后构建表达树的工作有所帮助。