---

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

struct tstk {
    double inf;
    tstk *a;
};

struct tstkStr {
    char inf[100];
    tstkStr *a;
};

tstk *AddStack(tstk *sp, double inf) {
    tstk *spt = new tstk;
    spt->inf = inf;
    spt->a = sp;
    return spt;
}

tstk *ReadStack(tstk *sp, double &inf) {
    tstk *spt = sp;
    inf = sp->inf;
    sp = sp->a;
    delete spt;
    return sp;
}

tstkStr *AddStackStr(tstkStr *sp, char *inf) {
    tstkStr *spt = new tstkStr;
    strcpy(spt->inf, inf);
    spt->a = sp;
    return spt;
}

tstkStr *ReadStackStr(tstkStr *sp, char *inf) {
    tstkStr *spt = sp;
    strcpy(inf, sp->inf);
    sp = sp->a;
    delete spt;
    return sp;
}

int isNumber(char *s) {
    int i = 0;
    if (s[0] == '-') i++;
    int dot = 0;
    for (; s[i]; i++) {
        if (s[i] == '.') { dot++; if (dot > 1) return 0; }
        else if (s[i] < '0' || s[i] > '9') return 0;
    }
    return 1;
}

int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// Вычисление RPN (числового, без переменных)
double calcRPN(char *str) {
    tstk *sp = NULL;
    char *tok = strtok(str, " ");
    double a, b;
    
    while (tok) {
        if (isNumber(tok)) {
            sp = AddStack(sp, atof(tok));
        } else if (strlen(tok) == 1 && isOperator(tok[0])) {
            sp = ReadStack(sp, b);
            sp = ReadStack(sp, a);
            switch (tok[0]) {
                case '+': sp = AddStack(sp, a + b); break;
                case '-': sp = AddStack(sp, a - b); break;
                case '*': sp = AddStack(sp, a * b); break;
                case '/': sp = AddStack(sp, a / b); break;
            }
        }
        tok = strtok(NULL, " ");
    }
    double res;
    sp = ReadStack(sp, res);
    return res;
}

// Проверка, состоит ли фрагмент только из чисел и операторов
int isConstantFragment(char *str) {
    char copy[100];
    strcpy(copy, str);
    char *tok = strtok(copy, " ");
    while (tok) {
        if (!isNumber(tok) && !(strlen(tok) == 1 && isOperator(tok[0]))) {
            return 0;
        }
        tok = strtok(NULL, " ");
    }
    return 1;
}

// Оптимизация RPN
void OptimizeRPN(char *in, char *out) {
    tstkStr *sp = NULL;
    char *tok = strtok(in, " ");
    
    while (tok) {
        // Если токен - число или переменная
        if (isNumber(tok) || (strlen(tok) == 1 && !isOperator(tok[0]))) {
            sp = AddStackStr(sp, tok);
        }
        // Если токен - оператор
        else if (strlen(tok) == 1 && isOperator(tok[0])) {
            // Берем два верхних элемента из стека
            char b[100], a[100];
            sp = ReadStackStr(sp, b);
            sp = ReadStackStr(sp, a);
            
            // Составляем фрагмент "a b оператор"
            char fragment[300];
            sprintf(fragment, "%s %s %s", a, b, tok);
            
            // Проверяем, можно ли вычислить этот фрагмент
            if (isNumber(a) && isNumber(b)) {
                // Оба числа - вычисляем
                char copy[300];
                strcpy(copy, fragment);
                double res = calcRPN(copy);
                char resStr[100];
                if (res == (int)res) sprintf(resStr, "%d", (int)res);
                else sprintf(resStr, "%g", res);
                sp = AddStackStr(sp, resStr);
            } else {
                // Нельзя вычислить - возвращаем обратно
                sp = AddStackStr(sp, a);
                sp = AddStackStr(sp, b);
                sp = AddStackStr(sp, tok);
            }
        }
        tok = strtok(NULL, " ");
    }
    
    // Собираем результат
    char temp[100][100];
    int cnt = 0;
    while (sp) {
        sp = ReadStackStr(sp, temp[cnt++]);
    }
    
    out[0] = '\0';
    for (int i = cnt - 1; i >= 0; i--) {
        strcat(out, temp[i]);
        if (i > 0) strcat(out, " ");
    }
}

int main() {
    char rpn[200], optimized[200];
    
    cout << "Vvedite RPN virazhenie: ";
    cin.getline(rpn, 200);
    
    char copy[200];
    strcpy(copy, rpn);
    
    OptimizeRPN(copy, optimized);
    
    cout << "Optimizirovannoe: " << optimized << endl;
    
    return 0;
}