CODEWITHSUNDEEP
c++data-structuresuser-inputmathematical-expressionsboolean-algebra
user3208209
user3208209

Reputation: 47

What is a good data structure for processing boolean algebra equations?

I'm creating a program that will calculate the truth values for a boolean algebra equation. I need to find a good data structure that will be able to correctly process the order of operations of an equation involving AND, OR, NOT, and parentheses as well. The equation will be typed in by the user.

Upvotes: 4

Views: 1503

Answers (2)

Damien Black
Damien Black

Reputation: 5647

Any type of "order of operation" objects are usually held in trees. It would look like this:

  • You process the textual representation finding the highest priority items first
  • Each simple statement (true OR false for example) would be put into a node
  • You could have different types of nodes for the different operations
  • The nodes themselves could be inserted into other nodes, to make complex statements

A final tree representation may end up looking something like this:

     OR
  ___|__
  |    |
true  AND
    ___|___
    |     |
 false   NOT
          |
         true

That would represent the statement:

true OR (false AND NOT true)

Upvotes: 2

user2033018
user2033018

Reputation:

A binary tree is the answer here.

Say you have expression A and B or C, then the representation you're looking for would resemble this:

    or
   / \
 and  C
 / \
A   B

Note that the tree already encodes the precedence rules.

A simple solution would look like this:

class tree_node
{
public:
    virtual ~tree_node() = default;
    virtual bool evaluate() = 0;
};

class false_literal_node : public tree_node
{
    bool evaluate() override
    {
        return false;
    }
};

// Same goes for `true` literal...

class variable_node : public tree_node
{
    bool evaluate() override
    {
        return value;
    }

    bool value;
};

class conjunction_node : public tree_node
{
    bool evaluate() override
    {
        return lhs->evaluate() && rhs->evaluate();
    }

    std::unique_ptr<tree_node> lhs;
    std::unique_ptr<tree_node> rhs;
};

You get the idea...

Evaluating an expression would then be to parse it (which would get you a tree) and then calling evaluate on the root.

Upvotes: 1

Related Questions