---

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

// ======================== СТЕК (односвязный список) ========================

// Стек для операторов (char)
typedef struct Node {
    char data;
    struct Node* next;
} Node;

Node* topOp = NULL;

void pushOp(char x) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = x;
    n->next = topOp;
    topOp = n;
}

char popOp() {
    if (!topOp) return '\0';
    Node* t = topOp;
    char val = t->data;
    topOp = topOp->next;
    free(t);
    return val;
}

char peekOp() {
    return topOp ? topOp->data : '\0';
}

// Стек для чисел (double)
typedef struct DNode {
    double data;
    struct DNode* next;
} DNode;

DNode* topNum = NULL;

void pushNum(double x) {
    DNode* n = (DNode*)malloc(sizeof(DNode));
    n->data = x;
    n->next = topNum;
    topNum = n;
}

double popNum() {
    if (!topNum) return 0;
    DNode* t = topNum;
    double val = t->data;
    topNum = topNum->next;
    free(t);
    return val;
}

void printStack() {                 // пошаговый вывод
    DNode* p = topNum;
    printf("[ ");
    while (p) {
        printf("%.2f ", p->data);
        p = p->next;
    }
    printf("]\n");
}

// Приоритет
int prio(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// ======================== ИНФИКС → ОПЗ ========================
void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    postfix[0] = '\0';

    while (infix[i]) {
        if (isspace(infix[i])) { i++; continue; }

        if (isdigit(infix[i])) {
            while (isdigit(infix[i]))
                postfix[j++] = infix[i++];
            postfix[j++] = ' ';
            continue;
        }

        if (infix[i] == '(') {
            pushOp('(');
        }
        else if (infix[i] == ')') {
            while (peekOp() != '(' && peekOp() != '\0') {
                postfix[j++] = popOp();
                postfix[j++] = ' ';
            }
            popOp(); // убираем '('
        }
        else if (strchr("+-*/", infix[i])) {
            while (prio(peekOp()) >= prio(infix[i]) && peekOp() != '(') {
                postfix[j++] = popOp();
                postfix[j++] = ' ';
            }
            pushOp(infix[i]);
        }
        i++;
    }

    while (peekOp() != '\0') {
        postfix[j++] = popOp();
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

// ======================== ВЫЧИСЛЕНИЕ ОПЗ ========================
double evaluatePostfix(char* postfix) {
    char* token = strtok(postfix, " ");
    
    printf("Пошаговое вычисление:\n");
    
    while (token) {
        if (isdigit(token[0])) {
            pushNum(atof(token));
            printf("push %.2f → ", atof(token));
            printStack();
        }
        else {
            double b = popNum();
            double a = popNum();
            double res = 0;
            
            switch(token[0]) {
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': 
                    if (b == 0) { printf("Деление на ноль!\n"); return 0; }
                    res = a / b; 
                    break;
            }
            pushNum(res);
            printf("%c → ", token[0]);
            printStack();
        }
        token = strtok(NULL, " ");
    }
    return popNum();
}

// ======================== MAIN ========================
int main() {
    char expr[256];
    char postfix[512];
    
    printf("Введите выражение: ");
    fgets(expr, sizeof(expr), stdin);
    
    infixToPostfix(expr, postfix);
    
    printf("\nИсходное: %s", expr);
    printf("ОПЗ: %s\n", postfix);
    
    double result = evaluatePostfix(postfix);
    
    printf("Результат = %.2f\n", result);
    
    return 0;
}