C++ Notes: Trees - Expression Tree Class

Here is a simple representation of expression trees that handles integer constants and binary (two-operand) operators. It doesn't take advantage of inheritance. Whenever a case statement appears in a function (as in eval), the question of whether this should be implemented with inheritance and virtual functions (which don't need the case statement).

The eval function evaluates trees recursively. It would be somewhat harder to do it iteratively.

The header file

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 

// exprnode/exprnode.h - Example expression tree
// 2004-02-25 Fred Swartz
#ifndef EXPRNODE_H
#define EXPRNODE_H

#include <cstdlib>  // for NULL
using namespace std;

//====================================== class ExprNode
class ExprNode {
 public:
    ExprNode(char oper, ExprNode* left, ExprNode* right);
    ExprNode(int val);
    int eval() const; // Evaluate expr tree. Return result.
    
 private:
    char      _op;    // one of +, -, *, /, #
    int       _value; // integer value used for constants.
    ExprNode* _left;  // left subtree
    ExprNode* _right; // right subtree
};
#endif

The implementation file

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 

// exprnode/exprnode.cpp - Example expression tree
// 2004-02-25 Fred Swartz

#include <cstdlib>  // for NULL
using namespace std;

#include "exprnode.h"
   
//============================================= ExprNode constructor
    // Constructs node for a binary operator.
ExprNode::ExprNode(char oper, ExprNode* left, ExprNode* right) {
    _op    = oper;
    _left  = left;
    _right = right;
}
   
//============================================== ExprNode constructor
    // Constructs a node for an integer constant
ExprNode::ExprNode(int v) {
    _op    = '#';
    _value = v;
    _left  = NULL;
    _right = NULL;
}

//===================================================== ExprNode::eval
int ExprNode::eval() const {
    // Recursively evaluate expression tree and return result.
    int result;
    switch (_op) {
        case '+': 
                result = _left->eval() + _right->eval();
                break;
        case '-': 
                result = _left->eval() - _right->eval();
                break;
        case '#': 
                result = _value;  // an integer constant
                break;
     }
     return result;
}

The test file

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 

// exprnode/exprnode-test.cpp
// 2004-02-25 Fred Swartz

#include <iostream>
using namespace std;

#include "exprnode.h"

//============================================================== main
int main() {
    // Example expression and evaluation.
    ExprNode* add = new ExprNode('+', new ExprNode(5), new ExprNode(6));
    ExprNode* sub = new ExprNode('-', add, new ExprNode(2));
    cout << sub->eval() << endl;
    
    system("PAUSE");
    return 0;
}

Programming extensions

  1. Add muliplication and division. Check that division by zero isn't attempted.
  2. Write one of the following functions, which will produce a string from the expression tree. Model it after the eval function. To simplify this problem, you can assume that a function exists which converts an int to a string with this prototype. string intToString(int i);