/*
* adopted from textbook example, using array stack.  
* HBF
*/
#include <stdio.h>
#include <string.h>

#define MAX 100

void push(int stk[], int *top, int val);
void pop(int stk[], int *top);
int  peek(int stk[], int top);

int main(int argc, char *args[]) {
  //setbuf(stdout, NULL);
  int stk[MAX], top = -1;

  char temp, exp[MAX] = "(x+y*(a+b))";
  int i, flag = 1;
  //printf("Enter an expression : ");
  //gets(exp);

  for (i = 0; i < strlen(exp); i++) {
    if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
      push(stk, &top, exp[i]);
    }

    if ( exp[i] == ')' || exp[i] == '}' || exp[i] == ']' ) {
      if (top == -1) {
        flag = 0;
		break;
      } else {
        temp = peek(stk, top);
        pop(stk, &top);
        
        if ((exp[i] == ')' && temp != '(') || 
		    (exp[i] == '}' && temp != '{') || 
			(exp[i] == ']' && temp != '[')) {
          flag = 0;
   	      break;
		}
      }
    }
  }
  
  if (flag == 0 || top >=0)
     printf("\nInvalid");
  else {
	printf("\nValid");
  }
  

  return 0;
}

void push(int stk[], int *top, int val) {
  if (*top == MAX-1) {
    printf("\n STACK OVERFLOW");
  } else {
    *top = *top + 1;
    stk[*top] = val;
  }
}

void pop(int stk[], int *top) {
  if (*top == -1) {
    printf("\n STACK UNDERFLOW");
  } else {
    *top = *top - 1;
  }
}

int peek(int stk[], int top) {
  if (top == -1) {
    printf("\n STACK IS EMPTY");
    return -1;
  } else
    return (stk[top]);
}