---

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <stack>
#include <string>
using namespace std;

// Структура для узла дерева выражений
struct ExprNode {
    string value;
    ExprNode* left;
    ExprNode* right;
    
    ExprNode(string val) : value(val), left(NULL), right(NULL) {}
};

// Стек для узлов при построении дерева из постфиксной записи
struct NodeStack {
    ExprNode* node;
    NodeStack* next;
};

NodeStack* pushNode(NodeStack* top, ExprNode* node) {
    NodeStack* newTop = new NodeStack;
    newTop->node = node;
    newTop->next = top;
    return newTop;
}

NodeStack* popNode(NodeStack* top, ExprNode*& node) {
    if (!top) return NULL;
    node = top->node;
    NodeStack* temp = top;
    top = top->next;
    delete temp;
    return top;
}

// Разбиение строки на токены
int splitTokens(char* input, char tokens[][20]) {
    int count = 0;
    char* token = strtok(input, " ");
    while (token && count < 100) {
        strcpy(tokens[count++], token);
        token = strtok(NULL, " ");
    }
    return count;
}

// Построение дерева из постфиксной записи
ExprNode* buildTreeFromPostfix(char tokens[][20], int tokenCount) {
    NodeStack* stack = NULL;
    
    for (int i = 0; i < tokenCount; i++) {
        char* tok = tokens[i];
        
        // Проверка: оператор (+, -, *, /)
        if (strlen(tok) == 1 && (tok[0] == '+' || tok[0] == '-' || tok[0] == '*' || tok[0] == '/')) {
            ExprNode* node = new ExprNode(tok);
            stack = popNode(stack, node->right);  // правый операнд
            stack = popNode(stack, node->left);   // левый операнд
            stack = pushNode(stack, node);
        }
        else {  // Операнд (число или переменная)
            ExprNode* node = new ExprNode(tok);
            stack = pushNode(stack, node);
        }
    }
    
    ExprNode* root = NULL;
    stack = popNode(stack, root);
    return root;
}

// Префиксный обход (корень → левый → правый)
void prefixOrder(ExprNode* node, string& result) {
    if (!node) return;
    if (!result.empty()) result += " ";
    result += node->value;
    prefixOrder(node->left, result);
    prefixOrder(node->right, result);
}

// Постфиксный обход (левый → правый → корень)
void postfixOrder(ExprNode* node, string& result) {
    if (!node) return;
    postfixOrder(node->left, result);
    postfixOrder(node->right, result);
    if (!result.empty()) result += " ";
    result += node->value;
}

// Освобождение памяти
void deleteTree(ExprNode* node) {
    if (!node) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

// Постфиксная → Префиксная
string postfixToPrefix(char* postfix) {
    // Копируем, так как strtok изменяет строку
    char buffer[200];
    strcpy(buffer, postfix);
    
    char tokens[100][20];
    int tokenCount = splitTokens(buffer, tokens);
    
    ExprNode* root = buildTreeFromPostfix(tokens, tokenCount);
    
    string prefix;
    prefixOrder(root, prefix);
    
    deleteTree(root);
    return prefix;
}

// Префиксная → Постфиксная (для проверки)
string prefixToPostfix(const string& prefix) {
    // Разбиваем префиксную строку на токены
    char buffer[200];
    strcpy(buffer, prefix.c_str());
    
    char tokens[100][20];
    int tokenCount = splitTokens(buffer, tokens);
    
    // Стек для поддеревьев (стек строк)
    stack<string> st;
    
    // Идём с конца к началу (для префиксной записи)
    for (int i = tokenCount - 1; i >= 0; i--) {
        char* tok = tokens[i];
        
        // Если оператор
        if (strlen(tok) == 1 && (tok[0] == '+' || tok[0] == '-' || tok[0] == '*' || tok[0] == '/')) {
            string left = st.top(); st.pop();
            string right = st.top(); st.pop();
            string expr = left + " " + right + " " + tok;
            st.push(expr);
        }
        else {  // Операнд
            st.push(tok);
        }
    }
    
    return st.top();
}

int main() {
    char postfix[200];
    
    cout << "========================================" << endl;
    cout << "Преобразование постфиксной записи в префиксную" << endl;
    cout << "========================================" << endl;
    cout << "Пример: 3 4 + 2 *" << endl;
    cout << endl;
    
    while (true) {
        cout << "Введите постфиксное выражение (или 'exit' для выхода): ";
        cin.getline(postfix, 200);
        
        if (strcmp(postfix, "exit") == 0) break;
        if (strlen(postfix) == 0) continue;
        
        // Постфиксная → Префиксная
        string prefix = postfixToPrefix(postfix);
        cout << "Префиксная запись: " << prefix << endl;
        
        // Проверка: Префиксная → Постфиксная
        string postfixBack = prefixToPostfix(prefix);
        cout << "Обратное преобразование (префиксная → постфиксная): " << postfixBack << endl;
        
        // Проверка совпадения
        if (strcmp(postfix, postfixBack.c_str()) == 0) {
            cout << "✓ ПРОВЕРКА ПРОЙДЕНА: исходная и полученная записи совпадают!" << endl;
        }
        else {
            cout << "✗ ПРОВЕРКА НЕ ПРОЙДЕНА!" << endl;
            cout << "Исходная:     " << postfix << endl;
            cout << "Полученная:   " << postfixBack << endl;
        }
        cout << endl;
    }
    
    return 0;
}