Construction of an Expression Tree

Posted in

Vinay Khatri
Last updated on September 17, 2024

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: