#include <iostream>
#include <vector>
#include <string>

using namespace::std;


class Node {
private:
    string data;
    long index;
    Node *parent;
    vector<Node*> children;
    void addChildren(Node *n) {
        children.push_back(n);
    }
public:
    Node(string d, long i) {
        data = d;
        index = i;
        parent = NULL;
    }
    void setParent(Node &p) {
        parent = &p;
        parent->children.push_back(this);
    }
    void setData(string d) {
        data = d;
    }
    long getIndex(){
        return index;
    }
    size_t GetCountOfChild() {
        return children.size();
    }
    Node *GetParent(){
        return parent;
    }
    
    string GetData() {
        return data;
    }
    vector<Node*> GetChildren() {
        return children;
    }
    ~Node() {
    }
};

class Tree {
private:
    vector<Node*> nodes;
    vector<string> result;
    
    void forwardStep(Node *node) {
        result.push_back(node->GetData());
        for (size_t i = 0; i < node->GetCountOfChild(); i++) {
            forwardStep(node->GetChildren()[i]);
        }
    }
    void notacjaPolska(Node *node) {
        for (size_t i = 0; i < node->GetCountOfChild(); i++) {
            notacjaPolska(node->GetChildren()[i]);
        }
        result.push_back(node->GetData());
    }
public:
    Tree() {}
    void addNewNode(Node *p) {
        nodes.push_back(p);
    }
    void setParentByNodeIndex(size_t child, size_t parent) {
        getNodeByNodeIndex(child)->setParent(*getNodeByNodeIndex(parent));
    }
    void setParentByIndex(size_t child, size_t parent) {
        nodes[child]->setParent(*nodes[parent]);
    }
    void forwardStep() {
        result.clear();
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes[i]->GetParent() == NULL &&  nodes[i]->GetCountOfChild() > 0) {
                forwardStep(nodes[i]);
                return;
            }
        }
    }
    void notacjaPolska() {
        result.clear();
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes[i]->GetParent() == NULL &&  nodes[i]->GetCountOfChild() > 0) {
                notacjaPolska(nodes[i]);
                return;
            }
        }
        
    }
    Node *getNodeByNodeIndex(long index) {
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes[i]->getIndex() == index)
                return nodes[i];
        }
        return NULL;
    }
    Node *getNodeByIndex(size_t index) {
        return nodes[index];
    }
    Node *operator[](size_t index) {
        return getNodeByNodeIndex(index);
    }
    vector<string> Result() {
        return result;
    }
    ~Tree() {
    }
};

int main() {
    Tree tree;
    tree.addNewNode(new Node("a", 1));
    tree.addNewNode(new Node("b", 2));
    tree.addNewNode(new Node("+", 3));
    
    tree.setParentByNodeIndex(1, 3);
    tree.setParentByNodeIndex(2, 3);
    
    tree.addNewNode(new Node("c", 5));
    tree.addNewNode(new Node("d", 6));
    tree.addNewNode(new Node("e", 7));
    tree.addNewNode(new Node("-", 8));
    tree.addNewNode(new Node("*", 9));
    tree.addNewNode(new Node("+", 10));
    
    tree.setParentByNodeIndex(6, 8);
    tree.setParentByNodeIndex(7, 8);
    
    tree.setParentByNodeIndex(5, 9);
    tree.setParentByNodeIndex(8, 9);
    
    tree.setParentByNodeIndex(3, 10);
    tree.setParentByNodeIndex(9, 10);
    tree.notacjaPolska();
    cout << "Польская запись: " << tree.Result()[0]<< endl;
    return 0;
}