testing-postfix-linklist

testing-postfix-linklist.cpp

#include <iostream>
using namespace std;

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

struct node * createNode(char data);
struct node * insertBack(struct node *header, char data);
struct node * insertFront(struct node *header, char data);
struct node *  deleteFront(struct node *);
struct node * deleteBack(struct node *header);
void insertAfter(struct node *afterNode, char data);
void display(struct node *header);
bool fistValidateParenthesis(struct node *header, char stringtoCheck[], int size);
bool isStackEmty(struct node *header);
char deleteFrontReturn(struct node *header);
bool paranthesisMatcher(char input1, char input2);


// algo 2
bool isOperand(char input1);
bool prcd(char, char);
void arithmeticInfixToPostfix(struct node *header, char stringtoCheck[], int size);
// int stackTop(struct stack *);

int main(void)
{
  char isValid;
  // init stack as link list
  struct node *header = NULL;

  // Input from the user - for now writing as Hard code for faster coding purposes
  char stringtoCheck[] = "A+B*C/D-E";
  int sizeOfString = sizeof(stringtoCheck) / sizeof(stringtoCheck[0]);
	// isValid =  fistValidateParenthesis(header, stringtoCheck, sizeOfString);
	// if (isValid)
	arithmeticInfixToPostfix(header, stringtoCheck, sizeOfString);
	system("PAUSE");
  return 0;
}

// int stackTop(struct stack *s) {
// 	return s->items[s->top];
// }



void arithmeticInfixToPostfix(struct node *header, char stringtoCheck[], int size) {

  // struct stack operatorStack,alphaStack;
	// initializeStack(&operatorStack);
	// initializeStack(&alphaStack);
  struct node *operatorStack = NULL;
  struct node *alphaStack = NULL;

	// A+B*C/D-E

	//bool valid = true;

	for (int j = 0; j < size - 1; j++) {

		char symb = stringtoCheck[j];
		//cout << endl << symb << endl << endl;
		// A*(B+C)/D
		if (isOperand(symb)) {
			cout << "PUSHING to alphaStack= "  << symb << endl;
			// push(&alphaStack, symb);
      alphaStack = insertFront(alphaStack, symb);

      // alphaStack = insertFront(header, currrentCharacter);
    }
    else {
			// while (!isStackEmty(operatorStack) && prcd(stackTop(&operatorStack), symb)) {
			while (!isStackEmty(operatorStack)) {
				// char operatorPop = pop(&operatorStack);
        char operatorPop = deleteFrontReturn(operatorStack);
        operatorStack = deleteFront(operatorStack);

				cout << "POPING & PUSHING to alphaStack= " << operatorPop << endl;
				// push(&alphaStack, operatorPop);
        alphaStack = insertFront(alphaStack, operatorPop);
        //now alphaStack is this
        cout << endl;
				// printStack(&alphaStack);
        display(alphaStack);
        cout << endl;
        //push(&operatorStack, symb);
			}
			//push(&operatorStack, symb);
			cout << "SYMBOL = " << symb << endl;
			if (  (symb == ')') || (symb == ']') || (symb == '}') ) {
				cout << "POPING= is symb is " << symb << endl;
				// pop(&operatorStack);
        operatorStack = deleteFront(operatorStack);
			}
			else {
				cout << "PUSHING to operatorStack= " << symb << endl;
				// push(&operatorStack, symb);
        operatorStack = insertFront(operatorStack, symb);
      }
    }
	}


	while (!isStackEmty(operatorStack)) //output any remaining operators 
	{
		// char topsymb = pop(&operatorStack);
		char topsymb = deleteFrontReturn(operatorStack);
    operatorStack = deleteFront(operatorStack);
		//add topsymb to the postfix string 
		// push(&alphaStack, topsymb);
    alphaStack=insertFront(alphaStack, topsymb);

	}

	cout << endl;
	cout << endl;
	cout << "######################Answer######################" << endl;

	// printStack(&alphaStack);
	display(alphaStack);
	alphaStack = deleteFront(alphaStack);

	cout << endl;
	cout << endl;


	//printStack(&alphaStack);
	//printStack(&operatorStack);

}

bool fistValidateParenthesis(struct node *header, char stringtoCheck[], int size) {
  bool valid = true;
	for (int j = 0; j < size - 1; j++) {

		char currrentCharacter = stringtoCheck[j];
    cout << "CHARACTER = " << currrentCharacter << endl;


		if (currrentCharacter == '(' || currrentCharacter == '[' || currrentCharacter == '{') {
			// cout << "PUSHING = " << currrentCharacter << endl;
			// push(s, currrentCharacter);
      header=insertFront(header, currrentCharacter);
		}

		if (currrentCharacter == ')' || currrentCharacter == ']' || currrentCharacter == '}') {
      
			char popedCharacter;
			if (isStackEmty(header)) {
				cout << "Stack link list was EMPTY with = " << endl;
				// cout << "Stack link list was EMPTY with = " << i << endl;
				valid = false;
				//return valid;
				break;
			}
      else {
        
        cout << "Link List *****BEFORE***** "<< endl;
        display(header);
        popedCharacter = deleteFrontReturn(header);
        header = deleteFront(header);
        // cout << "POPING = " << popedCharacter << endl;
        cout << "our currrent Character = " << currrentCharacter << endl;
        cout << "the character we jsut poped  = " << popedCharacter << endl;

        cout << "Link List *****AFTER***** "<< endl;
        display(header);

        if (paranthesisMatcher(popedCharacter, currrentCharacter)) {
					valid = true;
				}
				else {
					valid = false;
					//return valid;
					break;
				}
			}

		}

	}

  if (!isStackEmty(header)) {
		valid = false;
	}

	if (valid) {
		cout << "String is valid" << endl;
		return valid;
	}
	else {
		cout << "String is not valid(invalid)" << endl;
		return valid;
	}
}

bool isOperand(char input1)
{

  if (   input1 == '+' 
		|| input1 == '-' 
		|| input1 == '*' 
		|| input1 == '/' 
		|| input1 == '(' 
		|| input1 == ')' 
		|| input1 == '{' 
		|| input1 == '}' 
		|| input1 == '[' 
		|| input1 == ']'
		|| input1 == '^') {
		return false;
	}
	return true;
}

bool paranthesisMatcher(char input1, char input2)
{

	//cout << "First = " << input1;
	//cout << "Second = " << input2;

	if (input1 == '(' && input2 == ')') {
		return true;
	}

	if (input1 == '{' && input2 == '}') {
		return true;
	}

	if (input1 == '[' && input2 == ']') {
		return true;
	}

	return false;
}

bool prcd(char c1, char c2) {

	if ((c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-'))
		return true;

	if ((c1 == '^' ) && (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/'))
		return true;

	else if (c1 == '^'  && c2 == '^')
		return true;

	else if ((c1 == '*' || c1 == '/') && (c2 == '/' || c2 == '*'))
		return true;

	else if ((c1 == '+' || c1 == '-') && (c2 == '-' || c2 == '+'))
		return true;

	else if ((c1 == '*' || c1 == '/') && (c2 == '('|| c2 == '['|| c2 == '{'))
		return false;

	else if ((c1 == '(' || c1 == '[' || c1 == '{') && (c2 == '+' || c2 == '-'))
		return false;

	else if ((c1 == '+' || c1 == '-') && (c2 == ')'|| c2 == ']'|| c2 == '}'))
		return true;

	else if ( (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') && (c1 == '{' && c2 == '}') )
		return false;

	else
		return false;

}


bool isStackEmty(struct node *header) {
  if (header == NULL)
    return true;

  return false;
}
struct node * createNode(char item)
{
     struct node * temp;
     temp = (struct node *) malloc(sizeof(node));
     temp->data = item;
     temp->next = NULL;
     return temp;
}
struct node * insertBack(struct node *header, char data)
{
  // 1. Create node
  struct node * temp = createNode(data);
  struct node * headertemp;
  // 2. Check if the list is empty
  if (header == NULL)
  {
    header = temp;
    return header;
  }
  // 3. Find the end of list
  headertemp=header;

  while(headertemp->next != NULL)
      headertemp=headertemp->next;
  // 4. Connect new node to the end of list.
  headertemp->next = temp;
  // 5. Return header
  return header;
}
void insertAfter(struct node *afterNode, char data)
{
     // 1. Create node
     struct node * temp = createNode(data);
     // 2. Connect new node after the AfterNode
     temp->next=afterNode->next;
     // 3. Change the AfterNode pointer value so 
     //that it points to the new node.
     afterNode->next = temp;
}

struct node * insertFront(struct node *header, char data)
{
     // 1. Create node
     struct node * temp = createNode(data);
     // 2. Connect new node to the front of the list
     temp->next = header;
     // 3. Change the header value so that it points 
     // to the beginning of the LL.
     header=temp;
     // 4. Return new header
     return header;
}
void display(struct node *header)
{
    if (header == NULL)
        cout << "List is empty" << endl;
        
    struct node *temp = header;

    while (temp != NULL)
    {
        cout << temp->data << " --> ";
        temp=temp->next;
    }
    cout << endl;
}
struct node *  deleteFront(struct node *header)
{
	//2 --> 8 --> 75 --> 9 --> 3 -->
	//8 --> 75 --> 9 --> 3 -->
	// Check if node is only node
  struct node *temp;
	//Check if list is empty
	if (header == NULL) {
		return header;
	}
	//Assign header to headertemp
	temp = header;
  //set next node of headertemp to NULL, this will remove the node.
  header = header->next;
  //Free temp
  free(temp);
	//Return new header
	return header;

}
char deleteFrontReturn(struct node *header)
{
  char characterAfterDelete;

	//2 --> 8 --> 75 --> 9 --> 3 -->
	//8 --> 75 --> 9 --> 3 -->
	// Check if node is only node
  struct node *temp;

	//Assign header to headertemp
	temp = header;
  characterAfterDelete = header->data;

  //set next node of headertemp to NULL, this will remove the node.
  header = header->next;
  //Free temp
  free(temp);
	//Return new header
  return characterAfterDelete;
	//return header;
}
struct node * deleteBack(struct node *header)
{
	//Create a temp node (this will hold node that is going to be removed)
	// Create headertemp node (this node will be used to iterate through nodes, so we can
	// find the last node.
	struct node *temp, *headertemp;
	//Check if list is empty
	if (header == NULL) {
		return header;
	}
	//Assign header to headertemp
	headertemp = header;
	//Iterate through the list and set headertemp to last node.
	while (headertemp->next->next != NULL) {
		headertemp = headertemp->next;
	}
	//assign header temp's next node to temp (which is the node before end node)
	temp = headertemp->next;
	//set next node of headertemp to NULL, this will remove the node.
	headertemp->next = NULL;
	//Free temp
	free(temp);
	//Return new header
	return header;

}