Construction of an Expression Tree

By | March 16, 2022
Construction of an Expression Tree

Problem

Given a postfix expression, the task is to generate an expression tree from it and return the infix notation of the expression tree.

Example:

Below is the expression tree for the given expression: 2 + 3

Sample Input

2 3 +

Sample Output

The infix expression is

2 + 3

Explanation

Below is the expression tree for the given postfix expression

Vamware
           +
         /   \
        2     3

Approach

We can traverse the given string of expressions and use a stack data structure to keep track of the previous two operands. Whenever we find an operator, just pop both of them, evaluate and push them again into the stack. The element remaining in the stack once the string finishes will be the required answer.

Complexity Analysis

The time complexity would be O(N), and the space complexity would also be O(N) due to stack.

Vamware

C++ Programming 

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

struct TreeNode
{
    char val;
    TreeNode* left, *right;
};

// if character is operator
bool isOperator(char c)
{
    if (c == '+' || c == '-' ||
            c == '*' || c == '/' ||
            c == '^')

        return true;
    return false;
}

// get infix expression
void inorder(TreeNode *root)
{
    if(root)
    {   
        if(isOperator(root->val)) cout<<"(";
        inorder(root->left);

        cout<<root->val;
        inorder(root->right);

        if(isOperator(root->val))
            cout<<")";
    }
} 

// create node
TreeNode* createNode(char c)
{
    TreeNode *root = new TreeNode;
    root->left = root->right = NULL;
    root->val = c;
    return root;
};

TreeNode* getTree(char postfix[])
{
    stack<TreeNode *> st;
    TreeNode *root, *left, *right;

    // Traverse the string
    for (int i=0; i<strlen(postfix); i++)
    {
        // If operand
        if (!isOperator(postfix[i]))
        {
            root = createNode(postfix[i]);
            st.push(root);
        }

        else // if operator
        {
            root = createNode(postfix[i]);

            // Pop two top nodes
            right = st.top();
            st.pop();   

            left = st.top();
            st.pop();

             // make them left and righ childs
            root->right = right;
            root->left = left;

            // push into the stack
            st.push(root);
        }
    }
    root = st.top();
    st.pop();
    return root;
} 

int main()
{
    char postfix[] = "ab+ef*g*-";
    TreeNode* r = getTree(postfix);
    cout<<"The infix expression is \n";
    inorder(r);
    return 0;
}

Output

The infix expression is
((a + b )- ((e * f )* g ))

Java Programming

import java.util.Stack;

class Node {
    char val;
    Node left, right;

    Node(char item) {
        val = item;
        left = right = null;
    }
}

class Solution {

    // check if character is operator
    boolean isOperator(char c) {
        if (c == '+' || c == '-'
                || c == '*' || c == '/'
                || c == '^') {
            return true;
        }
        return false;
    }

    // do inorder traversal
    void inorder(Node root) {
        if (root != null) {
            if(isOperator(root.val)) 
                 System.out.print("(");
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
            if(isOperator(root.val)) 
                 System.out.print(")");
        }
    }

    Node getTree(char postfix[]) {
        Stack<Node> st = new Stack<Node>();
        Node root, left, right;

        // Traverse the string
        for (int i = 0; i < postfix.length; i++) {
            // If operand, push into stack
            if (!isOperator(postfix[i])) 
            {
                root = new Node(postfix[i]);
                st.push(root);
            } 
           else // if operator
            {
                root = new Node(postfix[i]);

                // Pop two top nodes
                right = st.pop();     
                left = st.pop();

                // make them left and right children
                root.right = right;
                root.left = left;

                // push the result to stack
                st.push(root);
            }
        }
        root = st.peek();
        st.pop();
        return root;
    }

    public static void main(String args[]) {
        Solution TreeNode = new Solution();
        String postfix = "ab+ef*g*-";
        char[] charArray = postfix.toCharArray();
        Node root = TreeNode.getTree(charArray);
        System.out.println("The infix expression is");
        TreeNode.inorder(root);
    }
}

Output

The infix expression is
((a + b )- ((e * f )* g ))

Python Programming

class TreeNode:
    def __init__(self , value):
        self.value = value
        self.left = None
        self.right = None

# check if character is an operator
def isOperator(c):
    if (c == '+' or c == '-' or c == '*'
        or c == '/' or c == '^'):
        return True
    else:
        return False

# do inorder traversal
def inorder(root):
    if root is not None:
        if(isOperator(root.value)):
            print("(",end="")

        inorder(root.left)
        print(root.value,end=" ")

        inorder(root.right)
        if(isOperator(root.value)):
            print(")",end="")

def getTree(postfix):
    st = []

    # Traverse the string
    for c in postfix :
        # if operand, simply push into st
        if not isOperator(c):
            root = TreeNode(c)
            st.append(root)

        # Operator
        else:
            # Pop two top nodes
            root = TreeNode(c)
            right = st.pop()
            left = st.pop()
            # make them children
            root.right = right
            root.left = left

            # Add this subexpression to st
            st.append(root)

    # Only element will be the root of the expression tree
    root = st.pop()
    return root

postfix = "ab+ef*g*-"
root = getTree(postfix)
print("The infix expression is")
inorder(root)

Output

The infix expression is
((a + b )- ((e * f )* g ))

Conclusion

To convert the given postfix expression into an infix expression, we have used a stack to keep track of operands. As we have used stack, the time and space complexity would be O(N). We have implemented the given problem in three different programming languages, namely C++, Python, and Java. Moreover, we have mentioned an approach to converting a postfix expression into an infix expression.

Hopefully, this article has helped you get familiar with the code to convert a postfix expression to infix. In case you have any queries, feel free to share them with us in the comments section below.

Happy learning!

People are also reading:

Author: Vinay Singh

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.