---

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

// Узел AST
struct ASTNode {
    string value;        // число, переменная или оператор
    ASTNode* left;
    ASTNode* right;
    
    ASTNode(string val) : value(val), left(NULL), right(NULL) {}
};

class AST {
private:
    ASTNode* root;
    string output;
    
    // Постфиксный обход (левый → правый → корень)
    void postOrder(ASTNode* node) {
        if (!node) return;
        postOrder(node->left);
        postOrder(node->right);
        if (!output.empty()) output += " ";
        output += node->value;
    }
    
    // Освобождение памяти
    void deleteTree(ASTNode* node) {
        if (!node) return;
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
    
public:
    AST() : root(NULL) {}
    ~AST() { deleteTree(root); }
    
    // Построение AST из инфиксного выражения (упрощенная версия)
    void buildFromInfix(string infix) {
        // Убираем пробелы
        string expr;
        for (char c : infix) {
            if (!isspace(c)) expr += c;
        }
        
        root = parseExpression(expr, 0, expr.length() - 1);
    }
    
    // Парсинг выражения с приоритетами
    ASTNode* parseExpression(string& s, int left, int right) {
        // Поиск оператора с наименьшим приоритетом вне скобок
        int minPriority = 10;
        int minPos = -1;
        int bracketLevel = 0;
        
        for (int i = left; i <= right; i++) {
            if (s[i] == '(') {
                bracketLevel++;
                continue;
            }
            if (s[i] == ')') {
                bracketLevel--;
                continue;
            }
            if (bracketLevel > 0) continue;
            
            int priority;
            if (s[i] == '+' || s[i] == '-') priority = 1;
            else if (s[i] == '*' || s[i] == '/') priority = 2;
            else continue;
            
            if (priority <= minPriority) {
                minPriority = priority;
                minPos = i;
            }
        }
        
        // Если нашли оператор — создаем узел и рекурсивно парсим левую и правую части
        if (minPos != -1) {
            ASTNode* node = new ASTNode(string(1, s[minPos]));
            node->left = parseExpression(s, left, minPos - 1);
            node->right = parseExpression(s, minPos + 1, right);
            return node;
        }
        
        // Убираем внешние скобки
        if (s[left] == '(' && s[right] == ')') {
            return parseExpression(s, left + 1, right - 1);
        }
        
        // Операнд (число или переменная)
        return new ASTNode(s.substr(left, right - left + 1));
    }
    
    // Получение RPN через постфиксный обход
    string getRPN() {
        output.clear();
        postOrder(root);
        return output;
    }
    
    void printTree() {
        printTreeHelper(root, 0);
    }
    
private:
    void printTreeHelper(ASTNode* node, int level) {
        if (!node) return;
        for (int i = 0; i < level; i++) cout << "  ";
        cout << node->value << endl;
        printTreeHelper(node->left, level + 1);
        printTreeHelper(node->right, level + 1);
    }
};

int main() {
    string expression;
    cout << "Введите инфиксное выражение: ";
    getline(cin, expression);
    
    AST ast;
    ast.buildFromInfix(expression);
    
    cout << "\nAST (дерево):" << endl;
    ast.printTree();
    
    string rpn = ast.getRPN();
    cout << "\nПостфиксная запись (RPN): " << rpn << endl;
    
    return 0;
}