Build Binary Expression Tree From Infix Expression - Leetcode Solution

Problem Statement: Given a string containing only non-negative integers, operators +, -, *, /, and empty spaces. The string represents a valid infix expression. You need to convert this infix expression into a binary expression tree that takes the infix expression as input and constructs a binary expression tree.

For Example: Input: "3+2*2" Output: + /
3 * /
2 2

Solution: We can solve the problem using a stack and a tree data structure.

Steps:

1. Create an empty stack and an empty tree (root = NULL)
2. Iterate through each character of the expression.
3. If the character is a digit, then create a new node for that digit and push it onto the stack.
4. If the character is an operator, then create a new node for that operator and set its left and right children to be the top two nodes on the stack (pop them from the stack). The new node is then pushed back onto the stack.
5. After iterating through all characters, the top node on the stack is the root of our binary expression tree.

Code:

struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char v) : val(v), left(NULL), right(NULL) {}
};

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

int priority(char c){
    if(c=='+' || c=='-')
        return 1;
    else if(c=='*' || c=='/')
        return 2;
    return 0;
}

TreeNode* constructTree(string s){
    stack<TreeNode*> st;
    TreeNode* root=NULL;

    for(int i=0;i<s.length();i++){
        if(s[i]==' ')
            continue;
        else if(isdigit(s[i])){
            int num=0;
            while(i<s.length() && isdigit(s[i])){
                num=num*10+(s[i]-'0');
                i++;
            }
            i--;
            TreeNode* node=new TreeNode(num+'0');
            st.push(node);
        }
        else if(isOperator(s[i])){
            TreeNode* node=new TreeNode(s[i]);
            while(!st.empty() && st.top()->val!='(' && priority(s[i])<=priority(st.top()->val)){
                node->left=st.top();
                st.pop();
            }
            node->right=st.top();
            st.pop();
            st.push(node);
        }
        else if(s[i]=='('){
            TreeNode* node=new TreeNode(s[i]);
            st.push(node);
        }
        else if(s[i]==')'){
            while(!st.empty() && st.top()->val!='('){
                TreeNode* node=st.top();
                st.pop();
                if(!st.empty() && st.top()->val!='('){
                    node->left=st.top();
                    st.pop();
                }
                st.push(node);
            }
            if(!st.empty() && st.top()->val=='(')
                st.pop();
        }
    }

    while(!st.empty()){
        root=st.top();
        st.pop();
    }
    return root;
}

The code above uses a stack to convert the infix expression to postfix expression and then uses the postfix expression to construct the binary expression tree.

1