// lifo.h  -- Stack of characters (dynamic storage)

struct node{
	node *next;
	char value;
};

struct lifo{
	node * next;	// whence we pop
};

// create and initialize a lifo
void createLifo(lifo& stack);

// push a new value into an existing lifo
void push(lifo& stack, char who);

// pop a value from a lifo
char pop(lifo& stack);

// check if a lifo is empty
int isempty(lifo& stack


// lifo.cpp  -- Stack of characters (dynamic storage)

#include "lifo.h"

#define NULL 0


// Create and initialize a lifo
// It returns a lifo whose next field is null and 
// whose count is 0
void createLifo(lifo& stack)
{
	stack.next  = NULL;
}


// push a new value into an existing lifo
void push(lifo& stack, char who)
{
	node *a = new node;

	a->next = stack.next;
	a->value = who;
	stack.next = a;
}

// pop a value from a lifo
char pop(lifo& stack)
{
	node *headNode;
	char who;

	if (stack.next != NULL) {
		headNode = stack.next;
		stack.next = stack.next->next;
		who = headNode->value;
		delete headNode;
		return who;
	}
	return '\0'; // You should never execute this
	          // statement (i.e. do not pop
			  // an empty stack)
}

// check if a lifo is empty
int isempty(lifo& stack)
{
	return (stack.next == NULL);
}


// main.cpp  -- Driver for lifo of characters.
//              Verify that a formula consisting of appropriately 
//              nested strings formed with the parentheses 
//              {,},[,],(,)  is well-formed.

#include <iostream>
#include "lifo.h"
using namespace std;

// Return true iff c1 and c2 are matching parentheses
int matching(char c1, char c2){
	if (((c1 == '(') && (c2 == ')')) ||
		((c1 == '[') && (c2 == ']')) ||
		((c1 == '{') && (c2 == '}')))
		return 1;
	else
		return 0;
}

enum {MAXLINE=256};

void main(void)
{
	char line[MAXLINE];
	int lcv;
	lifo stack;
	char c1;

	createLifo(stack);
	cout << "Enter a well formed string formed with {,},[,],(,): ";
	cin.getline(line, MAXLINE);
	lcv = 0;
	while((c1 = line[lcv++]) != '\0'){
		if (isspace(c1))
			;
		else if ((c1 == '{') || 
			(c1 == '[') ||
			(c1 == '('))
			push(stack, c1);
		else if ((c1 == '}') ||
			(c1 == ']') ||
			(c1 == ')')) {
			if (isempty(stack)) {
				cout << "Too many right parentheses" << endl;
				return;
			} else {
				if (!matching(pop(stack), c1)){
					cout << "The string has non-matching parentheses" << endl;
					return;
				}
			}
		}else{
			cout << "The string contains an illegal character" << endl;
			return;
		}
	}
	if (isempty(stack))
		cout << "The string is well formed" << endl;
	else
		cout << "Too many left parentheses" << endl;
}