112 lines
2.5 KiB
C++
Executable File
112 lines
2.5 KiB
C++
Executable File
/*
|
|
THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.
|
|
|
|
Problem Statement: Construct an expression tree from the given prefix expression eg. +--a*bc/def and traverse it using postordertraversal(non recursive) and then delete the entire tree.
|
|
|
|
Code from DataStructuresAndAlgorithms (SPPU - Second Year - Computer Engineering - Content) repository on KSKA Git: https://git.kska.io/sppu-se-comp-content/DataStructuresAndAlgorithms/
|
|
*/
|
|
|
|
// BEGINNING OF CODE
|
|
#include <iostream>
|
|
#include <map>
|
|
#include <stack>
|
|
|
|
using namespace std;
|
|
|
|
class node {
|
|
public:
|
|
char data;
|
|
node *left, *right;
|
|
node() {
|
|
left = NULL;
|
|
right = NULL;
|
|
}
|
|
|
|
node(char ch) {
|
|
data = ch;
|
|
left = NULL;
|
|
right = NULL;
|
|
}
|
|
};
|
|
|
|
class tree {
|
|
private:
|
|
node *root;
|
|
stack<node *> nodestack;
|
|
|
|
bool isOperator(char ch) {
|
|
switch (ch) {
|
|
case '+':
|
|
case '-':
|
|
case '*':
|
|
case '/':
|
|
return 1;
|
|
break;
|
|
default:
|
|
return 0;
|
|
break;
|
|
}
|
|
}
|
|
|
|
void insert(char ch) {
|
|
if (isOperator(ch)) {
|
|
node *newnode = new node(ch);
|
|
newnode->left = nodestack.top();
|
|
nodestack.pop();
|
|
newnode->right = nodestack.top();
|
|
nodestack.pop();
|
|
nodestack.push(newnode);
|
|
} else {
|
|
node *newnode = new node(ch);
|
|
nodestack.push(newnode);
|
|
}
|
|
}
|
|
|
|
public:
|
|
void input_prefix(string exp) {
|
|
for (int i = exp.length() - 1; i > -1; i--) {
|
|
insert(exp[i]);
|
|
}
|
|
root = nodestack.top();
|
|
nodestack.pop();
|
|
}
|
|
|
|
void display_postfix() {
|
|
node *temp = root;
|
|
|
|
stack<node *> stack1, stack2;
|
|
|
|
stack1.push(root);
|
|
|
|
while (!stack1.empty()) {
|
|
temp = stack1.top();
|
|
stack1.pop();
|
|
stack2.push(temp);
|
|
if (temp->left != NULL) {
|
|
stack1.push(temp->left);
|
|
}
|
|
if (temp->right != NULL) {
|
|
stack1.push(temp->right);
|
|
}
|
|
}
|
|
while (!stack2.empty()) {
|
|
temp = stack2.top();
|
|
stack2.pop();
|
|
cout << temp->data;
|
|
}
|
|
|
|
cout << endl;
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
tree exp_tree;
|
|
string e;
|
|
cout << "Prefix expression is:\t";
|
|
cin >> e;
|
|
exp_tree.input_prefix(e);
|
|
exp_tree.display_postfix();
|
|
return 0;
|
|
}
|
|
// +--a*bc/def
|
|
// END OF CODE
|