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

#define MAX_NODE_SIZE 128

typedef struct node {
  char data;
  struct node *next;
} Node;

typedef struct {
  Node *head;
  Node *crnt;
} List;

typedef struct {
  int max;
  int num;
  List stk;
} Stack;

#define head(stack) ((stack)->stk.head)
#define crnt(stack) ((stack)->stk.crnt)
#define num(stack) ((stack)->num)

static char pop(Stack *stack)
{
  char data = crnt(stack)->data;
  Node *next = crnt(stack)->next;

  free(crnt(stack));
  crnt(stack) = next;
  num(stack)--;

  return data;
}

static void final(Stack *stack)
{
  while (crnt(stack) != head(stack)) {
    Node *next = crnt(stack)->next;
    free(crnt(stack));
    crnt(stack) = next;
  }
}

static void push(Stack *stack, char data)
{
  Node *node;
  
  if (stack->num + 1 >= stack->max) {
    fprintf(stderr, "stack size is overflow, which must be smaller than %d\n", stack->max);
    final(stack);
    exit(1);
  }
  
  node = calloc(1, sizeof(*node));
  if (node == NULL) {
    fprintf(stderr, "Cannot allocate memory (stack size = %d)\n", stack->num);
    final(stack);
    exit(1);
  }
  
  node->data = data;
  node->next = crnt(stack);
  crnt(stack) = node;
  num(stack)++;
}

static void dbg(Stack *stack)
{
  Node *node;

  printf("max = %d\n", stack->max);
  printf("num = %d\n", num(stack));

  for (node = crnt(stack); node != head(stack); node = node->next)
    printf("%c\n", node->data);
}

static void init(Stack *stack, Node *head)
{
  stack->max = MAX_NODE_SIZE;
  stack->num = 0;
  head(stack) = head;
  crnt(stack) = head;
}

#define valid_or_return(stack, str, c, p)                            \
do {                                                                 \
  if (num(stack) == 0 || pop(stack) != c) {                          \
    printf("%s is invalid. %c is invalid character.\n", str, *p);    \
    final(stack);                                                    \
    return;                                                          \
  }                                                                  \
} while (0)

static void validate(char *str)
{
  Stack stack;
  Node head;
  char *p;

  init(&stack, &head);

  for (p = str; *p != '\0'; p++) {
    /** FIXME: not smart switch statement */
    switch (*p) {
    case '(':
    case '{':
    case '[':
      push(&stack, *p);
      break;
    case ')':
      valid_or_return(&stack, str, '(', p);
      break;
    case '}':
      valid_or_return(&stack, str, '{', p);
      break;
    case ']':
      valid_or_return(&stack, str, '[', p);
      break;
    default:
      /** skip this character */
      break;
    }
  }

  if (num(&stack) == 0)
    printf("%s is valid.\n", str);
  else
    printf("%s is invalid.\n", str);

  final(&stack);
}

static void task1()
{
  Stack stack;
  Node head;

  printf("task1\n");

  init(&stack, &head);

  push(&stack, 'A');
  push(&stack, 'B');
  push(&stack, 'C');
  push(&stack, 'C');
  pop(&stack);
  pop(&stack);
  dbg(&stack);

  /**
  do {
    int i;
    for (i = 0; i < stack.max; i++)
      push(&stack, '0');
  } while (0);
  */
  
  final(&stack);
}

static void task2()
{
  printf("task2\n");

  validate("(a)");
  validate("[a(b)c]");
  validate("{a(b)cd}");
  validate("{e}");
  validate("(a}");
  validate("[a(bc]");
  validate("{a(b)cd}[e}");
  validate("({}[()])");
  validate("({])");
  validate("({})])");
  validate("({}[()");
}

int main(void)
{
  task1();
  task2();
  return 0;
}