/*
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