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.
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 |
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; } |
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; } |
eval
function.
string toPrefix();
string toInfix();
string toPostfix();
string intToString(int i);