---

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

// ======================== СТЕК ДЛЯ ОПЕРАТОРОВ (char) ========================
typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
}

int isEmptyStack(Stack* s) {
    return s->top == NULL;
}

void pushStack(Stack* s, char value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Ошибка: не удалось выделить память!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

char popStack(Stack* s) {
    if (isEmptyStack(s)) {
        return '\0'; // ошибка
    }
    Node* temp = s->top;
    char value = temp->data;
    s->top = s->top->next;
    free(temp);
    return value;
}

char peekStack(Stack* s) {
    if (isEmptyStack(s)) return '\0';
    return s->top->data;
}

void freeStack(Stack* s) {
    while (!isEmptyStack(s)) {
        popStack(s);
    }
}

// ======================== СТЕК ДЛЯ ЧИСЕЛ (double) ========================
typedef struct DNode {
    double data;
    struct DNode* next;
} DNode;

typedef struct {
    DNode* top;
} DStack;

void initDStack(DStack* s) {
    s->top = NULL;
}

int isEmptyDStack(DStack* s) {
    return s->top == NULL;
}

void pushDStack(DStack* s, double value) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (!newNode) {
        printf("Ошибка памяти!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

double popDStack(DStack* s) {
    if (isEmptyDStack(s)) {
        printf("Ошибка: стек пуст при pop!\n");
        return 0.0;
    }
    DNode* temp = s->top;
    double value = temp->data;
    s->top = s->top->next;
    free(temp);
    return value;
}

// Пошаговый вывод состояния стека (для наглядности)
void printDStack(DStack* s) {
    DNode* current = s->top;
    printf("[ ");
    while (current != NULL) {
        printf("%.2f ", current->data);
        current = current->next;
    }
    printf("] (верхушка слева)\n");
}

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

// ======================== ПРЕОБРАЗОВАНИЕ ИНФИКС → ОПЗ (алгоритм сортировочной станции) ========================
char* infixToPostfix(const char* infix) {
    int len = strlen(infix);
    char* postfix = (char*)malloc(len * 2 + 10); // запас для пробелов
    if (!postfix) return NULL;
    postfix[0] = '\0';

    Stack s;
    initStack(&s);

    int i = 0;
    int j = 0; // индекс для postfix

    while (infix[i] != '\0') {
        // Пропускаем пробелы
        if (isspace(infix[i])) {
            i++;
            continue;
        }

        // Если число (целое)
        if (isdigit(infix[i])) {
            while (isdigit(infix[i])) {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';
            continue;
        }

        // Левая скобка
        if (infix[i] == '(') {
            pushStack(&s, '(');
        }
        // Правая скобка
        else if (infix[i] == ')') {
            while (!isEmptyStack(&s) && peekStack(&s) != '(') {
                postfix[j++] = popStack(&s);
                postfix[j++] = ' ';
            }
            if (!isEmptyStack(&s) && peekStack(&s) == '(') {
                popStack(&s); // удаляем '('
            } else {
                printf("Ошибка: несбалансированные скобки!\n");
            }
        }
        // Оператор
        else if (strchr("+-*/", infix[i])) {
            char op = infix[i];
            while (!isEmptyStack(&s) && peekStack(&s) != '(' &&
                   precedence(peekStack(&s)) >= precedence(op)) {
                postfix[j++] = popStack(&s);
                postfix[j++] = ' ';
            }
            pushStack(&s, op);
        } else {
            printf("Некорректный символ: %c\n", infix[i]);
        }
        i++;
    }

    // Вытаскиваем оставшиеся операторы
    while (!isEmptyStack(&s)) {
        if (peekStack(&s) == '(') {
            printf("Ошибка: несбалансированные скобки!\n");
        }
        postfix[j++] = popStack(&s);
        postfix[j++] = ' ';
    }

    postfix[j] = '\0';
    freeStack(&s);
    return postfix;
}

// ======================== ВЫЧИСЛЕНИЕ ОПЗ (стековый калькулятор) ========================
double evaluatePostfix(const char* postfix) {
    DStack s;
    initDStack(&s);

    char temp[1024];
    strncpy(temp, postfix, sizeof(temp) - 1);
    temp[sizeof(temp) - 1] = '\0';

    char* token = strtok(temp, " ");

    printf("Пошаговое вычисление ОПЗ:\n");
    while (token != NULL) {
        // Если число (поддержка отрицательных)
        if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
            double num = atof(token);
            pushDStack(&s, num);
            printf("После push %.2f: ", num);
            printDStack(&s);
        } 
        // Если оператор
        else if (strlen(token) == 1 && strchr("+-*/", token[0])) {
            if (isEmptyDStack(&s)) {
                printf("Ошибка: недостаточно операндов!\n");
                return 0.0;
            }
            double right = popDStack(&s);
            if (isEmptyDStack(&s)) {
                printf("Ошибка: недостаточно операндов!\n");
                return 0.0;
            }
            double left = popDStack(&s);

            double result = 0.0;
            char op = token[0];
            switch (op) {
                case '+': result = left + right; break;
                case '-': result = left - right; break;
                case '*': result = left * right; break;
                case '/':
                    if (right == 0.0) {
                        printf("Ошибка: деление на ноль!\n");
                        return 0.0;
                    }
                    result = left / right;
                    break;
                default:
                    printf("Неизвестный оператор!\n");
                    return 0.0;
            }

            pushDStack(&s, result);
            printf("После %c (%.2f %c %.2f = %.2f): ", op, left, op, right, result);
            printDStack(&s);
        }

        token = strtok(NULL, " ");
    }

    if (isEmptyDStack(&s)) {
        printf("Ошибка: пустой результат!\n");
        return 0.0;
    }

    double result = popDStack(&s);

    if (!isEmptyDStack(&s)) {
        printf("Предупреждение: в стеке остались элементы!\n");
    }

    return result;
}

int main() {
    char infix[512];

    printf("Введите арифметическое выражение (например: 3 + 4 * 2 / (1 - 5)):\n");
    fgets(infix, sizeof(infix), stdin);
    infix[strcspn(infix, "\n")] = 0; // удаляем перевод строки

    printf("\nИсходное выражение: %s\n", infix);

    char* postfix = infixToPostfix(infix);
    if (postfix == NULL) {
        printf("Ошибка преобразования!\n");
        return 1;
    }

    printf("Обратная польская запись (ОПЗ): %s\n\n", postfix);

    double result = evaluatePostfix(postfix);

    printf("\nРезультат: %.2f\n", result);

    free(postfix);
    return 0;
}