Construction of an Expression Tree

Posted in

Construction of an Expression Tree

Vinay Khatri
Last updated on September 19, 2022

    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

               +
             /   \
            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.

    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 an 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:

    Tags:
    tree

    Leave a Comment on this Post

    0 Comments