C++ Program to Create Expression Tree from 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

Here is source code of the C++ Program to Construct an Expression Tree for an Infix Expression. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <string>
  5. #include <stack>
  6. #include <exception>
  7.  
  8. using namespace std;
  9.  
  10. class ExpressionElementNode
  11. {
  12.     public:
  13.         virtual double value() = 0; // Return the value of this node.
  14. };
  15.  
  16. class NumericElementNode: public ExpressionElementNode
  17. {
  18.  
  19.     private:
  20.         double number;
  21.         NumericElementNode(const NumericElementNode& n);
  22.         NumericElementNode();
  23.         NumericElementNode&operator=(const NumericElementNode& n);
  24.     public:
  25.  
  26.         NumericElementNode(double val);
  27.         virtual double value();
  28. };
  29.  
  30. inline NumericElementNode::NumericElementNode(double val) :
  31.     number(val)
  32. {
  33. }
  34.  
  35. inline double NumericElementNode::value()
  36. {
  37.     return number;
  38. }
  39.  
  40. class BinaryOperationNode: public ExpressionElementNode
  41. {
  42.  
  43.     private:
  44.  
  45.         char binary_op;
  46.  
  47.         ExpressionElementNode *left;
  48.         ExpressionElementNode *right;
  49.  
  50.         BinaryOperationNode(const BinaryOperationNode& n);
  51.         BinaryOperationNode();
  52.         BinaryOperationNode &operator=(const BinaryOperationNode& n);
  53.  
  54.     public:
  55.         BinaryOperationNode(char op, ExpressionElementNode *l,
  56.                 ExpressionElementNode *r);
  57.  
  58.         virtual double value();
  59. };
  60.  
  61. inline BinaryOperationNode::BinaryOperationNode(char op,
  62.         ExpressionElementNode *l, ExpressionElementNode *r) :
  63.     binary_op(op), left(l), right(r)
  64. {
  65. }
  66. double BinaryOperationNode::value()
  67. {
  68.     // To get the value, compute the value of the left and
  69.     // right operands, and combine them with the operator.
  70.     double leftVal = left->value();
  71.  
  72.     double rightVal = right->value();
  73.  
  74.     double result;
  75.  
  76.     switch (binary_op)
  77.     {
  78.  
  79.         case '+':
  80.             result = leftVal + rightVal;
  81.             break;
  82.  
  83.         case '-':
  84.             result = leftVal - rightVal;
  85.             break;
  86.  
  87.         case '*':
  88.             result = leftVal * rightVal;
  89.             break;
  90.  
  91.         case '/':
  92.             result = leftVal / rightVal;
  93.             break;
  94.     }
  95.  
  96.     return result;
  97. }
  98. class ExpressionElementNode;
  99. class BinaryOperationNode;
  100.  
  101. class BinaryExpressionBuilder
  102. {
  103.  
  104.     private:
  105.         // holds either (, +, -, /, or *
  106.         std::stack<char> operatorStack;
  107.  
  108.         // operandStack is made up of BinaryOperationNodes and NumericElementNode
  109.         std::stack<ExpressionElementNode *> operandStack;
  110.  
  111.         void processOperator(char op);
  112.         void processRightParenthesis();
  113.  
  114.         void doBinary(char op);
  115.  
  116.         int precedence(char op);
  117.  
  118.     public:
  119.  
  120.         class NotWellFormed: public std::exception
  121.         {
  122.  
  123.             public:
  124.                 virtual const char* what() const throw ()
  125.                 {
  126.                     return "The expression is not valid";
  127.                 }
  128.         };
  129.  
  130.         BinaryOperationNode *parse(std::string& istr) throw (NotWellFormed);
  131. };
  132. int BinaryExpressionBuilder::precedence(char op)
  133. {
  134.     enum
  135.     {
  136.         lowest, mid, highest
  137.     };
  138.  
  139.     switch (op)
  140.     {
  141.  
  142.         case '+':
  143.         case '-':
  144.             return mid;
  145.  
  146.         case '/':
  147.         case '*':
  148.             return highest;
  149.  
  150.         default:
  151.             return lowest;
  152.     }
  153. }
  154.  
  155. // Input: +, -, /, or *
  156. // creates BinaryOperationNode's from all preceding
  157. BinaryOperationNode *BinaryExpressionBuilder::parse(std::string& str)
  158.         throw (NotWellFormed)
  159. {
  160.     istringstream istr(str);
  161.     char token;
  162.  
  163.     while (istr >> token)
  164.     {
  165.  
  166.         switch (token)
  167.         {
  168.  
  169.             case '+':
  170.             case '-':
  171.             case '*':
  172.             case '/':
  173.                 processOperator(token);
  174.                 break;
  175.  
  176.             case ')':
  177.                 processRightParenthesis();
  178.                 break;
  179.  
  180.             case '(':
  181.                 operatorStack.push(token);
  182.                 break;
  183.  
  184.             default:
  185.                 // If it is not an operator, it must be a number.
  186.                 // Since token is only a char in width, we put it back,
  187.                 // and get the complete number as a double.
  188.                 istr.putback(token);
  189.                 double number;
  190.  
  191.                 istr >> number;
  192.  
  193.                 NumericElementNode *newNode = new NumericElementNode(number);
  194.                 operandStack.push(newNode);
  195.  
  196.                 continue;
  197.         } // end switch
  198.     } // end while
  199.  
  200.     while (!operatorStack.empty())
  201.     {
  202.  
  203.         doBinary(operatorStack.top());
  204.         operatorStack.pop();
  205.     }
  206.  
  207.     // Invariant: At this point the operandStack should have only one element
  208.     //     operandStack.size() == 1
  209.     // otherwise, the expression is not well formed.
  210.     if (operandStack.size() != 1)
  211.     {
  212.  
  213.         throw NotWellFormed();
  214.     }
  215.  
  216.     ExpressionElementNode *p = operandStack.top();
  217.  
  218.     return static_cast<BinaryOperationNode *> (p);
  219. }
  220.  
  221. void BinaryExpressionBuilder::processOperator(char op)
  222. {
  223.     // pop operators with higher precedence and create their BinaryOperationNode
  224.     int opPrecedence = precedence(op);
  225.  
  226.     while ((!operatorStack.empty()) && (opPrecedence <= precedence(
  227.             operatorStack.top())))
  228.     {
  229.  
  230.         doBinary(operatorStack.top());
  231.         operatorStack.pop();
  232.     }
  233.  
  234.     // lastly push the operator passed onto the operatorStack
  235.     operatorStack.push(op);
  236. }
  237.  
  238. void BinaryExpressionBuilder::processRightParenthesis()
  239. {
  240.     while (!operatorStack.empty() && operatorStack.top() != '(')
  241.     {
  242.  
  243.         doBinary(operatorStack.top());
  244.         operatorStack.pop();
  245.     }
  246.  
  247.     operatorStack.pop(); // remove '('
  248. }
  249.  
  250. // Creates a BinaryOperationNode from the top two operands on operandStack
  251. // These top two operands are removed (poped), and the new BinaryOperation
  252. // takes their place on the top of the stack.
  253. void BinaryExpressionBuilder::doBinary(char op)
  254. {
  255.     ExpressionElementNode *right = operandStack.top();
  256.  
  257.     operandStack.pop();
  258.  
  259.     ExpressionElementNode *left = operandStack.top();
  260.  
  261.     operandStack.pop();
  262.  
  263.     BinaryOperationNode *p = new BinaryOperationNode(operatorStack.top(), left,
  264.             right);
  265.  
  266.     operandStack.push(p);
  267. }
  268. int main(int argc, char** argv)
  269. {
  270.  
  271.     NumericElementNode num1(10);
  272.     NumericElementNode num2(20);
  273.     BinaryOperationNode n('+', &num1, &num2);
  274.  
  275.     BinaryExpressionBuilder b;
  276.  
  277.     cout << "Enter expression" << endl;
  278.  
  279.     string expression;
  280.     getline(cin, expression);
  281.  
  282.     BinaryOperationNode *root = b.parse(expression);
  283.  
  284.     cout << " result = " << root->value();
  285.     return 0;
  286. }

Output:

$ g++ ExpressionTreeInfix.cpp
$ a.out
 
Enter expression
2+3*5
result = 17
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.