0
$\begingroup$

I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g.

but have issues with the commutativity. Assuming the expression is

then the tree would look like this:

       xor
       /\
     xor b
     /\
   xor true
   /\
true a

The expression can be simplified:

but I don't know how to apply the above rule to this tree since it is never directly applicable to one of the subtrees. Is there a better way than having to rotate the tree in all possible orders?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Convert to list, sort (so that the same variables/values are grouped together), apply rules, convert back to binary tree. $\endgroup$
    – user114966
    Commented Aug 21, 2020 at 18:15
  • 1
    $\begingroup$ @Dmitry There's no need to sort, using a hashmap you can do it in $O(n)$ by only keeping track of the parity of each element. $\endgroup$
    – orlp
    Commented Aug 21, 2020 at 21:45
  • $\begingroup$ @twinrix another idea is to allow ($\lnot a$) in your tree. That way you could use the reduction $true \oplus x = x \oplus true = \lnot x$ ( and ofc $false \oplus x = x$). You would end up with: xor(true, a) => not(a), xor(not(a),true) => a, xor(a,b) as final result. Other rules are $x\oplus \lnot x = true$, $x \oplus x = false$. $\endgroup$
    – plshelp
    Commented Aug 23, 2020 at 0:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.