A project for Data Structures by Tyler Galpin during the Fall 2011.

This project took about one day to complete and was completed on December 6th, 2011.

The point of this project is to create a program that is capable of taking a string as input and determine if that string is a palindrome (reads the same backwards as forwards). The program is to implement our created libraries for the various data structures we covered throughout the year.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• Working linked list library
• Working stack library
• Understanding of string input and manipulation in language of choice
• Understanding of a sorting algorithm to reverse a string and check its value

A useful data structure to use in this program would be a stack, due to its FILO nature. You can fill a stack with the characters of a string, then simply start from the top of the original stack (you should already be there once it is filled!) and copy the characters in reverse order to the new stack. Then it is simply a matter checking each character against the corresponding character in the other string.

It only really checks for palindromes, so its use is limited to that, but the program could be used to create other string checking programs quite easily.

• linked list: The stack is based off of a linked list
• doubly linked list: The stack uses a doubly linked list.
• pointers: make up the backbone of the data structure
• malloc: needed in the creation of new stacks/nodes
• stack: Uses stacks for the strings.
• sorts: Uses sorting algorithms to change the order of characters
• File I/O: Used in main.c for test implementation

/*
 * Stack implementation -- Palindrome project
 *                             + EOCE Assignment
 *
 * Fall2011 Data Structures
 *
 * To compile: gcc -o [output file] [source code]
 *
 * Known problems: Currently does not account for different letter casing.
 *
 */
 
// Include files
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
// Create our node structure
struct node {
	char value;
	struct node *next;
	struct node *prev;
};
//Node contains pointers to next and previous nodes,
//and holds a character value.
typedef struct node Node;// From now on, 'Node' means the same
			 // as 'struct node' in this code
 
Node *stack, *top, *tmp; //initialize 3 other nodes
			 //stack (first node), top (last node)
 
void pushChar(char); // stack push function accepts a char and adds it to
		 // the stack
void popChar();	 // removes top node
void displayString(); //Displays current status of stack
 
// main function
int main()
{
	Node *reverse, *rtop, *tmp2; //Initialize nodes for mirrored string
			//reverse (first node) and rtop* (last)
	char input, junk; //initialize character variables
			//input goes in to stacks, junk catches
			//the junk data to keep the program moving.
	int choice, i=0; //Variable used in debugging interface
	puts("[Palindrome Program]: "); 
	puts("Find out if a lower case string is a palindrome.\n\n");
	puts("Enter a string: ");
	scanf("%c", &input);//Accept character
	while(input != '\n')//Loop used to accept a string until enter
			// is pushed
	{
		pushChar(input);//Send input char to stack
		scanf("%c", &input);//Accept next char
	}
/* //This section is the debugging interface.
	puts("Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]");
	scanf("%d", &choice);
	scanf("%c", &junk);
	while (choice != 0)
	{
		if (choice == 1)
		{
			input= '0';
			puts("Please add to the string: ");
			scanf("%c", &input);
			while(input != '\n')
			{
				pushChar(input);
				scanf("%c", &input);
			}
		}
		else if (choice == 2)
		{
			popChar();
		}
		else if (choice == 3)
		{
			displayString();
		}	
		puts("Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]");
		scanf("%d", &choice);
		scanf("%c", &junk);
	}
*/
	tmp=top; //Set tmp to the top of the original stack (the end of the string)
	reverse = (Node *) malloc(sizeof(Node)); //allocate space for the first character of the new string
	rtop=reverse; //Set the ending node of the new stack to the starting node (there is only one node)
	reverse->next=NULL; //Nothing ahead
	reverse->prev=NULL; //Nothing behind
	tmp2=reverse; //Set tmp2 to the first node
	reverse->value=top->value; //The first character of the new string is the same as the last of the original.
	tmp=tmp->prev; //Move the tmp node that is deal with the original string back one character
	while(tmp != NULL)//While tmp still is going backwards through the original string
	{
		if (reverse == rtop) //If there is only one node
		{
			tmp2= (Node *) malloc(sizeof(Node)); //Allocate space for tmp2
			rtop->next=tmp2; //Set the next character in the new string to tmp2
			tmp2->prev=rtop; //Have the new character (node) connect to the old last character
			rtop=rtop->next; //Move the title of the last character in the string (rtop) to the new end
			rtop->value=tmp->value; //The newest character of the new string 
						//is the same as the second to last of the original
			rtop->next=NULL; //Nothing beyond this node
			tmp=tmp->prev; //Move tmp another character back on the original string
		}
		else //if there is more than two nodes
		{
			tmp2=reverse;//Set tmp2 to the begining character
		       	while(tmp2 != NULL)//While it still has characters to find
		        {   
        	        	tmp2=tmp2->next;//Move next up on character in the new string
    	   		}   
      		  	tmp2 = (Node *) malloc (sizeof(Node)); //Allocate space for a new character node
        		rtop -> next = tmp2; //Point the old last character to the new last character
        		tmp2 -> prev = rtop; //Point it back to the old last character
	        	rtop = rtop -> next; //Make the new last character the official end of the string
        		rtop -> value = tmp -> value; // The new last character in the new string is the same as
							//whatever the current character tmp is pointing to in the
							//the original string
	        	rtop -> next = NULL; // Nothing beyond this character currently
			tmp=tmp->prev; //Move tmp back another character
		}
	}
	puts("\n[Original String]:");
	displayString();	//Show original string
	puts("[Backwards String]:");
	tmp2=reverse;		//Show original string reversed
	while(tmp2 != NULL) //While reversed string is still being gone through
	{
		printf("%c", tmp2->value); //Print the current character
		tmp2=tmp2->next; //Move to next character
	}
	puts("\n");
	tmp=stack;//Set tmp to beginning of original string
	tmp2=reverse;//Set tmp2 to beginning of reversed string
	//Palindrome checking algorithm below
	while(tmp != NULL && tmp2 != NULL) //while not at the end of either string
	{
		if (tmp->value == tmp2->value) //If the two current characters are the same
		{
			tmp=tmp->next; //move on to next character
			tmp2=tmp2->next; // for both strings
			if(tmp == NULL && tmp2 == NULL) //If at the end of both strings
			{
				puts("The string is a palindrome!\n");
			}
		}
		else //if any two characters do not match at any time
		{
			puts("The string is not a palindrome.\n");
			tmp=top->next; // move both tmp nodes to the end of their string to end loop
			tmp2=rtop->next;
		}
	}
	return(0);
}
 
void pushChar(char value) //return no value, accept char value
{
	if (stack==NULL) //if string is empty, add first character
	{
		stack = (Node *) malloc(sizeof(Node));
		top=stack;
		stack->next=NULL;
		stack->prev=NULL;
		tmp=stack;
		stack->value=value;
	}
	else if (stack == top) //if only one character, add new one
	{
		tmp= (Node *) malloc(sizeof(Node));
		top->next=tmp;
		tmp->prev=top;
		top=top->next;
		top->value=value;
		top->next=NULL;
	}
	else //more than one character, add new to end
	{
		tmp=stack;
		int i=0;
	       	while(tmp != NULL)
	        {   
        	        i++;
                	tmp=tmp->next;
       		}   
        	tmp = (Node *) malloc (sizeof(Node));
        	top -> next = tmp;
        	tmp -> prev = top;
        	top = top -> next;
        	top -> value = value;
        	top -> next = NULL;
	}
}
 
void popChar()//function is really only here for debugging
{
	tmp=top;
	tmp->prev->next=NULL;
	top=top->prev;
	tmp->prev=NULL;
	free(tmp);
}
 
void displayString()
{
	tmp=stack; //move to beginning of string
	while(tmp != NULL) //while characters remain in string
	{
		printf("%c", tmp->value); //print character
		tmp=tmp->next; //move to next
	}
	puts("\n");
}

This is how to compile and execute:

lab46:~/src/data/palindrome$ gcc -o palindrome main.c
lab46:~/src/data/palindrome$ ./palindrome

This was a fun program to write. It did not take very long, but it was challenging all the same, as there were many ways to the same result. I definitely felt as though I had gotten something significant done upon completion.

In performing this project, the following resources were referenced:

• Matt Haas + Class lecture
• C Programming Language O'Reilly Pocket Reference