Problem

Given a string from the input (no bound on the number of characters of the string), we want to verify whether the string is a valid expression of the following language:

S -> (S) | [S] | {S} | SS | e

So ()[], ([]{}) and []{()([])} are valid expressions, whereas ()[ and ([{]}) are not.

The program should read one such string as input and output 'VALID' or 'INVALID'.

Program

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

typedef struct stackNode {
  char c;
  struct stackNode *next;
} snode;

/* Debug: Prints the stack */
void printS(snode *_Top)
{
  printf("Top-> ");
  for (; _Top; _Top=_Top->next)
    printf("%c ", _Top->c);
  printf("\n");
}

/* inserts a char in the top of the stack */
void push(char _c, snode **_Top)
{
  snode *ptr = (snode *)malloc(sizeof(snode));
  if (!ptr)
    exit(-1);
  ptr->c = _c;
  if (!(*_Top))
  {
    ptr->next = NULL;
    *_Top = ptr;
  }
  else
  {
    ptr->next = *_Top;
    *_Top = ptr;
  }
}

/* returns the char at the top of the stack,
or 0 if the stack is empty */
char pop(snode **_Top)
{
  snode *ptr = *_Top;
  char c = 0;
  
  if (*_Top)
  {
    *_Top = ptr->next;
    c = ptr->c;
    free(ptr);
  }
  return c;
}

/* pops all elements of the stack and empties it */
void emptyStack(snode **_Top)
{
  for(;*_Top;)
    (void)pop(_Top);
}

void main()
{
  snode *Top = NULL;
  int c, cont=1;
  
  for (c=getchar(); (c!='\n') && (c!=0) && (c!=EOF) && cont; c=getchar())
  switch (c)
  {
    case '[':
    case '{':
    case '(':
      push(c, &Top);
      /* printS(Top); */
      break;
    case ']':
      if (pop(&Top)!='[')
      {
        printf("INVALID\n");
        cont=0;
      }
      /* printS(Top); */
      break;
    case '}':
      if (pop(&Top)!='{')
      {
        printf("INVALID\n");
        cont=0;
      }
      /* printS(Top); */
      break;
    case ')':
      if (pop(&Top)!='(')
      {
        printf("INVALID\n");
        cont=0;
      }
      /* printS(Top); */
      break;
    default:
      printf("Illegal character %c(%d) found!\n", c, c);
      cont=0;
  }
  if (cont)
    { if (pop(&Top)) printf("INVALID\n"); else printf("VALID\n"); }
  emptyStack(&Top);
}