/*
	* This is a program on stack using C++ where u can evaluate wether an
	  expression has is valid or not

	* The are two important points to be kept in mind
		1. Your program should evaluate equal no. of right and left
		   braces i.e. left braces -  right brace = 0.
		2. For each left brace there is a right brace i.e.
		   for each opening brace there is ac losing brace.


	* Stack is an ordered collection of items into which new items
	  may be inserted and deletd at one end , called the TOP of the stack.

	* We can only delete or insert items from the top that is why it is
	  referred to as last in first out ( LIFO ). The last item enterd
	  is deleted first.


	* Over here we do this by simply using a stack.

*/

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

class stack
{
	public:
	int arr[100]; /* declaring the stack of a particular size */
	int top;
	int start , full ;
	int valid;

	public:
	stack()
	{
		top = start = -1;   /* initially the top and the
					starting point are same */

		full = 100 ;  /* the size of the array is
					initiallized to mark the end */
		valid = 1;  /* valid is used as a flag to mark wether overflow
			      or underflow of the stack  */
	}

	void push(int a);
	int pop();
};

void stack::push(int a)
{

	if(top == full-1 )
	{
		printf("\n the stack is full cannot enter any more values");

	}
	else
	{
		top++ ;
		arr[top] = a ;

	}
}

int stack::pop()
{

	int i;

	if(top == start)
	{
		printf("\n the stack is empty");
		printf("\n a garbage value is printed");
		valid = 0;

	}
	else
	{
		i = arr[top];
		top--;
		valid = 1;

	}

	if(valid == 1)
	{
		return i;
	}
}



void main()
{
	clrscr();
	stack s;
	char c , i ;
	int flag = 1 , count = 0;

	printf("\n enter you expression");
	printf("\nenter y to end your expression");


	while(1)
	{
		fflush(stdin);
		printf("\nenter :");
		scanf("%c",&c);

		if( c=='('|| c== '{'|| c== '[')
		{
			s.push(c);
			count++;  /*count is used to count the
				       number of braces */
		}

		if( c== ')'|| c== '}' || c==']')
		{
			i = s.pop();
			count--;
			 /* when an open closing brace is
			    encounters it checks for its pair */
			switch(c)
			{
				case ')':
						if( i == '(')
						flag = 1;   /*flag is used to
							      mark the validity
							      of the expression */
						else
						flag = 0;
						break;
				case '}':
						if( i == '{')
						flag = 1;
						else
						flag = 0;
						break;
				case ']':
						if( i == '[')
						flag = 1;
						else
						flag = 0;
						break;
			}


		}
		if( flag == 0 || c == 'y')
		 break;


	}

       if( flag == 0 || count != 0)
		printf(" not a valid string");
       else
		printf(" a valid string");
	/* if the flag is not marked valid in terms of every opening having its
	   closing brace the string becomes invalid or if the number of
	   opening and closing braces are not equal this is done by
	   count */

       getch();
}