// Will England
// Programming 1
// December 8, 1998
//
// prog6.cpp
//
// This program impliments a stack in a linked list using dynamic variables
//
// 5:40 PM 12-7-1998 Works as designed.  TODO:  Add support for {} and [].
//
// 7:29 PM This one is getting a bit wierd - we've successfully added support
// for {} and [], but having a hard time parsing what is missing from the 
// expression.  Maybe we just don't worry about it.


#include<iostream.h>
#include<string.h>

const int MAX = 80;

// the struct is a new concept, basically a user defined variable with 
// the capability of holding multiple datatypes.  We are using a self-
// referencing bit here to impliment a linked list.  The *nextptr is a 
// pointer to the next item, or node, in the linked list.

struct Nodetype
{
  int info;
  Nodetype *nextptr;
};


//FUNCTION PROTOTYPES
void createStack (Nodetype **);
int emptyStack (Nodetype **);
void push (Nodetype **, int);
void pop (Nodetype **, int &);
void topElement (Nodetype **, int &);
void input (char []);
int checkBrace(const char[], Nodetype **);


// Main function
int main()
{
	char expression[MAX];
	int checkVal;
	Nodetype *stack;
	createStack(&stack);
	cout << "Please enter a math expression, using parentheses: \n";
	input(expression);
	checkVal = checkBrace(expression, &stack);
	cout << "The returned value is " << checkVal << " \n";
		switch (checkVal){
			case 0:
				cout << "\nYour expression is unbalanced in some way.\n";
				break;
			case 1:
				cout << "\nYour expression is balanced.\n";
				break;
			case 2:
				cout << "\nYour expression is missing a ( somewhere.\n";
				break;
			case 3:
				cout << "\nYour expression is missing a { somewhere.\n";
				break;
			case 4:
				cout << "\nYour expression is missing a [ somewhere.\n";
				break;
			default:
				cout << "DainBramage!\n";
				break;
		}


	return(0);

}


// Function input gets a string from the keyboard.  Eventually, we will
// sanity check it.  Later.

void input(char problem[MAX])
{
	cin.getline(problem, MAX, '\n');
}

// Function checkBrace uses the stack to check to see if the parentheses
// are balanced.  


int checkBrace(const char string[MAX], Nodetype **ptr)
{
	int check, temp, flag = 1;
	// flag = 0 -- unbalanced
	// flag = 1 -- balanced
	// flag = 2 -- missing (
	// flag = 3 -- missing {
	// flag = 4 -- missing [

	//while (i < strlen(string) && (flag == 1))
	for (int i = 0; i<strlen(string) && flag == 1; i++)
	{
		switch (string[i]){
			case '(':
				push(ptr, 9);
				break;
			case '{':
				push(ptr, 18);
				break;
			case '[':
				push(ptr, 32);
				break;
			case ')':
			case '}':
			case ']':
				// yes, this sucks. Sorry.
				if (emptyStack(ptr) == 1)
				{
					flag = 0;
					break;
				};
				topElement(ptr, check);
				switch (string[i]){
					case ')':
						cout << ")";
						if (check == 9)
							pop(ptr, temp);
						else 
							flag = 2;
						break;
					case '}':
						cout << "}";
						if (check == 18)
							pop(ptr, temp);
						else
							flag = 3;
						break;
					case ']':
						cout << "]";
						if (check == 32)
							pop(ptr, temp);
						else
							flag = 4;
						break;
					default:
						break;
				} // end inner switch
			default:
				break;
		} // end outer switch
	} // end for loop
				
// and if we have never set the flag, check for an empty stack and return
	
	if (flag == 1)
		flag = emptyStack(ptr);
	return(flag);
} // end function


/////////////////////////////////////////////////////////////////////
//						White Box from here down				   //
// Code provided by John Vogt (vogtj@newmanu.edu) - not modifiable //
/////////////////////////////////////////////////////////////////////

// THIS FUNCTION INITIALIZES A STACK
// The ** shows that you are referencing a pointer to a pointer. We sent
// a pointer to a struct from the main function.
// 
// We just assign 0 to the value of the de-referenced ptr (or memory 
// address) which effectively creates a new stack.

void createStack (Nodetype **ptr)
{
  (*ptr) = 0;
}

// THIS FUNCTION DETERMINES IF THE STACK IS EMPTY
// again, using a pointer to a pointer, hence the **

int emptyStack (Nodetype **ptr)
{
  if ((*ptr) == 0)
    return(1);
  else
    return(0);
}

// THIS FUNCTION ADDS A NEW ELEMENT TO THE TOP OF THE STACK
// Here we use a new keyword, NEW.  This creates a new instance
// of the struct.  Then, we assign the data passed to the function
// to the struct.  Also, you can see where we assign the nextptr
// value.  

void push (Nodetype **ptr, int item)
{
  Nodetype *tempptr;

  tempptr = new Nodetype;
// assigns tempptr.info the value of item
  tempptr -> info = item;
// and give the current head-of-list value to the newly created node.
  tempptr -> nextptr = (*ptr);
// and sets the head of the list to *ptr.
  (*ptr) = tempptr;
}

// THIS FUNCTION REMOVES THE TOP ELEMENT OF THE STACK
// Another new keyword here, DELETE.  This removes the struct that 
// we created earlier and frees up the memory.  tempptr is not part 
// of the stack after the if{} statement, but it is still occupying
// memory.  

void pop (Nodetype **ptr, int  &item)
{
  Nodetype *tempptr;

// Note that we do not dereference the ptr value, we actually pass the
// memory location.  

  if(!emptyStack(ptr))
  {
// remember where the original top of list is
    tempptr = (*ptr);
// pop off the current item - it's passed back to main, if you want it.
    item = (*ptr) -> info; 
// set the *ptr to the next item in the list
    (*ptr) = (*ptr) -> nextptr;
// collect garbage
    delete tempptr;
  }
  else
	cout << "\n\nThe stack is empty!\n";

}

// THIS FUNCTION COPIES THE TOP ELEMENT FROM THE STACK

void topElement (Nodetype **ptr, int &item)
{
  if (!emptyStack(ptr))
    item = (*ptr) -> info;
  else
    cout << "\n\nThe stack is empty!\n";
}