C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Construct an Expression Tree for an Infix Expression Program to Construct an Expression Tree for an Infix Expression This is a C++ Program to construct an Expression tree for an Infix Expression. A binary expression tree is a specific application of a binary tree to evaluate certain expressions. Two common types of expressions that a binary expression tree can represent are algebraic[1] and boolean. These trees can represent expressions that contain both unary and binary operators.In general, expression trees are a special kind of binary tree. A binary tree is a tree in which all nodes contain zero, one or two children. This restricted structure simplifies the programmatic processing of Expression trees #include <cstdlib> #include <iostream> #include <sstream> #include <string> #include <stack> #include <exception> using namespace std; class ExpressionElementNode { public: virtual double value() = 0; // Return the value of this node. }; class NumericElementNode: public ExpressionElementNode { private: double number; NumericElementNode(const NumericElementNode& n); NumericElementNode(); NumericElementNode&operator=(const NumericElementNode& n); public: NumericElementNode(double val); virtual double value(); }; inline NumericElementNode::NumericElementNode(double val) : number(val) { } inline double NumericElementNode::value() { return number; } class BinaryOperationNode: public ExpressionElementNode { private: char binary_op; ExpressionElementNode *left; ExpressionElementNode *right; BinaryOperationNode(const BinaryOperationNode& n); BinaryOperationNode(); BinaryOperationNode &operator=(const BinaryOperationNode& n); public: BinaryOperationNode(char op, ExpressionElementNode *l, ExpressionElementNode *r); virtual double value(); }; inline BinaryOperationNode::BinaryOperationNode(char op, ExpressionElementNode *l, ExpressionElementNode *r) : binary_op(op), left(l), right(r) { } double BinaryOperationNode::value() { // To get the value, compute the value of the left and // right operands, and combine them with the operator. double leftVal = left->value(); double rightVal = right->value(); double result; switch (binary_op) { case '+': result = leftVal + rightVal; break; case '-': result = leftVal - rightVal; break; case '*': result = leftVal * rightVal; break; case '/': result = leftVal / rightVal; break; } return result; } class ExpressionElementNode; class BinaryOperationNode; class BinaryExpressionBuilder { private: // holds either (, +, -, /, or * std::stack<char> operatorStack; // operandStack is made up of BinaryOperationNodes and NumericElementNode std::stack<ExpressionElementNode *> operandStack; void processOperator(char op); void processRightParenthesis(); void doBinary(char op); int precedence(char op); public: class NotWellFormed: public std::exception { public: virtual const char* what() const throw () { return "The expression is not valid"; } }; BinaryOperationNode *parse(std::string& istr) throw (NotWellFormed); }; int BinaryExpressionBuilder::precedence(char op) { enum { lowest, mid, highest }; switch (op) { case '+': case '-': return mid; case '/': case '*': return highest; default: return lowest; } } // Input: +, -, /, or * // creates BinaryOperationNode's from all preceding BinaryOperationNode *BinaryExpressionBuilder::parse(std::string& str) throw (NotWellFormed) { istringstream istr(str); char token; while (istr >> token) { switch (token) { case '+': case '-': case '*': case '/': processOperator(token); break; case ')': processRightParenthesis(); break; case '(': operatorStack.push(token); break; default: // If it is not an operator, it must be a number. // Since token is only a char in width, we put it back, // and get the complete number as a double. istr.putback(token); double number; istr >> number; NumericElementNode *newNode = new NumericElementNode(number); operandStack.push(newNode); continue; } // end switch } // end while while (!operatorStack.empty()) { doBinary(operatorStack.top()); operatorStack.pop(); } // Invariant: At this point the operandStack should have only one element // operandStack.size() == 1 // otherwise, the expression is not well formed. if (operandStack.size() != 1) { throw NotWellFormed(); } ExpressionElementNode *p = operandStack.top(); return static_cast<BinaryOperationNode *> (p); } void BinaryExpressionBuilder::processOperator(char op) { // pop operators with higher precedence and create their BinaryOperationNode int opPrecedence = precedence(op); while ((!operatorStack.empty()) && (opPrecedence <= precedence( operatorStack.top()))) { doBinary(operatorStack.top()); operatorStack.pop(); } // lastly push the operator passed onto the operatorStack operatorStack.push(op); } void BinaryExpressionBuilder::processRightParenthesis() { while (!operatorStack.empty() && operatorStack.top() != '(') { doBinary(operatorStack.top()); operatorStack.pop(); } operatorStack.pop(); // remove '(' } // Creates a BinaryOperationNode from the top two operands on operandStack // These top two operands are removed (poped), and the new BinaryOperation // takes their place on the top of the stack. void BinaryExpressionBuilder::doBinary(char op) { ExpressionElementNode *right = operandStack.top(); operandStack.pop(); ExpressionElementNode *left = operandStack.top(); operandStack.pop(); BinaryOperationNode *p = new BinaryOperationNode(operatorStack.top(), left, right); operandStack.push(p); } int main(int argc, char** argv) { NumericElementNode num1(10); NumericElementNode num2(20); BinaryOperationNode n('+', &num1, &num2); BinaryExpressionBuilder b; cout << "Enter expression" << endl; string expression; getline(cin, expression); BinaryOperationNode *root = b.parse(expression); cout << " result = " << root->value(); return 0; }
