C++ program to construct an expression tree

In this tutorial, we will see how to construct an expression tree in C++. We will construct the tree from a given string of postfix expression. But first, let’s see what is an expression tree.

A tree in which the root is an operator and the children are operands is an expression tree. e.g.

                                          (*)
                                      /         \
                                    (/)         (-)
                                  /     \      /    \
                                (+)      (+)  F      G
                               /   \    /   \
                              A     B  C     D

In the above tree, all the operands are connected through an operator which thus forms:

A + B / C + D * F - G 
// result

Algorithm

• We will call a function constructTree() with postfix string, a stack of structure ExpressionTree’s pointer, size of string postfix and value 0 for iterator ‘i’.
• In the constructTree() function we check one by one if the current character is operator or operand till ‘i’ is smaller than the size of the string.
• To check for operators we will pass the character to isOperator() function which will check for different operators.
• If the character is not an operator just push it into the stack ‘st’.
• Else we pop top two elements(which are operands or expressions) and put them into right and left subtree of the operator, and push the final expression back into the stack.
• Then we recursively call constructTree() for the remaining elements.
• When the string ends return the top of the stack as it contains the head of the expression tree.
• With the head obtained print the tree by calling InorderPrint() function.

Implementation of the algorithm

Below is the full code implementing the algorithm:

#include<bits/stdc++.h> 
using namespace std; 

struct ExpressionTree 
{ 
  char value; 
  ExpressionTree* left, *right; 
  
  ExpressionTree(char x){
      this->value =x;
      this->left = this->right = NULL;
  }
}; 


bool isOperator(char c) 
{ 
  if (c == '+' || c == '-' || 
      c == '*' || c == '/')
    return true; 
    
  return false; 
} 


void InorderPrint(ExpressionTree *head) 
{ 
  if(head) 
  { 
    InorderPrint(head->left); 
    
    cout<<head->value<<' '; 
    
    InorderPrint(head->right); 
  } 
} 


ExpressionTree* constructTree(string postfix ,stack<ExpressionTree*> &st,
                                int n,int i) 
{ 
    if(i>=n) return NULL;
    
  if (!isOperator(postfix[i])) 
    { 
      ExpressionTree *temp = new ExpressionTree(postfix[i]); 
      st.push(temp); 
    } 
  else 
    { 
      ExpressionTree *temp = new ExpressionTree(postfix[i]);

      temp->right = st.top(); 
      st.pop();
      temp->left = st.top();
      st.pop();

      st.push(temp); 
    } 
    
  constructTree(postfix,st,n,i+1);

  return st.top(); 
  //return head of ExpressionTree
} 


int main() 
{ 
  string postfix = "AB+CD+/FG-*"; 
  stack<ExpressionTree*> st;
  
  ExpressionTree* head = constructTree(postfix,st,postfix.size(),0); 
  
  cout<<"Expression is : "; 
  InorderPrint(head); 
  
  return 0; 
} 

OUTPUT:

Expression is : A + B / C + D * F - G

The algorithm works in O(n) time complexity.

That’s it hope you understood.