/*
 * УПРАЖНЕНИЯ ПО РАБОТЕ СО СТЕКОМ В C
 * ===================================
 *
 * Теория:
 * -------
 * Стек - структура данных LIFO (Last In, First Out)
 * Операции: push (добавить), pop (удалить), peek (посмотреть), isEmpty
 *
 * В C есть два типа памяти:
 * - СТЕК (Stack) - автоматическая, быстрая, ограниченная, локальные переменные
 * - КУЧА (Heap) - динамическая (malloc/free), медленная, большая
 */

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

#define MAX_SIZE 100

/* ============================================================================
 * ЗАДАЧА 1: Базовый стек на массиве
 * ============================================================================
 * Реализуй простой стек с операциями push, pop, peek, isEmpty
 */

typedef struct {
  int data[MAX_SIZE];
  int top; // индекс вершины стека
} Stack;

// Инициализировать стек
void stack_init(Stack *s) {
  // TODO: реализуй инициализацию
}

// Проверить, пуст ли стек
bool stack_isEmpty(Stack *s) {
  // TODO: реализуй проверку
  return false;
}

// Проверить, полон ли стек
bool stack_isFull(Stack *s) {
  // TODO: реализуй проверку
  return false;
}

// Добавить элемент в стек
bool stack_push(Stack *s, int value) {
  // TODO: реализуй push
  // Проверь переполнение!
  return false;
}

// Удалить и вернуть элемент из стека
bool stack_pop(Stack *s, int *value) {
  // TODO: реализуй pop
  // Проверь, не пуст ли стек!
  return false;
}

// Посмотреть элемент на вершине без удаления
bool stack_peek(Stack *s, int *value) {
  // TODO: реализуй peek
  return false;
}

void test_task1() {
  printf("\n=== ЗАДАЧА 1: Базовый стек ===\n");
  Stack s;
  stack_init(&s);

  // Тест push
  stack_push(&s, 10);
  stack_push(&s, 20);
  stack_push(&s, 30);

  // Тест peek
  int value;
  if (stack_peek(&s, &value)) {
    printf("Вершина стека: %d (ожидается 30)\n", value);
  }

  // Тест pop
  while (!stack_isEmpty(&s)) {
    stack_pop(&s, &value);
    printf("Pop: %d\n", value);
  }
}

/* ============================================================================
 * ЗАДАЧА 2: Перевернуть строку используя стек
 * ============================================================================
 * Используй стек для переворачивания строки
 */

void reverse_string(char *str) {
  // TODO: используй стек для переворота строки
  // Подсказка: помести каждый символ в стек, затем извлеки обратно
}

void test_task2() {
  printf("\n=== ЗАДАЧА 2: Перевернуть строку ===\n");
  char str[] = "Hello, Stack!";
  printf("До:    %s\n", str);
  reverse_string(str);
  printf("После: %s\n", str);
  printf("Ожидается: !kcatS ,olleH\n");
}

/* ============================================================================
 * ЗАДАЧА 3: Проверка сбалансированности скобок
 * ============================================================================
 * Проверь, правильно ли расставлены скобки: (), [], {}
 * Примеры:
 * - "([])" -> true
 * - "([)]" -> false
 * - "{[()]}" -> true
 */

bool is_balanced(const char *expr) {
  // TODO: используй стек для проверки скобок
  // Алгоритм:
  // 1. При открывающей скобке - push
  // 2. При закрывающей - pop и проверь соответствие
  // 3. В конце стек должен быть пуст
  return false;
}

void test_task3() {
  printf("\n=== ЗАДАЧА 3: Сбалансированность скобок ===\n");
  const char *tests[] = {"()",  "([])", "([)]",   "{[()]}",
                         "(((", "))",   "{[(])}", ""};

  for (int i = 0; i < 8; i++) {
    printf("\"%s\" -> %s\n", tests[i],
           is_balanced(tests[i]) ? "сбалансированы" : "НЕ сбалансированы");
  }
}

/* ============================================================================
 * ЗАДАЧА 4: Калькулятор обратной польской нотации (RPN)
 * ============================================================================
 * Вычисли выражение в постфиксной записи
 * Пример: "3 4 + 2 *" = (3 + 4) * 2 = 14
 *
 * Алгоритм:
 * - Если число - push в стек
 * - Если операция - pop два числа, выполни операцию, push результат
 */

int evaluate_rpn(const char *expr) {
  // TODO: реализуй RPN калькулятор
  // Подсказка: используй strtok для разбора строки
  return 0;
}

void test_task4() {
  printf("\n=== ЗАДАЧА 4: RPN Калькулятор ===\n");
  const char *expressions[] = {
      "3 4 +",             // 7
      "3 4 + 2 *",         // 14
      "5 1 2 + 4 * + 3 -", // 14
  };

  for (int i = 0; i < 3; i++) {
    printf("\"%s\" = %d\n", expressions[i], evaluate_rpn(expressions[i]));
  }
}

/* ============================================================================
 * ЗАДАЧА 5: Стековая память vs Куча
 * ============================================================================
 * Изучи разницу между стековой памятью и кучей
 */

void demonstrate_stack_memory() {
  printf("\n=== ЗАДАЧА 5: Стековая память ===\n");

  // Локальные переменные - на стеке
  int stack_var = 42;
  int stack_array[10];

  printf("Адрес stack_var: %p\n", (void *)&stack_var);
  printf("Адрес stack_array: %p\n", (void *)stack_array);

  // Динамическая память - в куче
  int *heap_var = malloc(sizeof(int));
  int *heap_array = malloc(10 * sizeof(int));

  printf("Адрес heap_var: %p\n", (void *)heap_var);
  printf("Адрес heap_array: %p\n", (void *)heap_array);

  printf("\nСтек растет вниз (адреса уменьшаются)\n");
  printf("Куча растет вверх (адреса увеличиваются)\n");

  // TODO: попробуй создать рекурсивную функцию и посмотри
  // как меняются адреса локальных переменных

  free(heap_var);
  free(heap_array);
}

/* ============================================================================
 * ЗАДАЧА 6: Динамический стек (бонус)
 * ============================================================================
 * Реализуй стек, который растет при необходимости
 */

typedef struct {
  int *data;
  int top;
  int capacity;
} DynamicStack;

void dynamic_stack_init(DynamicStack *s) {
  // TODO: начальная емкость = 4
}

bool dynamic_stack_push(DynamicStack *s, int value) {
  // TODO: если заполнен - удвой размер с помощью realloc
  return false;
}

bool dynamic_stack_pop(DynamicStack *s, int *value) {
  // TODO: можешь также уменьшать размер при малой заполненности
  return false;
}

void dynamic_stack_free(DynamicStack *s) {
  // TODO: освободи память
}

void test_task6() {
  printf("\n=== ЗАДАЧА 6: Динамический стек ===\n");
  DynamicStack s;
  dynamic_stack_init(&s);

  // Добавь больше элементов, чем начальная емкость
  for (int i = 0; i < 10; i++) {
    dynamic_stack_push(&s, i);
    printf("Pushed %d, capacity: %d\n", i, s.capacity);
  }

  dynamic_stack_free(&s);
}

/* ============================================================================
 * MAIN - Запуск всех тестов
 * ============================================================================
 */

int main() {
  printf("╔════════════════════════════════════════╗\n");
  printf("║   УПРАЖНЕНИЯ ПО СТЕКУ В C            ║\n");
  printf("╚════════════════════════════════════════╝\n");

  // Раскомментируй по мере выполнения задач
  test_task1();
  // test_task2();
  // test_task3();
  // test_task4();
  // demonstrate_stack_memory();
  // test_task6();

  return 0;
}