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 in-order fashion. However, an opening and closing parenthesis must be added at the beginning and ending 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
|
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// A Binary Tree Node
struct Node
{
char data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
};
Node(int 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)
{
// 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 current node to 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 to 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 Expressiont: “;
postorder(root);
cout << “nInfix Expressiont: “;
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
|
import java.util.Stack;
// 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)
{
// 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 current node to 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 to 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
|
from collections import deque
# 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):
# 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 current node to 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 to 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 Expressiont: “, end=”)
postorder(root)
print(“nInfix Expressiont: “, end=”)
inorder(root)
|
Output:
Postfix Expression : ab+cde+××
Infix Expression : ((a+b)×(c×(d+e)))
Download Run Code
Output:
Postfix Expression : ab+cde+××
Infix Expression : ((a+b)×(c×(d+e)))
Download Run Code
Output:
Postfix Expression : ab+cde+××
Infix Expression : ((a+b)×(c×(d+e)))
Download Run Code
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.
source