---

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

struct tstk {
    double inf;
    tstk *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;
}

// Стек для строк (для оптимизации RPN)
struct tstkStr {
    char inf[100];
    tstkStr *a;
};

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 *str) {
    int i = 0;
    if (str[0] == '-') i++;
    int dotCount = 0;
    for (; str[i]; i++) {
        if (str[i] == '.') {
            dotCount++;
            if (dotCount > 1) return 0;
            continue;
        }
        if (str[i] < '0' || str[i] > '9') return 0;
    }
    return 1;
}

// Проверка, является ли символ оператором
int isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

// Выполнение операции
double applyOp(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

// Оптимизация RPN: вычисление константных подвыражений
void OptimizeRPN(char *strin, char *strout) {
    tstkStr *sp = NULL;
    char token[100];
    char a[100], b[100], res[100];
    int n = 0;
    
    // Разбиваем входную строку на токены (разделитель - пробел)
    char *ptr = strtok(strin, " ");
    
    while (ptr != NULL) {
        // Если это не оператор (число или переменная)
        if (strlen(ptr) == 1 && isOperator(ptr[0]) && ptr[0] != '-') {
            // Это оператор
            if (sp != NULL && sp->a != NULL) {
                // Извлекаем два верхних элемента
                sp = ReadStackStr(sp, b);
                sp = ReadStackStr(sp, a);
                
                // Проверяем, являются ли оба числами
                if (isNumber(a) && isNumber(b)) {
                    double va = atof(a);
                    double vb = atof(b);
                    double r = applyOp(va, vb, ptr[0]);
                    
                    // Формируем строку результата
                    if (r == (int)r)
                        sprintf(res, "%d", (int)r);
                    else
                        sprintf(res, "%g", r);
                    
                    sp = AddStackStr(sp, res);
                } else {
                    // Нельзя вычислить - возвращаем обратно в обратном порядке
                    sp = AddStackStr(sp, a);
                    sp = AddStackStr(sp, b);
                    sp = AddStackStr(sp, ptr);
                }
            } else {
                sp = AddStackStr(sp, ptr);
            }
        } else {
            // Число или переменная
            sp = AddStackStr(sp, ptr);
        }
        ptr = strtok(NULL, " ");
    }
    
    // Собираем результат из стека
    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 rpn[200], optimized[200];
    
    cout << "=== Оптимизация выражений в обратной польской записи ===" << endl;
    cout << "Программа находит константные подвыражения и вычисляет их заранее." << endl;
    cout << endl;
    
    // Пример 1
    cout << "Пример 1:" << endl;
    strcpy(rpn, "2 3 + x *");
    cout << "Исходное RPN: " << rpn << endl;
    OptimizeRPN(rpn, optimized);
    cout << "Оптимизированное: " << optimized << endl;
    cout << "Пояснение: 2+3=5, результат '5 x *'" << endl;
    cout << endl;
    
    // Пример 2
    cout << "Пример 2:" << endl;
    strcpy(rpn, "3 4 + 5 2 - *");
    cout << "Исходное RPN: " << rpn << endl;
    OptimizeRPN(rpn, optimized);
    cout << "Оптимизированное: " << optimized << endl;
    cout << "Пояснение: 3+4=7, 5-2=3, 7*3=21, результат '21'" << endl;
    cout << endl;
    
    // Пример 3
    cout << "Пример 3:" << endl;
    strcpy(rpn, "10 2 / 3 * 4 +");
    cout << "Исходное RPN: " << rpn << endl;
    OptimizeRPN(rpn, optimized);
    cout << "Оптимизированное: " << optimized << endl;
    cout << "Пояснение: 10/2=5, 5*3=15, 15+4=19, результат '19'" << endl;
    cout << endl;
    
    // Пример 4
    cout << "Пример 4:" << endl;
    strcpy(rpn, "a 2 * 4 2 / +");
    cout << "Исходное RPN: " << rpn << endl;
    OptimizeRPN(rpn, optimized);
    cout << "Оптимизированное: " << optimized << endl;
    cout << "Пояснение: 4/2=2, результат 'a 2 * 2 +'" << endl;
    cout << endl;
    
    // Пример 5
    cout << "Пример 5:" << endl;
    strcpy(rpn, "x y + 5 3 - * z /");
    cout << "Исходное RPN: " << rpn << endl;
    OptimizeRPN(rpn, optimized);
    cout << "Оптимизированное: " << optimized << endl;
    cout << "Пояснение: 5-3=2, результат 'x y + 2 * z /'" << endl;
    cout << endl;
    
    // Ввод от пользователя
    cout << "=== Ввод пользователя ===" << endl;
    cout << "Введите RPN выражение (токены разделены пробелами): ";
    cin.getline(rpn, 200);
    
    // Сохраняем оригинал для вывода
    char original[200];
    strcpy(original, rpn);
    
    OptimizeRPN(rpn, optimized);
    cout << "Исходное: " << original << endl;
    cout << "Оптимизированное: " << optimized << endl;
    
    return 0;
}