# 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.
   - `string toPrefix();`
   - `string toInfix();`
   - `string toPostfix();`
   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);`