C++: Data Structures: Expression Tree Struct

This code is a typical non-OOP solution to the expression tree problem.

//======================================= ExprNode
struct ExprNode {
    char      op;    // one of +, -, *, /, #
    int       value; // integer value
    ExprNode* left;  // left subtree
    ExprNode* right; // right subtree
};



//======================================= eval
int eval(ExprNode* x) {
    // Recursively evaluate expression tree.
    int result;
    switch (x->op) {
       case '+': result = eval(x->left) + eval(x->right);
               break;
       case '-': result = eval(x->left) - eval(x->right);
               break;
       case '/': result = eval(x->left) * eval(x->right);
               break;
       case '#': result = x->value;  // an integer constant
    }
    return result;
}

Solutions like this are quite common in non-OOP programs, however OOP programming offers several advantages:

Integrity of the the node can be ensured with constructors and methods as in the next example: Expression Tree Class - 1.
Inheritance can be used to distinguish between different types of nodes, where each kind overrides the eval function to process the node as it should. A hint that inheritance should be used is when a processing function has a case statement in it to determine what kind of object it is.