[go: up one dir, main page]
Scribd
Upload
6 views2 pages

Employeeinformation Using Postorder

The document provides a C++ program that constructs an expression tree from a given prefix expression and performs a non-recursive post-order traversal to print the corresponding postfix expression. It includes functions to build the tree, traverse it, and delete the entire tree after use. The program prompts the user to input a prefix expression and handles invalid expressions with error messages.

Uploaded by

omshi112233
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views2 pages

Employeeinformation Using Postorder

The document provides a C++ program that constructs an expression tree from a given prefix expression and performs a non-recursive post-order traversal to print the corresponding postfix expression. It includes functions to build the tree, traverse it, and delete the entire tree after use. The program prompts the user to input a prefix expression and handles invalid expressions with error messages.

Uploaded by

omshi112233
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

/*Construct an expression tree from the given

prefix expression eg. +--a*bc/def and traverse it


using post order traversal (non recursive) and
then delete the entire tree.*/
#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Node structure for the expression tree


struct Node {
string data;
Node* left;
Node* right;

Node(const string& val) {


data = val;
left = right = nullptr;
}
};

// Check if a character is an operator


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

// Build expression tree from prefix expression (right to left)


Node* buildTreeFromPrefix(const string& prefix) {
stack<Node*> st;

for (int i = prefix.length() - 1; i >= 0; i--) {


char ch = prefix[i];
if (ch == ' ') continue; // skip spaces if any
string token(1, ch);
Node* node = new Node(token);

if (isOperator(ch)) {
if (st.size() < 2) {
cerr << "Invalid prefix expression.\n";
exit(1);
}
node->left = st.top(); st.pop();
node->right = st.top(); st.pop();
}

st.push(node);
}

if (st.size() != 1) {
cerr << "Invalid prefix expression.\n";
exit(1);
}

return st.top();
}

// Non-recursive postorder traversal to print postfix expression


void postOrderNonRecursive(Node* root) {
if (!root) return;
stack<Node*> s1, s2;
s1.push(root);

while (!s1.empty()) {
Node* curr = s1.top(); s1.pop();
s2.push(curr);

if (curr->left) s1.push(curr->left);
if (curr->right) s1.push(curr->right);
}

cout << "Postfix Expression: ";


while (!s2.empty()) {
cout << s2.top()->data;
s2.pop();
}
cout << endl;
}

// Delete the expression tree (post-order deletion using stack)


void deleteTree(Node* root) {
if (!root) return;
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* node = st.top(); st.pop();
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
delete node;
}
}

int main() {
string prefix;
cout << "Enter a prefix expression (e.g., +--a*bc/def): ";
cin >> prefix;

Node* root = buildTreeFromPrefix(prefix);


postOrderNonRecursive(root);
deleteTree(root);

return 0;
}

You might also like