---

#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) {
    if (s[0] == '\0') return 0;
    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 == '/');
}

// Разбор строки на токены (аналог strtok без его использования)
int parseTokens(char *str, char tokens[100][100]) {
    int n = 0;
    int i = 0;
    int j = 0;
    char token[100];
    
    for (i = 0; str[i] != '\0'; i++) {
        if (str[i] == ' ') {
            if (j > 0) {
                token[j] = '\0';
                strcpy(tokens[n++], token);
                j = 0;
            }
        } else {
            token[j++] = str[i];
        }
    }
    if (j > 0) {
        token[j] = '\0';
        strcpy(tokens[n++], token);
    }
    return n;
}

// Вычисление числового RPN
double calcRPN(char tokens[100][100], int count) {
    tstk *sp = NULL;
    double a, b;
    
    for (int i = 0; i < count; i++) {
        if (isNumber(tokens[i])) {
            sp = AddStack(sp, atof(tokens[i]));
        }
        else if (strlen(tokens[i]) == 1 && isOperator(tokens[i][0])) {
            sp = ReadStack(sp, b);
            sp = ReadStack(sp, a);
            switch (tokens[i][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;
            }
        }
    }
    double res;
    sp = ReadStack(sp, res);
    return res;
}

void OptimizeRPN(char *strin, char *strout) {
    tstkStr *sp = NULL;
    char tokens[100][100];
    int tokCount = parseTokens(strin, tokens);
    
    for (int i = 0; i < tokCount; i++) {
        char *tok = tokens[i];
        
        // Если токен - число или переменная (буква)
        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);
            
            // Проверяем, можно ли вычислить
            if (isNumber(a) && isNumber(b)) {
                char fragment[100][100];
                strcpy(fragment[0], a);
                strcpy(fragment[1], b);
                strcpy(fragment[2], tok);
                double res = calcRPN(fragment, 3);
                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);
            }
        }
    }
    
    // Собираем результат из стека
    char temp[100][100];
    int cnt = 0;
    while (sp != NULL) {
        sp = ReadStackStr(sp, temp[cnt++]);
    }
    
    strout[0] = '\0';
    for (int i = cnt - 1; i >= 0; i--) {
        strcat(strout, temp[i]);
        if (i > 0) strcat(strout, " ");
    }
}

int main() {
    char str[200], strp[200];
    
    cout << "Vvedite RPN virazhenie (tokeni cherez probel): ";
    cin.getline(str, 200);
    
    OptimizeRPN(str, strp);
    
    cout << "Optimizirovannoe: " << strp << endl;
    
    return 0;
}