415 - Balanceamento de Parênteses

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

typedef struct node Node;
struct node {
  char item;
  Node *next_node;
};

typedef struct stack Stack;
struct stack {
  Node *top;
};

Stack* create_stack() {
  Stack *stack = (Stack*) malloc(sizeof(Stack));
  stack->top = NULL;
  return stack;
}

void push(Stack *stack, char item) {
  Node *new_top = (Node*) malloc(sizeof(Node));
  new_top->item = item;
  new_top->next_node = stack->top;
  stack->top = new_top;
}

int is_empty(Stack *stack) {
  return (stack->top == NULL);
}

char pop(Stack *stack) {
  if (is_empty(stack)) return '0';

  Node *return_top = (Node*) malloc(sizeof(Node));
  char item = stack->top->item;
  stack->top = stack->top->next_node;
  free(return_top);
  return item;
}

char peek(Stack *stack) {
  if(is_empty(stack)) return '0';

  else return stack->top->item;
}

void free_list(Node *node) {
  if(node == NULL) return;

  free_list(node->next_node);

  free(node);
}

int is_balanced(char* sequence) {
  Stack* stack_parenthesis = create_stack();
  Stack* stack_brackets = create_stack();
  int i, balanced = 1;

  for(i = 0; i < strlen(sequence); ++i) {
    if(sequence[i] == '(') push(stack_parenthesis, sequence[i]);
    if(sequence[i] == '[') push(stack_brackets, sequence[i]);

    if(sequence[i] == ')') {
      if(pop(stack_parenthesis) == '0') {
        balanced = 0;
        break;
      }
    }

    if(sequence[i] == ']') {
      if(pop(stack_brackets) == '0') {
        balanced = 0;
        break;
      }
    }
  }

  if(!is_empty(stack_parenthesis) || !is_empty(stack_brackets)) balanced = 0;
  free_list(stack_parenthesis->top);
  free(stack_parenthesis);
  free_list(stack_brackets->top);
  free(stack_brackets);

  return balanced;
}

int main() {
  char sequence[256];
  int n, i;

  scanf("%d", &n);
  getchar();

  for(n; n != 0; --n) {
    fgets(sequence, 255, stdin);

    if(is_balanced(sequence)) printf("Yes\n");
    else printf("No\n");
  }

  return 0;
}