Expression Tree

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand so for example expression tree for 3 + ((5+9)*2) would be:

Inorder traversal of expression tree produces infix version of given postfix expression (same with preorder traversal it gives prefix expression)

Evaluating the expression represented by expression tree:

Let t be the expression tree
If  t is not null then
      If t.value is operand then  
                Return  t.value
      A = solve(t.left)
      B = solve(t.right)
 
      // calculate applies operator 't.value' 
      // on A and B, and returns value
      Return calculate(A, B, t.value)

Construction of Expression Tree:
Now For constructing expression tree we use a stack. We loop through input expression and do following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node again.
At the end only element of stack will be root of expression tree.

Below is the implementation :

C/C++

// C++ program for expression tree 
#include<bits/stdc++.h> 
using namespace std; 
  
// An expression tree node 
struct et 
{ 
    char value; 
    et* left, *right; 
}; 
  
// A utility function to check if 'c' 
// is an operator 
bool isOperator(char c) 
{ 
    if (c == '+' || c == '-' || 
            c == '*' || c == '/' || 
            c == '^') 
        return true; 
    return false; 
} 
  
// Utility function to do inorder traversal 
void inorder(et *t) 
{ 
    if(t) 
    { 
        inorder(t->left); 
        printf("%c ", t->value); 
        inorder(t->right); 
    } 
} 
  
// A utility function to create a new node 
et* newNode(int v) 
{ 
    et *temp = new et; 
    temp->left = temp->right = NULL; 
    temp->value = v; 
    return temp; 
}; 
  
// Returns root of constructed tree for given 
// postfix expression 
et* constructTree(char postfix[]) 
{ 
    stack<et *> st; 
    et *t, *t1, *t2; 
  
    // Traverse through every character of 
    // input expression 
    for (int i=0; i<strlen(postfix); i++) 
    { 
        // If operand, simply push into stack 
        if (!isOperator(postfix[i])) 
        { 
            t = newNode(postfix[i]); 
            st.push(t); 
        } 
        else // operator 
        { 
            t = newNode(postfix[i]); 
  
            // Pop two top nodes 
            t1 = st.top(); // Store top 
            st.pop();      // Remove top 
            t2 = st.top(); 
            st.pop(); 
  
            //  make them children 
            t->right = t1; 
            t->left = t2; 
  
            // Add this subexpression to stack 
            st.push(t); 
        } 
    } 
  
    //  only element will be root of expression 
    // tree 
    t = st.top(); 
    st.pop(); 
  
    return t; 
} 
  
// Driver program to test above 
int main() 
{ 
    char postfix[] = "ab+ef*g*-"; 
    et* r = constructTree(postfix); 
    printf("infix expression is
"); 
    inorder(r); 
    return 0; 
} 

Java

// Java program to construct an expression tree 
  
import java.util.Stack; 
  
// Java program for expression tree 
class Node { 
  
    char value; 
    Node left, right; 
  
    Node(char item) { 
        value = item; 
        left = right = null; 
    } 
} 
  
class ExpressionTree { 
  
    // A utility function to check if 'c' 
    // is an operator 
  
    boolean isOperator(char c) { 
        if (c == '+' || c == '-'
                || c == '*' || c == '/'
                || c == '^') { 
            return true; 
        } 
        return false; 
    } 
  
    // Utility function to do inorder traversal 
    void inorder(Node t) { 
        if (t != null) { 
            inorder(t.left); 
            System.out.print(t.value + " "); 
            inorder(t.right); 
        } 
    } 
  
    // Returns root of constructed tree for given 
    // postfix expression 
    Node constructTree(char postfix[]) { 
        Stack<Node> st = new Stack(); 
        Node t, t1, t2; 
  
        // Traverse through every character of 
        // input expression 
        for (int i = 0; i < postfix.length; i++) { 
  
            // If operand, simply push into stack 
            if (!isOperator(postfix[i])) { 
                t = new Node(postfix[i]); 
                st.push(t); 
            } else // operator 
            { 
                t = new Node(postfix[i]); 
  
                // Pop two top nodes 
                // Store top 
                t1 = st.pop();      // Remove top 
                t2 = st.pop(); 
  
                //  make them children 
                t.right = t1; 
                t.left = t2; 
  
                // System.out.println(t1 + "" + t2); 
                // Add this subexpression to stack 
                st.push(t); 
            } 
        } 
  
        //  only element will be root of expression 
        // tree 
        t = st.peek(); 
        st.pop(); 
  
        return t; 
    } 
  
    public static void main(String args[]) { 
  
        ExpressionTree et = new ExpressionTree(); 
        String postfix = "ab+ef*g*-"; 
        char[] charArray = postfix.toCharArray(); 
        Node root = et.constructTree(charArray); 
        System.out.println("infix expression is"); 
        et.inorder(root); 
  
    } 
} 
  
// This code has been contributed by Mayank Jaiswal 

Python

# Python program for expression tree 
  
# An expression tree node 
class Et: 
  
    # Constructor to create a node 
    def __init__(self , value): 
        self.value = value 
        self.left = None
        self.right = None
  
# A utility function to check if 'c' 
# is an operator 
def isOperator(c): 
    if (c == '+' or c == '-' or c == '*'
        or c == '/' or c == '^'): 
        return True
    else: 
        return False
  
# A utility function to do inorder traversal 
def inorder(t): 
    if t is not None: 
        inorder(t.left) 
        print t.value, 
        inorder(t.right) 
  
# Returns root of constructed tree for 
# given postfix expression 
def constructTree(postfix): 
    stack = [] 
  
    # Traverse through every character of input expression 
    for char in postfix : 
  
        # if operand, simply push into stack 
        if not isOperator(char): 
            t = Et(char) 
            stack.append(t) 
  
        # Operator 
        else: 
  
            # Pop two top nodes 
            t = Et(char) 
            t1 = stack.pop() 
            t2 = stack.pop() 
                
            # make them children 
            t.right = t1 
            t.left = t2 
              
            # Add this subexpression to stack 
            stack.append(t) 
  
    # Only element  will be the root of expression tree 
    t = stack.pop() 
     
    return t 
  
# Driver program to test above 
postfix = "ab+ef*g*-"
r = constructTree(postfix) 
print "Infix expression is"
inorder(r) 

C#

// C# program to construct an expression tree 
using System; 
using System.Collections; 
  
public class Node 
{ 
  
    public char value; 
    public Node left, right; 
  
    public Node(char item) 
    { 
        value = item; 
        left = right = null; 
    } 
} 
  
class ExpressionTree  
{ 
  
    // A utility function to check if 'c' 
    // is an operator 
    Boolean isOperator(char c) 
    { 
        if (c == '+' || c == '-' || c == '*'
            || c == '/' || c == '^') 
        { 
            return true; 
        } 
        return false; 
    } 
  
    // Utility function to do inorder traversal 
    void inorder(Node t)  
    { 
        if (t != null)  
        { 
            inorder(t.left); 
            Console.Write(t.value + " "); 
            inorder(t.right); 
        } 
    } 
  
    // Returns root of constructed tree for given 
    // postfix expression 
    Node constructTree(char []postfix) 
    { 
        Stack st = new Stack(); 
        Node t, t1, t2; 
  
        // Traverse through every character of 
        // input expression 
        for (int i = 0; i < postfix.Length; i++) 
        { 
  
            // If operand, simply Push into stack 
            if (!isOperator(postfix[i]))  
            { 
                t = new Node(postfix[i]); 
                st.Push(t); 
            }  
            else // operator 
            { 
                t = new Node(postfix[i]); 
  
                // Pop two top nodes 
                // Store top 
                t1 = (Node)st.Pop();     // Remove top 
                t2 = (Node)st.Pop(); 
  
                // make them children 
                t.right = t1; 
                t.left = t2; 
  
                // System.out.println(t1 + "" + t2); 
                // Add this subexpression to stack 
                st.Push(t); 
            } 
        } 
  
        // only element will be root of 
        // expression tree 
        t = (Node)st.Peek(); 
        st.Pop(); 
  
        return t; 
    } 
  
    // Driver code 
    public static void Main(String []args)  
    { 
        ExpressionTree et = new ExpressionTree(); 
        String postfix = "ab+ef*g*-"; 
        char[] charArray = postfix.ToCharArray(); 
        Node root = et.constructTree(charArray); 
        Console.WriteLine("infix expression is"); 
        et.inorder(root); 
    } 
} 
  
// This code has been contributed by Arnab Kundu 

Output:

infix expression is
a + b - e * f * g

C/C++

Java

Python

C#

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books