Construction of an expression tree
Construct an expression tree from a given postfix notation and print the infix notation.
The binary expression tree is a binary tree whose leaves are operands, such as constants or variable names, and the other nodes contain operators.
For example, the postfix notation a b + c d e + * * results in the following expression tree. The corresponding infix notation is (a+b)*(c*(d+e)) which can be produced by traversing the expression tree in an inorder fashion. However, an opening and closing parenthesis must be added at the beginning and end of each expression (every subtree represents a subexpression).
The construction of the expression tree takes place by reading the postfix expression one symbol at a time. If the symbol is an operand, a new binary tree node is created, and its pointer is pushed onto a stack. If the symbol is an operator, the pointers to two trees, x and y, are popped from the stack, and a new tree whose root is the operator and whose left and right children point to y and x, respectively is formed. A pointer to this new tree is then pushed to the stack. In the end, a pointer to the full expression tree remains on the stack.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#include <iostream> #include <stack> #include <string> using namespace std; // Data structure to store a binary tree node struct Node { char data; Node *left, *right; Node(char data) { this->data = data; this->left = this->right = nullptr; }; Node(char data, Node *left, Node *right) { this->data = data; this->left = left; this->right = right; }; }; // Function to check if a given token is an operator bool isOperator(char c) { return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^'); } // Print the postfix expression for an expression tree void postorder(Node* root) { if (root == nullptr) { return; } postorder(root->left); postorder(root->right); cout << root->data; } // Print the infix expression for an expression tree void inorder(Node* root) { if (root == nullptr) { return; } // if the current token is an operator, print open parenthesis if (isOperator(root->data)) { cout << "("; } inorder(root->left); cout << root->data; inorder(root->right); // if the current token is an operator, print close parenthesis if (isOperator(root->data)) { cout << ")"; } } // Function to construct an expression tree from the given postfix expression Node* construct(string postfix) { // base case if (postfix.length() == 0) { return nullptr; } // create an empty stack to store tree pointers stack<Node*> s; // traverse the postfix expression for (char c: postfix) { // if the current token is an operator if (isOperator(c)) { // pop two nodes `x` and `y` from the stack Node* x = s.top(); s.pop(); Node* y = s.top(); s.pop(); // construct a new binary tree whose root is the operator and whose // left and right children point to `y` and `x`, respectively Node* node = new Node(c, y, x); // push the current node into the stack s.push(node); } // if the current token is an operand, create a new binary tree node // whose root is the operand and push it into the stack else { s.push(new Node(c)); } } // a pointer to the root of the expression tree remains on the stack return s.top(); } int main() { string postfix = "ab+cde+**"; Node* root = construct(postfix); cout << "Postfix Expression: "; postorder(root); cout << "\nInfix Expression: "; inorder(root); return 0; } |
Output:
Postfix Expression: ab+cde+**
Infix Expression: ((a+b)*(c*(d+e)))
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
import java.util.Stack; // Data structure to store a binary tree node class Node { char data; Node left, right; Node(char data) { this.data = data; this.left = this.right = null; } Node(char data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } class Main { // Function to check if a given token is an operator public static boolean isOperator(char c) { return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^'); } // Print the postfix expression for an expression tree public static void postorder(Node root) { if (root == null) { return; } postorder(root.left); postorder(root.right); System.out.print(root.data); } // Print the infix expression for an expression tree public static void inorder(Node root) { if (root == null) { return; } // if the current token is an operator, print open parenthesis if (isOperator(root.data)) { System.out.print("("); } inorder(root.left); System.out.print(root.data); inorder(root.right); // if the current token is an operator, print close parenthesis if (isOperator(root.data)) { System.out.print(")"); } } // Function to construct an expression tree from the given postfix expression public static Node construct(String postfix) { // base case if (postfix == null || postfix.length() == 0) { return null; } // create an empty stack to store tree pointers Stack<Node> s = new Stack<>(); // traverse the postfix expression for (char c: postfix.toCharArray()) { // if the current token is an operator if (isOperator(c)) { // pop two nodes `x` and `y` from the stack Node x = s.pop(); Node y = s.pop(); // construct a new binary tree whose root is the operator and whose // left and right children point to `y` and `x`, respectively Node node = new Node(c, y, x); // push the current node into the stack s.add(node); } // if the current token is an operand, create a new binary tree node // whose root is the operand and push it into the stack else { s.add(new Node(c)); } } // a pointer to the root of the expression tree remains on the stack return s.peek(); } public static void main(String[] args) { String postfix = "ab+cde+**"; Node root = construct(postfix); System.out.print("Postfix Expression: "); postorder(root); System.out.print("\nInfix Expression: "); inorder(root); } } |
Output:
Postfix Expression: ab+cde+**
Infix Expression: ((a+b)*(c*(d+e)))
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
from collections import deque # Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to check if a given token is an operator def isOperator(c): return c == '+' or c == '-' or c == '*' or c == '/' or c == '^' # Print the postfix expression for an expression tree def postorder(root): if root is None: return postorder(root.left) postorder(root.right) print(root.data, end='') # Print the infix expression for an expression tree def inorder(root): if root is None: return # if the current token is an operator, print open parenthesis if isOperator(root.data): print('(', end='') inorder(root.left) print(root.data, end='') inorder(root.right) # if the current token is an operator, print close parenthesis if isOperator(root.data): print(')', end='') # Function to construct an expression tree from the given postfix expression def construct(postfix): # base case if not postfix: return # create an empty stack to store tree pointers s = deque() # traverse the postfix expression for c in postfix: # if the current token is an operator if isOperator(c): # pop two nodes `x` and `y` from the stack x = s.pop() y = s.pop() # construct a new binary tree whose root is the operator and whose # left and right children point to `y` and `x`, respectively node = Node(c, y, x) # push the current node into the stack s.append(node) # if the current token is an operand, create a new binary tree node # whose root is the operand and push it into the stack else: s.append(Node(c)) # a pointer to the root of the expression tree remains on the stack return s[-1] if __name__ == '__main__': postfix = 'ab+cde+**' root = construct(postfix) print('Postfix Expression: ', end='') postorder(root) print('\nInfix Expression: ', end='') inorder(root) |
Output:
Postfix Expression: ab+cde+**
Infix Expression: ((a+b)*(c*(d+e)))
The time complexity of the above solution is O(n) and requires O(n) extra space for the stack, where n is the length of the postfix expression.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)