4

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
user3208209
  • 47
  • 6
  • When I worked on a calculator in school, we converted the input into RPN and then calculated using a stack. – clcto Mar 10 '14 at 18:17
  • You can parse and evaluate using a [recursive descent parser](http://en.wikipedia.org/wiki/Recursive_descent_parser) and no explicit data structure like a tree or stack. – Jim Mischel Mar 10 '14 at 21:51

2 Answers2

2

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)
Damien Black
  • 5,579
  • 18
  • 24
1

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.