Strings Code

4
Strings
Database to DNA!
INTRODUCTION
In this chapter we will learn how to represent a string in C. In computer science, we deal regularly with
strings everywhere, starting from details of customer in a service industry to DNA strands in the bio-
chemistry lab. C doesnt offer string as a basic built in data structure. We use char array or char pointer
to simulate string behavior. This type of representation is commonly known as C-Style String Represen-
tation. Once we learn basic string initialization, then we will learn about the C-library functions which
will be the building blocks for some user defined functions that we build towards the later of this chap-
ter. Moreover linked lists are also used to represent strings and store them. Most contemporary object
oriented programming languages, like Java and C#, support splitting a given string by delimiters. We
will create such a function in this chapter. This function will take a string and a delimiter to chop it and
will return a linked list of chopped strings. Later in the book, especially in the chapter on file handling
we will use this function for reading delimited notepad files and process them.
4.1 SOME KEY FACTS ABOUT STRINGS IN C

l C- Strings are nothing but NULL (\0) terminated character array.
l char *string; is a pointer to a C-style string.
l char string[20] is a C-Style string, that can hold 20 characters
l %s is used to scan string from console using scanf()..
l There is no need to give & sign while scanning a string from the console, because in C, strings
are nothing but null terminated character array and the array name is the pointer to itself.
l For using built-in C-Style string manipulation functions you need to include string.h in the
program.
l Strings are used to represent a variety of data, starting from name of a person in a database table to
a DNA strand of an individual.
l Fast String matching algorithms like Boyer Moore and KMP are used for matching DNA strands,
protein patterns, cancer cell repetition pattern, etc.
166 Data Structures using C
l String processing also finds application to find Plagiarism. Mostly Rabin-Karp algorithm is
used to detect it.
l String comparison algorithms/methods are used in different areas like Spell Checking, DNA
matching, Adaptive Text Prediction using T9 dictionary for mobile phones, etc.
4.2 C-STYLE STRING

A C-Style String is a null(\0) terminated character array. Here is a picture of a C-Style String
J A C O B \0
The Null Character

If the character array named Name stores this C-Style String then
Name[0] = J;
Name[1] = A;
Name[2] = C;
Name[3] = O;
Name[4] = B;
Name[5] = \0;
These C-Style strings can be initialized in so many ways as discussed later.
String Initialization
C-Style Strings can be initialized in many ways. From now on C-Style strings will be referred by just
string.
4.3 HOW TO INITIALIZE AT THE TIME OF DECLARATION

While declaring the string, we can initialize it. Here are few examples.
//Not Calculative. Codes is the pointer to the string
//We can store any length string.
char *codes=wxy8#455j%32;
//Calculative Initialization
//The name below has exactly 15 characters
//and thus it has been stored in
//a character array of 16 pockets. The
//last pocket of the array is for storing the null character.
char name[16]=Jacob Alexander;
4.4 HOW TO INITIALIZE STRINGS USING USER-DEFINED VALUES

Most of the cases you will be interested to initialize the string using user defined/supplied values. We
can use scanf( ) or gets( ) method for scanning the, user string inputs, but there is a difference. In case
there is a blank space in the input then if we try to scan it using scanf( ) it will scan only till that part when
the scanf( ) encountered a space. On the other hand if we use gets( ) we can scan strings with white
spaces in between them. Here is one example:
Strings (Database to DNA!) 167
char *name;
printf(Enter your name :);
fflush(stdin);
gets(name);
If you enter Brian Kernighan while asked for the name, the name array will store it like
name
B R i a n <space> K e r n i n g h a n \0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
<space> denotes a single space character
The integers denote the locations of the characters in the name. Later it will be shown how to extract
a part of a given string. Then we can use that function to extract the first, middle and the last name.
4.5 HOW TO INITIALIZE ONE STRING WITH ANOTHER STRING

One string can be initialized with another string or part of it (substring). Here is an example.
char *s=STEPANOV;
char *copy_of_a=a;
Here copy_of_a is a string and contents the value of a. This is done when the string a will be manipu-
lated and at the end we again need to use the initial value of the string a. In such cases value of a will be
copied in some other character arrays.
4.6 HOW TO INITIALIZE A STRING USING CHARACTER VALUES

We can use characters separately to fill a string. Here is one example.
char a[5]={A,B,C,D,E};
This above declaration is same as
//Easy and looks Professional.
char *a=ABCDE;
4.7 HOW TO INITIALIZE A STRING USING ASCII VALUES

In some real life applications, mostly in cryptography, we get ASCII values of characters instead of the
characters. Fortunately, C allows us to assign ASCII Values to assign a C String. The ASCII Value for
\0 (Null character that marks the end of a C-Style String) is zero. So the end value should be 0. Here is
an example.
char a[6]={65,66,67,68,69,0};
puts(a);
The output of this snippet will be
ABCDE
Initializing a string with ASCII values is the only possible solution when we need to put some una-
vailable (in the keyboard) characters in the array. For example think of a situation where we are
programming for a biological institute and we need to print human genome symbols for both genders
Here are pictures of the symbols:
G The Male Genome Symbol
E The Female Genome Symbol
The following program prints these patterns.

#include <stdio.h>
#include <string.h>
int main()
{
char s[2]={12,11};
printf("The Female Symbol :%c\n",s[0]);
printf("The Male Symbol :%c\n",s[1]);
return 0;
}
Here is the output of the program,
The Female Symbol:E
The Male Symbol:G
This scheme for initializing strings are highly used in cryptography and user interface design for
console based C programs. (You will find these applications in departmental stores).
4.8 INTRODUCTION TO SOME BUILT-IN TURBO C STRING LIBRARY

FUNCTIONS
The functions are grouped and discussed according to the jobs they perform.
Finding the Length of the String
Functions used:
strlen()
To find the length of the string we can use library method strlen(). The following code snippet explains
how to use strlen().
char *name=Sir Issac Newton;
printf(Name is of length :%d,strlen(name));
S i r I s s a c N e w t o n \0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
strlen() returns length of the string including the null character. So the length of the string returned is 16.
Concatenating Two C-Style Strings
Functions used:
l strcat()
l strncat()
strcat()
To concatenate two strings entirely (One is concatenate at the end of the other) we can use strcat () as
shown below.
char *firstname = John;
//Note the carefully left blank space before the family name.
//If this blank space is not left then, given name and family name will
//be close and not readable
char *familyname= Gottamann;

printf(Full Name :%s,strcat(firstname,familyname));
The output of this program will be John Gottamann

strncat()
This function is used when we need to concatenate up to some predefined number of characters of one
string at the end of the other. Here is an example.
char *firstname = John;
char *familyname= Gottamann;
printf(Full Name :%s,stnrcat(firstname,familyname,5));
This code will output John Got.
Comparing Two Strings
Functions used:
l strcmp()
l strcmpi() [ A macro ]
l stricmp() [ Same as strcmpi() but it is a function ]
l strncmp()
l strncmpi()
strcmp()
Two strings can be compared using the built-in library function strcmp(). This method compares two
strings considering case. That means if we compare the strings World and wOrLd then its compari-
son will tell us that the strings are not equal. In case the two passed arguments are equal then this
function returns zero. Otherwise this method will return a non zero value. Here is an example.
char *a=world;
char *b=worm;
if(strcmp(a,b)==0)
printf(Two Strings are same );
else
printf(They are unequal);
The output of this program snippet will be They are unequal as the two strings are unequal.
Besides using this built-in function you can write your own string comparison method. The algorithm
is to check letter by letter and then proceed until you encounter the null character or a mismatch.
There are two other methods that are used to compare strings. They are
strcmpi()
This functions compares two strings ignoring their cases. This function also returns 0 in case the two
string values are same. Two Strings World and wOrLd are same to strcmpi(). So the output of the
code snippet
char *s=World;
char *t=wOrLd;
if(strcmpi(s,t)==0)
printf(The two strings are same);
else
printf(The strings are different);
strncmp()
It accepts three arguments, two strings and one integer. It checks two strings up to that nth character. In
case they are same, then zero is returned. Otherwise, non zero value is returned. This function becomes
particularly handy, when we search for names in address-book programs. Suppose you want to find out
that how many names are there in the address-book that starts with Ja, then we can do something like
//Start searching
//Till the end of the address book
//pick the name of the person in a string called Name then
if(strncmp(Name,Ja,strlen(Ja))==0)
//Show the name
strlen(Ja) = 2. So the above piece of code will return success for all those entries in the
address book entries for which, the first 2 letters of the name are Ja, like Jacob, Jack, Jasmin,
Jana, etc.
But it will return false for Jonathon, because here only the first character matches.
strncmpi()
Same as strcmp(). The only difference is that this function is case-insenstive. This function compares
two strings up-to nth character ignoring their case. So in the above example (of address-book) the best
suited method is strncmpi() because that will match names starting with Ja, jA, JA and ja
This function also returns 0 on success and a non-zero value on failure.
Copying a String to Another
Functions used:
l stpcpy()
l strcpy()
l strncpy()
stpcpy()
This function copies all the characters of one string to other empty string till it reaches the null character.
So this function is appropriate when you are trying to add some more characters at the logical end of the
string being copied.
#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
char *a="FRANKFURT";
char *b=";
stpcpy(b,a);
puts(b);
getch();
return 0;
}
strcpy()
This function copies one string to another blank string. This function is mainly used for assigning the
new string variables.
#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
char *a="FRANKFURT";
char *b="Hamburg";
//We will swap the contents of the strings using strcpy
char *temp="";
clrscr();
printf("Before Swapping a = %s and b = %s\n",a,b);
strcpy(temp,a);
strcpy(a,"");
strcpy(a,b);
strcpy(b,"");
strcpy(b,temp);
printf("After Swapping a = %s and b = %s\n",a,b);
getch();
return 0;
}
The output of the program will be
Before Swapping a = FRANKFURT and b = Hamburg
After Swapping a = Hamburg and b = FRANKFURT
strncpy()
This function is similar to that of strcpy(), but it will copy up to the nth character of the source string.
Suppose we have the complete name for a person and we want to extract the first name. To do that, we
first need to find out the index of the first white space in the string. Then we need to copy part of the
string from starting to the index one less than the index of the first white space.
#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
char *name="Jacob Alexander";
char *fname="";
int i;
clrscr();
//Finding the location of the first whitespace.
for(i=0;name[i]!=' ';i++);
printf("%d ",i);
strncpy(fname,name,i);
//Putting the null character manually.
fname[strlen(fname)]='\0';
puts(fname);
getch();
return 0;
}
The output of this code will be
Jacob.
Changing Case of a String to Lower or to UPPER
Functions used
l strlwr()
l strupr()
strlwr()
This function returns a string which is a lower cased version of the argument string.
strupr()
This function returns a string which is a upper cased version of the argument string.
4.9 DESIGNING UTILITY TOOLS USING THESE TWO FUNCTIONS

Correcting Wrong Case Program in C/C++ (Using strlwr( ))
When PASCAL programmer migrate to C/C++, he often goes wrong syntactically, because in PASCAL
almost everything is written in CAPITAL letters while in C/C++ family, languages are written in small
letters. But there are some alimony also. In C/C++ the built-in constants (like M_PI in <math.h> ) are all
written in capital letters.
Assuming that there is no built-in constants used in a particular C/C++ Program, we can write an
application that can correct a wrong case C Program to correct case. Here is a typical input file.
//test.C
#INCLUDE <STDIO.H>
#INCLUDE <stdlib.h>
#include <CONIO.H>
int MAIN ()
{
puts ("I am here");
RETURN 0;
}
The program accepts the filename and then displays the corrected version of the program.
#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
char *line;
FILE *fp;
clrscr();
//Open the input wrong case program file
fp = fopen("D:\\test.C","r");
if(fp)
{
while(!feof(fp))
{
fgets(line,81,fp);
puts(strlwr(line));
}
}
else
perror("Error");
getch();
return 0;
}
Here is the output of the program.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int main ()
{
puts ("i am here");
return 0;
}
Try to extend this application that will take care of the following situations:
1. User defined constants like #define USD2INR 44.5 should not be changed to lower case.
2. User defined function name like draw_rectangle() should not be changed to lower case.
3. Inbuilt constant names (like M_PI_2) and macro names (like EOF) should not be changed to lower
case.
4.10 A TOOL FOR CHANGING CASE OF FEW CHOSEN ABBREVIATIONS IN

A FILE ( USING STRUPR())
Abbreviations are normally written in CAPITAL letters, like WHO, UNICEF, etc. It is really painful to
capitalize these words while editing a file. A small C program can be written that can do these changes
with little or no effort. Here is the strategy. The program will first open the file where these abbreviations
need to be changed and then read that file word by word. If any word exactly matches to any of these
abbreviations supplied to the code then the program will change those words to uppercase and display it.
We can redirect the corrected output to another text file.
Here is the program source.
#include <stdio.h>
#include <string.h>
#include <conio.h>
int main()
{
char *line;
FILE *fp;
clrscr();
fp = fopen("D:\\who.txt","r");
if(fp)
{
while(!feof(fp))
{
fscanf(fp,"%s",line);
if(strcmpi(line,"who")==0 ||
strcmpi(line,"unicef")==0)
printf("%s ",strupr(line));
else
printf("%s ",line);
}
}
else
perror("Error");
getch();
return 0;
}
Who.txt contains
WHO, the World Health Organization, had identified 7th June 2006 as Global Polio Eradication Day.
Who said that whosoever may tell you that these 2 drops are useless, you shouldnt listen to them. unicef
and who requested the state and central government to take necessary measures to assure that all the kids
up to the age of 5, get the polio vaccine as per who standard. unicef along with local ngos are trying their
best to ensure that no child is left out from this gigantic who - unicef effort. I will take my children to the
nearest polio booth. As a who doctor, I ask you to do so my friend! lets fight polio along with who,
unicef and ngos.
and the output of the program will be
WHO the World Health Organization had identified 7th June 2006 as Global Polio Eradication Day.
WHO said that whosoever may tell you that these 2 drops are useless, you shouldnt listen to them.
UNICEF and WHO requested the state and central government to take necessary measures to assure
that all the kids up to the age of 5, get the polio vaccine as per WHO standard. UNICEF along with
local NGOs are trying their best to ensure that no child is left out from this gigantic WHO - UNICEF
effort. I will take my children to the nearest polio booth. As a WHO doctor, I ask you to do so my friend!
Lets fight polio along with WHO, UNICEF and NGOs.
See the changes are made bold
Try extending this program with the following changes.
1. Try to make the changes (i.e. capitalization) interactively. For example there may be a sentence
like who doesnt know who? It actually means who doesnt know WHO ? Whenever an abbrevia-
tion from the pool of abbreviations is found, display the full line and then ask user whether to
change that abbreviation or not. If yes then make the case change, else skip it and continue search
for next matching abbreviation.
2. Create a pool of abbreviations
3. Allow users to add new abbreviations.
4.11 HOW TO REVERSE A STRING

Functions
l strrev( )
strrev ( )
This function returns a string which is reverse of the input string. In string processing reversing a string
is very trivial and important operation.
#include <stdio.h>
#include <conio.h>
int main()
{
char *s=ABACAS;
printf(Original String : %s\n,s);
printf(Reverse String : %s\n,strrev(s));
return 0;
}
This will display

Original String: ABACAS
Reverse String: SACABA
See the Palindrome Example in the Array Chapter to know how to use this method.
4.12 HOW TO SET CHARACTERS OF A STRING WITH ANOTHER

CHARACTER
Functions Used
l strset ()
l strnset()
strset()
This function is used to set all the characters of a string to another user given character. Here is a sample
code to explain how the function behaves.
#include <stdio.h>
#include <string.h>
int main()
{
char *s=abcdefghijklmnop;
char symbol = x;
printf(The original string is : %s\n,s);
printf(After setting with x :%s\n,strset(s,symbol));
return 0;
}
The original string is: abcdefghijklmnop
After setting with x: xxxxxxxxxxxxxxxx
strnset()
Sometime you may be interested to set only a particular number of characters from the start of the string.
In those situations, you have to use strnset( ). This function sets the first n characters of a string to
another character as given by the user.
#include <stdio.h>
#include <string.h>
int main()
{
char *s=abcdefghijklmnop;
char symbol = x;
printf(The original string is : %s\n,s);
printf(After setting with x up to first 4 characters
:%s\n,strnset(s,symbol,4));
return 0;
}
The original string is: abcdefghijklmnop
After setting with x up to first 4 characters: xxxxefghijklmnop
These functions can be used in computer secrecy projects. For example, you may have noticed that when
you buy something over internet using your credit card, the digits of the credit card are set to some
different characters. Sometimes all the characters are set and sometime some predefined range of char-
acters are set. These sorts of operations can be achieved using these two functions.
4.13 HOW TO FIND THE FIRST OCCURRENCE OF A CHARACTER

OF A SUBSTRING WITHIN ANOTHER STRING
Functions used:
l strchr()
l strstr()
strchr()
This function finds for the first occurrence of the sought character. Finding the occurrence of a character
in a string is very common and trivial operation in the string algorithms. Instead of writing a loop by
yourself you can use this function.
strchr(string_to_search, char_to_search) returns a pointer to the location where the sought character is
found for the first time. So by subtracting the base pointer to the string from the returned pointer we can
get the index of the characters first occurrence.
#include <stdio.h>
#include <conio.h>
#include <string.h>
int main()
{
char *s=Life is beautiful;
printf(The first occurrence of e is at %d\n,
strchr(s,e)-s);
return 0;
}
The first occurrence of e is at 3
strstr()
This function is used for finding out the first occurrence of a substring/word from a given string. This is
syntactically the same as strchr( ). This function returns the substring that starts from the given word. For
example if the given string is
char *s = Life is beautiful;
And the search pattern/word is is then if we call strstr() as strstr(s,is) then it will return
is beautiful
Using similar pointer arithmetic as in strchr() we can find the index location of the first occurrence of
the sought word. Here is the code
#include <stdio.h>
#include <conio.h>
#include <string.h>
int main()
{
char *s=Life is beautiful;
printf("The first occurrence of \"is\" is at
%d\n",strstr(s,"is")-s);
return 0;
}
The output of this code is
The first occurrence of is is at 5
4.14 HOW TO FIND THE LOCATION FROM WHERE TWO STRINGS START
TO DIFFER
Functions used:
l strspn()
l strcspn()
strspn()
This function is used to find the location of a string where it started to differ from another given string.
Here is a code snippet to demonstrate the functions behaviour.
#include <stdio.h>
#include <string.h>
#include <malloc.h>
int main()
{
char *s="12345678";
char *t="1234ffsf";
printf("The strings intersect at %d\n",strspn(s,t));
return 0;
}
This program prints
The strings intersect at 4
The point where from the strings start differing is sometime referred as their intersection point.
strcspn()
This is just the complimentary function of strspn(). This function finds that position in a string till when
it doesnt match with another string. Here is the code
#include <stdio.h>
#include <string.h>
#include <malloc.h>
int main()
{
char *s="12345678";
char *t="ffsf5678";
printf("The strings intersect at %d\n",strcspn(s,t));
return 0;
}
Here is the output of the program:
The strings intersect at 4
4.15 HOW TO CREATE THE DUPLICATE OF A STRING IN A

MEMORY-EFFICIENT MANNER
Function used: strdup( )
strdup()
This function creates a duplicate string of the passed argument. Very often we need to keep copies of a
string before we process it further. At the end of processing we can use this duplicate copy for some
operations. Here is a code to demonstrate its use.
#include <stdio.h>
#include <string.h>
int main()
{
char *s=Able was I as I saw Elba; //A Palindromic String!
char *dup_s = strdup(s);
printf(Duplicate String : %s\n,dup_s);
free(dup_s);
return 0;
}
This will print
Duplicate String: Able was I as I saw Elba
4.16 HOW TO TOKENIZE A GIVEN STRING

Function used:
l strtok ()
strtok()
This function is great for tokenizing needs. Do you remember that in Array chapter we tried to design
some clone to stringtokenizer of Java. The same type of application can be performed by this neat and
portable function in C. Suppose we have a string like
12,400
And we want to extract part of the string that is leading , and the trailing part. Here is the code:
#include <stdio.h>
#include <string.h>
int main()
{
char *s=12,400;
printf(Part before , is %s\n,strtok(s,,));
printf(Part after , is %s\n,strtok(NULL,,));
return 0;
}
This will print
Part before , is 12
Part after , is 400
So you may have noticed that to get the trailing part (Whichever part of the string is after the delimiter)
we need to call strtok(NULL,delimiter); after calling strtok(stringname, delimiter) ;
This function can be very handy to extract part of a code or phone number. Typically any land line
number has three parts. They are country code, city code and the phone number. We can write a small
program from which we will accept a phone number from the user and then extract these three sections
from that number. Here is the code and the sample output.
#include <stdio.h>
#include <string.h>
int main()
{
char s[16];
puts("Enter Number as [country_code-City_code-Phone Number ,
Eg 123-456-12345678] :" );
gets(s);
char *p;
p=strtok(s,"-");
printf("Country Code : %s\n",p);
p = strtok(NULL,"-");
printf("City Code : %s\n",p);
printf("Phone Number : %s\n",strtok(NULL,"-"));
return 0;
}
A Sample Run of this code
Enter Number as [country_code-City_code-Phone Number , Eg 123-456-12345678]:
91-011-25882746
Country Code: 91
City Code: 011
Phone Number: 25882746
Next in this chapter there is a function Split() that uses strtok() internally to tokenize a given line with
a given delimiter. If you want, you can jump there to understand how that works.
4.17 WHAT DO YOU MEAN BY PREFIX OF A STRING?

A string is said to be prefix of another string if the second one starts with the first. For example Won-
der is a prefix of the string Wonderful because Wonderful starts with Wonder.
Example 4.1 Write a program to find whether a string is a prefix of another string or not.
Solution
int isPrefix(char *Text,char *Pattern)
{
int Pref = 1;
int i = 0;
int j = 0;
if(Text[0]==Pattern[0])
{
for(i=0,j=0;i<strlen(Pattern);i++,j++)
{
for(i=0,j=0;i<strlen(Pattern);i++,j++)
{
if(Text[j]!=Pattern[i])
{
Pref = 0;
break;
}
}
}
else
Pref = 0;
return Pref;
4.18 WHAT DO YOU MEAN BY SUFFIX OF A STRING?

A string is said to be suffix of another string if the second one ends with the first. For example long is
a Suffix of the string Lifelong because Lifelong ends with long. Later in this chapter you will find
two functions startswith() and endswith() that can be re-written as wrappers of these two functions
isPrefix() and isSuffix(). Try that yourself!
Example 4.2 Write a program to find whether a string is a suffix of another string or not.
Solution
int isSuffix(char *Text,char *Pattern)
{
int i = 0;
int j = 0;
int Suff = 1;
if(Text[strlen(Text)-1]==Pattern[strlen(Pattern)-1])
{
for(i=strlen(Text)-2,j=strlen(Pattern)-2;j>=0;i--,j--)
{
if(Text[i]!=Pattern[j])
{
Suff = 0;
break;
}
}
}
else
Suff = 0;
return Suff;
}
4.19 WHAT DO YOU MEAN BY SUBSEQUENCE OF A STRING?

Sometimes people misunderstand subsequence as a substring, which is not correct. There is a subtle
difference between these two. A string is called a subsequence of the another string, if the characters of
the first occur in the second from left to right, but not necessarily in contiguous locations unlike substrings.
For example Wine is a subsequence of the string World is not enough.
Example 4.3 Write a program to find whether a string is subsequence of another string or not.
Assume that the alphabets present in both the strings are unique.
Solution This version works only when a and b do not have any duplicate characters.
int isSubSequence(char *a,char *b)
{
//Wonderful
//oder
int iss = 1;
int i = 0, j = 0 , k = 0;
int arr[30];
for(i=0;i<strlen(b);i++)
{
for(j=0;j<strlen(a);j++)
{
if(b[i]==a[j])
{
arr[k] = j;
k++;
}
}
}
for(i=0;i<k-1;i++)
{
if(arr[i+1]<arr[i])
{
iss = 0;
break;
}
}
return iss;
//O(MN)
}
This above function finds whether b is a subsequence of a or not, provided a and b do NOT have any
duplicate characters. The time complexity of the above code is O(MN + K) where M is the length of the
text, N is the length of the Pattern b.
Try Yourself: Try to modify this above program to allow duplicate in pattern a and b:
For example the above code will say that order is a subsequence for wonderful but it will fail to
identify that rental is a subsequence of ornamental because a occurs once before e and the
above program does not store location information of characters of the word.
Maintain a linked list of the positions for each character. Write a structure to store each character
and its location list. Now once you preprocess the main word (example Ornamental in the figure)
then you will be ready for checking whether another string (Like rental) is a subsequence of it or not.
The picture explains the rest for you. Try it!
How to Check whether a Word starts with a Prefix or not
int startsWith(char *string,char *pattern)
{
int start = 1;
int i=0;
for(;i<strlen(pattern);i++)
{
if(string[i]!=pattern[i])
{
start=0;
break;
}
}
return start;
}
We can also write the above method using strncmp as
int startsWith(char *string,char *pattern)
{
return strncmp(string,pattern,strlen(pattern));
}
How to Check whether a Word Ends with a given Suffix or not.

//This function returns the reverse of a string.
char* rstring(char *s)
{
char rs[30];
int i;
int j;
for(i=strlen(s)-1,j=0;i>=0;i--,j++)
rs[j]=s[i];
rs[j]='\0';
return rs;
}
//This function finds out whether the given string with the given
pattern
int endsWith(char *string,char *pattern)
{
char rs[20],rp[20];
strcpy(rs,rstring(string));
strcpy(rp,rstring(pattern));
return startsWith(rs,rp);//Notice how startsWith() is re-
used.
}
Example 4.4 Write a function to check whether a string matches the following basic asterisk (*)
wild character matches or not. Namely,
<pattern>*
*<pattern>
<pattern1>*<pattern2>
*<pattern>*
Solution Here is a simple function that uses the startsWith and endsWith function defined above in
order to match the four wildcard patterns mentioned. It doesnt work for a generalized combination of
those wildcard characters.
int wildCharMatch(char *string,char *pattern)
{
char t[20];
char *p = strchr(pattern,'*');
int starindex = p - pattern;
if(pattern[0]=='*')
{
if(pattern[strlen(pattern)-1]=='*')
{
strcpy(t,substring(pattern,1,strlen(pattern)-2));
return strstr(string,t)!=NULL?1:0;
}
else
{
return endsWith(string,t);
}
}
if(pattern[strlen(pattern)-1]=='*')
{
return startsWith(string,t);
}
if( i d ! 0 || i d ! l ( ) 1)
if(starindex!=0 || starindex!=strlen(pattern)-1)
{
strcpy(t,substring(pattern,0,starindex-1));
if(startsWith(string,t)==1)
{
strcpy(t,substring(pattern,starindex+1,strlen(pattern)-1));
return endsWith(string,t);
}
}
else
return 0;
}
How to accept a String of Words Delimited with Space and Return a Linked
List of Those Words as char*
typedef struct String
{
char s[20];
struct String *next;
}String;
String* push_back_String(String *last,char *s)

{
if(last==NULL)
{
last = (String *)malloc(sizeof(String));
strcpy(last->s,s);
last->next = NULL;
return last;
}
else
{
String *p = (String *)malloc(sizeof(String));
last->next = p;
strcpy(p->s,s);
p->next = NULL;
return p;
}
}
//This function splits the given string by the provided delimeter.

String* split(char *string,char *del)
{
String* h=NULL;
String* ch=NULL;
char *p;
p = strtok(string,del);
h = push_back_String(h,p);
ch = h;
while((p=strtok(NULL,del))!=NULL)
h = push_back_String(h,p);
return ch;//Returning the head of the list
}
How to Count the Total Number of Words in a Sentence
int countWords(String *words)
{
int totalwords = 0;
String *cwords=words;
for(;cwords!=NULL;cwords=cwords->next)
totalwords++;
return totalwords;
}
How to Replace a Word by another Word from a Phrase
char* replace(char phrase[81],char *word,char *newword)
{
int count = 0;
int i,j=0;
String *words = NULL;
words = split(phrase," ");
String *cwords = NULL, *modphrase = NULL;
char newphrase[81];
for(;words!=NULL;words=words->next)
{
if(strcmp(words->s,word)==0)
{
cwords = push_back_String(cwords,newword);
count++;
if(count==1)
modphrase = cwords;
cwords = push_back_String(cwords," ");
}
else
{
cwords = push_back_String(cwords,words->s);
count++;
if(count==1)
modphrase = cwords;
for(;modphrase!=NULL;modphrase=modphrase->next)
for(i=0;i<strlen(modphrase->s);i++,j++)
newphrase[j]=modphrase->s[i];
newphrase[j]='\0';
return newphrase;
}
When called with the following client code

char phrase[]={"A hundred fathoms a hundred fathoms away from home."};
strcpy(t,replace(phrase,"fathoms","miles"));
puts(t);
it prints the following string.
A hundred miles a hundred miles away from home.
How to Delete all Occurrences of a given Word from a Sentence
char* DeleteWord(char *sentence,char *word)
{
int i=0,j=0;
char cs[200];
char modifiedsentence[200];
int count = 0;
String *cwords = NULL;
String *modifiedline = NULL;
strcpy(cs,sentence);
String *words = split(cs," ");

{
if(strcmpi(words->s,word)!=0)
{
cwords = push_back_String(cwords,words->s);
count++;
if(count == 1)
modifiedline = cwords;
}
for(;modifiedline!=NULL;modifiedline=modifiedline->next)
for(i=0;i<strlen(modifiedline->s);i++,j++)
modifiedsentence[j] = modifiedline->s[i];
modifiedsentence[j] = '\0';
return modifiedsentence;
}
Here is a client code snippet that demonstrates the usage of the above function.
strcpy(t,"Anger is never without reason but seldom with a good one);
strcpy(t,DeleteWord(t,"without"));
strcpy(t,DeleteWord(t,"reason"));
strcpy(t,DeleteWord(t,"but"));
strcpy(t,DeleteWord(t,"seldom"));
strcpy(t,DeleteWord(t,"with"));
strcpy(t,DeleteWord(t,"a"));
strcpy(t,DeleteWord(t,"one"));
puts(t);
This outputs
Anger is never good
How to Display Text in a Word Wrap Mode

void wordWrap(char *longsentence,int wordsperline)
{
int count = 0;
String *words = NULL;
words = split(longsentence," ");
{
printf("%s ",words->s);
count++;
if(count==wordsperline)
{
count=0;
printf("\n");
}
}
}
When called by the following client code
int main()
{
char *t;
strcpy(t,"Few people are capable of expressing with equanimity
opinions which differ from the prejudices of their social
environment. Most people are even incapable of forming such
opinions Albert Einstein");
wordWrap(t,3);//Wraps the text with maximum three words per line
getch();
return 0;
}
it generates the following output:
Few people are
capable of expressing
with equanimity opinions
which differ from
the prejudices of
their social environment.
Most people are
even incapable of
forming such opinions
Albert Einstein
How to Demonstrate the Random Cipher Encryption of a Text
char* encrypt(char *pwd)
{
char *epwd;
int i,j;
//Add more symbols if you want
char a[]={'a','b','c','d','e','f','g','h','i','j','k'
,'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
'1','2','3','4','5','6','7','8','9','0'};
char b[]={'0','9','8','7','6','5','4','3','2',
'1','z','y','x','w','v','u','t','s','r','q','p','o','n','m','l',
'k','j','i','h','g','f','e','d','c','b','a'};
for(i=0;i<strlen(pwd);)
{
{
if(pwd[i]==a[j])
{
epwd[i]=b[j];
i++;
}
}
}
epwd[i]='\0';
return epwd;
}
How to Decrypt a Text Encrypted with the Above Function
char* decrypt(char *pwd)
{
char *dpwd;
int i,j;
char a[]={'a','b','c','d'
,'e','f','g','h'
,'i','j','k','l'
,'m','n','o','p','q'
,'r','s','t','u','v'
,'w','x','y','z','1'
,'2','3','4','5','6'
,'7','8','9','0'};
char b[]={'0','9','8','7'
,'6','5','4','3','2'
,'1','z','y','x','w'
,'v','u','t','s','r'
,'q','p','o','n','m'
,'l','k','j','i','h'
,g','f','e','d','c'
,'b','a'};
{
{
if(pwd[i]==b[j])
{
dpwd[i]=a[j];
i++;
}
}
}
dpwd[i]='\0';
return dpwd;
}
,'l','k','j','i','h'
,g','f','e','d','c'
,'b','a'};
{
{
if(pwd[i]==b[j])
{
dpwd[i]=a[j];
i++;
}
}
}
dpwd[i]='\0';
return dpwd;
}
How to Represent a String as a Linked List of Characters
typedef struct character
{
char c;
struct character *next;
struct character *prev;
}character;
typedef character* string;

How to Create a New String Using the Above Linked List Representation of
the Strings
string push_back(character *last,char c)
{
if(last==NULL)
{
last = (character *)malloc(sizeof(character));
last->c = c;
last->next = NULL;
last->prev = NULL;
return last;
}
else
{
character *p = (character *)malloc(sizeof(character));
last->next = p;
p->prev = last;
p->c = c;
return p;
}
}
string createNew(char *ns)
{
character *cs = NULL;
character *s = NULL;
int i = 0;
for(i=0;i<strlen(ns);)
{
s = push_back(s,ns[i]);
i++;
if(i==1)
cs = s;
}
s=push_back(s,'\0');
return cs;
}
How to Display such a String Represented by a Linked List

void displayString(string s)
{
for(;s!=NULL;s=s->next)
{
if(s->c=='\0')
break;
else
putc(s->c,stdout);
}
}
How to Extract Substring of a String Starting from an Index and Ending at
Another Index
char* substring(char *string,int start,int end)
{
char *temp;
int i,j;
for(i=start,j=0;i<=end;i++,j++)
temp[j] = string[i];
temp[j] = '\0';
return temp;
}
How to Trim a Specified Number of Characters from the Left of a Given String
char* trimleft(char *word,int index)
{
char *tl;
int last = strlen(word);
strcpy(tl,substring(word,index,last));
return tl;
}
This function will trim the specified number of characters from the left of the given word. Here is
how to call the function.
trimleft(,Wonderful,1) will return Wonderful
How to Trim a Specified Number of Characters from the Right of a Given String
char* trimright(char *word,int index)
{
char *t;
int x = strlen(word);
strcpy(t,substring(word,0,x-index-1));
return t;
}
The function will trim the specified number of characters from the right of the given word. Here is
how to call the function
trimright(Lovely,2) will return Love
How to Pad n Number of Specified Characters to the Left of a String
char* padleft(char *word,char c,int n)
{
char *t;
int i;
for(i=0;i<n;i++)
t[i]=c;
t[i]='\0';
strcat(t,word);
return t;
}
The function will pad n number of characters c at the left of the word. Here is an example run.
padleft(100.00,$,1) will return $100.00
How to Pad n Number of Specified Characters to the Right of a String
//In this function we have not used strcat()
char* padright(char *word,char c,int n)
{
char *t;
int i,j;
for(i=0;i<strlen(word);i++)
t[i]=word[i];
for(j=i;j<n+i;j++)
t[j]=c;
t[j]='\0';
return t;
}
This function will pad the given word at the left with the given number of characters at the right side.
Like if the function is called like padright(chapter0,?,2) will return chapter0??
We can use these building block functions to create the following functions.
How to Trim White Spaces from Both Sides of a Word
//It is assumed that the word passed as a parameter to this function has
//whitespaces on both sides.
char* trim(char *word)
{
char *templ;
char *tempr;
int i = 0;
int index = 0;
for(;i<strlen(word);i++)
{
if(word[i]!=' ')
{
index = i;
break;
}
}
strcpy(templ,trimleft(word,index));//Left whitespaces trimmed
for(i=0;i<strlen(templ);i++)
{
if(templ[i]==' ')
break;
}
strcpy(tempr,trimright(templ,i));//Right whitespaces trimmed
return tempr;
How to Pad a String with a Specified Character and an Alignment Choice

enum {ALLIGN_LEFT = -1, ALLIGN_CENTER, ALLIGN_RIGHT};
char *pad(char *word,int totalwidth,char c,int allignment)

{
//-1 left 0 center 1 right
char temp[100];
int len = strlen(word);
if(allignment==ALLIGN_LEFT)
{
//If we have to make the string appear left alligned,
//we have to pad characters to its right hand side
strcpy(temp,padright(word,c,totalwidth-len));
return temp;
}
if(allignment==ALLIGN_RIGHT)
{
//If we have to make the string appear right alligned,
//we have to pad characters to its left hand side.
strcpy(temp,padleft(word,c,totalwidth-len));
return temp;
}
if(allignment==ALLIGN_CENTER)
{
//If we have to make the string appear center alligned
//we shall have to pad same number of characters to its both ends.
strcpy(temp,padleft(word,c,(totalwidth-len)/2));
strcpy(temp,padright(temp,c,(totalwidth-len)/2));
//Warning! We might be less than the total number of characters,
//So lets add them at the end.
if(strlen(temp)<totalwidth)
strcpy(temp,padright(temp,c,totalwidth-strlen(temp)));
return temp;
}
}
Here is a sample client code snippet that demonstrates the above function pad():
strcpy(t,pad("Love",20,'.',ALLIGN_LEFT));
puts(t);
printf("Length = %d\n",strlen(t));
strcpy(t,pad("Love",20,'.',ALLIGN_CENTER));
puts(t);
strcpy(t,pad("Love",20,'.',ALLIGN_RIGHT));
puts(t);
And here is the output of this code..
Love................
Length = 20
........Love........
Length = 20
................Love
Length = 20
How to Remove all the Blank Spaces in a Phrase
char* sweepwspace(char *phrase)
{
int i = 0,j=0;
char temp[100];
for(;i<strlen(phrase);i++)
{
if(phrase[i]!=' ')
{
temp[j]=phrase[i];
j++;
}
}
temp[j]='\0';
return temp;
}
How to Extract all the k-grams of a String for a given k
String* kgrams(char *line,int k)
{
int i = 0;
int count = 0;
char temp[50];
//deleting all the white spaces
strcpy(line,sweepwspaces(line));
String *words = NULL,*ktokens = NULL;
int total = strlen(line)-k-1;
for(;i<=total;i+=k)
{
strcpy(temp,substring(line,i,i+k-1));
words = push_back_String(words,temp);
count++;
if(count == 1)
ktokens = words;
}
return ktokens;
}
k-grams are used for generating the digital fingerprint of intelligent materials like a document. See the
end of chapter on file. There is an algorithm called Winnowing which uses k-grams to detect plagiarism.
Different nearest neighbor identification algorithms, like Near Duplicate Document finding in a web
search uses k grams.
How to check whether a String is a Valid UPC (Universal Product Code)
Code or not
Each product being sold in the market has a different product code. This code is known as Universal
Product Code or UPC in short. This concept was first introduced for making grocery store checkout
time faster. The first digit in the UPC tells about the type of the product. The last digit (6 in this case) is
the check digit. This digit tells the scanner whether the code had been read properly or not.
The algorithm to check whether UPC is valid or not is popularly known as Module 10 algorithm or as
Luhn Algorith according to its discoverer Hans Peter Luhn.
Step 1: The even place digits are added
Step 2: The number at odd places are multiplied by 3 and then the sum of the digits of all generated
numbers are found.
Step 3: If the total of the numbers obtained in step 1 and step 2 is divided by 10.
Step 3: If the remainder is 0 that means the UPC code is valid. Otherwise it means that the UPC code is
invalid.
int digsum(int number)
{
int sum = 0;
while(number!=0)
{
sum+=number%10;
number/=10;
}
return sum;
}
int isValidUPC(char *UPC)

{
String *kgs = kgrams(UPC,1);
int count = 1;
int EvenSum = 0;
int OddSum = 0;
for(;kgs!=NULL;kgs=kgs->next)
{
if(count%2!=0)
OddSum+=digsum(atoi(kgs->s));
else
EvenSum+=atoi(kgs->s);
count++;
}
return (EvenSum + 3 * OddSum)%10==0;
4.20 HOW TO CHECK WHETHER A STRING IS A VALID ISBN OR NOT

The algorithm to check whether an ISBN number is valid or not is just a dialect of 10 module algorithm
described as follows.
int isValidISBN(char *ISBN)

{
String *kgs = NULL;
int weight = 1;
int sum = 0;
if(strlen(ISBN)!=10)
return 0;
else
{
kgs = kgrams(ISBN,1);
for(;kgs->next!=NULL; kgs = kgs->next ,weight++)
sum+=atoi(kgs->s)*weight;
if(sum%11==atoi(kgs->s))
return 1;
else
return 0;
}
4.21 HOW TO CHECK VALIDITY OF A SOCIAL INSURANCE NUMBER (SIN) CODE

In Canada, every person has a social insurance number which
is unique and used for identification. This number can be vali-
dated with a variant of Check Digit or Module 10 algorithm.
This algorithm is implemented in the function below.
int isValidSIN(char *SIN)
{
String *kgs = kgrams(SIN,1);
int count=1;
int EvenSum = 0;
int OddSum = 0;
{
if(count%2==0)
//Find digit sum of numbers we get by multiplying the
digits at
//even locations.
EvenSum+=digsum(atoi(kgs->s)*2);
else
OddSum+=atoi(kgs->s);
count++;
}
return (EvenSum + OddSum )%10==0;

}
4.22 HOW TO CHECK WHETHER A GIVEN CREDIT CARD NUMBER IS

VALID OR NOT
To validate a credit card number three things need to be tested. First of all we need to find out whether
the card has a proper length for its type or not. For example, if the card is of type VISA then the length
of the card needs to be validated. Once that is done, then it is checked whether the card number starts
with a predefined globally accepted prefix for VISA type cards or not. Once all these criteria are passed
then the number is validated using check digit or Luhn or Module 10 algorithm.
The following two functions implement the algorithm.
int IsValidCheckDigit(char *ccn)
{
String *kgs = kgrams(ccn,1);
int count = 1;
int EvenSum = 0;
int OddSum = 0;
{
if(count%2==0)
EvenSum+=digsum(2*atoi(kgs->s));
else
OddSum+=digsum(atoi(kgs->s));
count++;
}
return (EvenSum + OddSum)%10==0;
}
int isValidCreditCard(char *type, char *ccn)

{
if(strcmpi(type,"American Express")==0)
{
if(strlen(ccn)==15)
{
if(startsWith(ccn,"34")==1 || startsWith(ccn,"37")==1)
{
if(IsValidCheckDigit(ccn)==1)
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Carte Blanche")==0 || strcmpi(type,"Diners Club")==0 )
{
if(strlen(ccn)==14)
{
if(startsWith(ccn,"300")==1
|| startsWith(ccn,"301")==1
|| startsWith(ccn,"38")==1)
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Discover")==0 )
{
if(strlen(ccn)==16)
{
if(startsWith(ccn,"6011")==1)
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Enroute")==0 )
{
if(strlen(ccn)==15)
{
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"JCB")==0 )
{
if(strlen(ccn)==15 || strlen(ccn)==16)
{
|| startsWith(ccn,"2131")==1 || startsWith(ccn,"1800")==1)
{
return 1;
else
return 0;
}
l
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Maestro")==0 )
{
if(strlen(ccn)==16)
{
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Mastercard")==0 )
{
if(strlen(ccn)==16)
{
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Solo")==0 )
{
if(strlen(ccn)==16 || strlen(ccn)==18 || strlen(ccn)==19)
{
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Switch")==0 )
{
if(strlen(ccn)==16 || strlen(ccn)==18 || strlen(ccn)==19)
{
if(startsWith(ccn,"4903")==1 ||
startsWith(ccn,"4905")==1
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Visa")==0 )
{
if(strlen(ccn)==13 || strlen(ccn)==16)
{
if(startsWith(ccn,"4")==1)
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
if(strcmpi(type,"Visa Electron")==0 )
{
{
if(strlen(ccn)==16)
{
||startsWith(ccn,"4917")==1 || startsWith(ccn,"4913")==1)
{
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
4.23 HOW TO CHANGE THE CASE OF A SENTENCE TO SENTENCE CASE

Sometimes we miss the capitalization after fullstop while composing a letter or a doc. We can correct
our text by passing them to the function below. This function makes sure that every character that
follows a dot (.) is in upper case.
char* SentenceCase(char *sentence)
{
int i,index=0;
for(i=0;i<strlen(sentence);i++)
{
if(sentence[i]=='.')
sentence[i+1]=toupper(sentence[i+1]);
}
return sentence;
}
When called with the following client code snippet
char *t;
strcpy(t,I am here.lets folk again!);
strcpy(t,SentenceCase(t));
puts(t)
the following output is generated.
I am here.Lets folk again!
Try Yourself: Try to change the above program so that it can handle random capitalization. For example,
a call to SentenceCase() like
strcpy(t,I am here.lETs FoLk agAin!);
strcpy(t,SentenceCase(t));
puts(t)
should output
I am here. Lets folk again.
4.24 HOW TO TOGGLE THE CASE OF THE LETTERS OF A SENTENCE

This function toggles the case of each letter in the sentence or the phrase passed.
char* ToggleCase(char *sentence)
{
int i,index=0;
char *toggledsentence;
for(i=0;i<strlen(sentence);i++)
{
if(sentence[i]>='a' && sentence[i]<='z')
{
toggledsentence[i] = toupper(sentence[i]);
continue;
}
if(sentence[i]>='A' && sentence[i]<='Z')
{
toggledsentence[i] = tolower(sentence[i]);
continue;
}
else
{
toggledsentence[i] = sentence[i];
continue;
}
}
toggledsentence[i]='\0';
return toggledsentence;
}
When called with the following client code snippet
char *t;
strcpy(t,I am here.lets fOlk agAin!);
strcpy(t, ToggleCase(t));
puts(t)
i AM HERE.LETS FoLK AGaIN!
How to Calculate the Frequency of a given Word in a Sentence
int WordFrequency(char *sentence,char *word)
{
int freq = 0;
char *csen;
strcpy(csen,sentence);
String *words = split(csen," ");
if(strcmp(words->s,word)==0)
freq++;
return freq;
}
To know how this function can be called, see the next question.
How to Display the Word Histogram of a given Sentence
void WordHistogram(char *sentence)
{
char *longsentence;
char *mostusedword;
strcpy(longsentence,sentence);
String *words = split(sentence," ");
printf("%s %d\n",words->s,WordFrequency(longsentence,
words->s));
}
Here is a client code snippet that demonstrates how to use the above
function.
strcpy(t,"Anger is never without a reason but it is seldom with a good

one");
WordHistogram(t);
The following output is generated for this client call.
Anger 1
is 2
never 1
without 1
a 2
reason 1
but 1
it 1
is 2
seldom 1
with 1
a 2
good 1
one 1
Try Yourself: As you can see this program shows same word multiple times if it occurs multiple times
in the sentence. Create an user defined Word-Frequency List to remove this duplication.
How to Find the Most Used Word in a Sentence/Phrase/String
char* MostUsedWord(char *sentence)
{
char longsentence[100];
int maxf;
char mostusedword[30];
strcpy(longsentence,sentence);
String *words = split(sentence," ");
maxf = WordFrequency(longsentence,words->s);
if(maxf<WordFrequency(longsentence,words->s))
strcpy(mostusedword,words->s);
return mostusedword;
}
When called with the following client code snippet,
char *t,*s;
strcpy(t,"If you miss the train I'm on you will know that I am gone");
strcpy(s,MostUsedWord(t));
puts(The most used word is );
puts(s);
The most used word is
you
How to Find whether a Word/Phrase is an Anagram of Another One
An anagram is a different combination of same characters that occur in a word or phrase. While compar-
ing whether two words/phrases are anagrams of one another or not we check for the frequencies of all
the characters in two strings. If they match, then the two strings are anagram of one another. Punctuations
and special characters are discarded. For example Great Taste! and Gear at Test! are the anagrams
of one another. While generating anagrams all the punctuations are discarded.
typedef struct CharacterWithFrequency

{
char c;
int freq;
struct CharacterWithFrequency *next;
}CharacterWithFrequency;
int isAnagram(char *phrase,char *diffcomb)

{
int flag = 0;
CharacterWithFrequency *s=NULL,*s1=NULL;
CharacterWithFrequency *t=NULL,*t1=NULL;
CharacterWithFrequency cf;
CharacterWithFrequency *temp=NULL;
int anagram = 1;
int i=0,j=0;
int count=0;
if(strlen(phrase)!=strlen(diffcomb))
anagram = 0;
else
{
//Creating the histogram of characters for the first string
for(;i<strlen(phrase);i++)
{
cf.freq = 0;
cf.c = phrase[i];
for(j=0;j<strlen(phrase);j++)
{
if(phrase[i]==phrase[j])
{
cf.freq++;
}
}
if(!Contains(s1,cf.c))
{
s = push_back(s,cf);
}
count++;
if(count==1)
s1 = s;
}
count = 0;
i=0;
//Creating the histogram of characters of the second string
for(;i<strlen(diffcomb);i++)
{
cf.freq = 0;
cf.c = diffcomb[i];
for(j=0;j<strlen(diffcomb);j++)
{
if(diffcomb[i]==diffcomb[j])
{
cf.freq++;
}
}
if(!Contains(t1,cf.c))
{
t = push_back(t,cf);
}
count++;
if(count==1)
t1 = t;
}
}
//Voila! Now we have both the histogram of strings. So we are ready to run
//through these histograms to see if they match or not.
for(;s1!=NULL;s1=s1->next)
{
temp = t1;
//Two words which are anagram of one another
//s=doctorwho
//d-1
//o-3
//c-1
//t-1
//r-1
//w-1
//h-1
//t=torchwood
//t-1
//o-3
//r-1
//c-1
//h-1
//w-1
//d-1
for(;temp!=NULL;temp=temp->next)
{
if(s1->c==temp->c)
{
flag=1;
//Well, we have the same character in both the strings
//but their frequencies dont match. So they are not anagram
//of one another
if(s1->freq!=temp->freq)
{
anagram = 0;
break;
}
}
//there is some character in one of the string

//that does not occur at all in another
if(flag==0)
{
anagram = 0;
break;
}
}
return anagram;
}
4.25 HOW TO FIND OUT THE SOUNDEX CODE FOR A GIVEN WORD
A soundex code is the phonetic code of the word. If the soundex codes of two words are same, that
means they are pronounced same way. This soundex algorithm was developed for indexing surnames in
a census.
Here is the soundex algorithm:
l Delete all occurrences of a,e,i,o,u,w,h and y from the word
l The first character of the soundex code will be the same as that of the words first character.
l If two consecutive characters are same, then the first one will be considered and the rest all will be
ignored.
l If the character encountered in the word is either b,f,p or v put 1 in the corresponding soundex
code of the word.
l If the character encountered in the word is either c,k,x,q,g,z,j, or s put 2 in the corresponding
soundex code of the word.
l If the character encountered in the word is either d or t put 3 in the corresponding soundex code of
the word.
l If the character encountered in the word is l put 4 in the corresponding soundex code of the word.
l If the character encountered in the word is either m or n put code 5 in the corresponding soundex
code of the word.
l If the character encountered in the word is r put 6 in the corresponding soundex code of the word.
th
l Find the substring of the Soundex code till the 4 character.
l If there are fewer than 4 characters in the soundex code, including the initial letter, then pad the
right of the soundex code with zeros.
//The following function returns the soundex code for a given word.
char* SoundexCode(char *word)
{
int i,j;
char temp[30];
temp[0]=word[0];
for(i=1,j=1;i<strlen(word);i++)
{
if(word[i]==word[i-1])
i++;//This is to avoid repetition of characters
if(word[i]!='a' || word[i]!='e' || word[i]!='h' ||
word[i]!='i'
|| word[i]!='o' || word[i]!='u' || word[i]!='w' ||
word[i]!='y')
{
if(word[i]=='b' || word[i]=='f' || word[i]== 'p' ||
word[i]== 'v')
{
temp[j]='1';
j++;
}
if(word[i]=='c' || word[i]=='g' || word[i]=='j'
|| word[i]=='k' || word[i]=='q' || word[i]=='s'
|| word[i]=='x' || word[i]=='z')
{
temp[j]='2';
j++;
}
if(word[i]=='d' || word[i]=='t')
{
temp[j]='3';
j++;
}
if(word[i]=='l')
{
temp[j]='4';
j++;
}
if(word[i]=='m' || word[i]=='n')
{
temp[j]='5';
j++;
}
if(word[i]=='r')
{
temp[j]='6';
j++;
}
}
}
temp[j]='\0';
strcpy(temp,substring(temp,0,3));
return temp;
}
How to Check whether two Words are Pronounced Same or not Using Their
Soundex Codes
int isSameSoundex(char *word,char *suspectedhomonym)
{
if(strcmp(word,suspectedhomonym)==0)
return 1;
else
return 0;
}
Here is a client code that tests two functions defined above.

int main()
{
//The soundex code will never be four characters.
//Anything beyond 4 characters are discarded.
char t[4],s[4];
strcpy(t,SoundexCode("build"));
puts(t);
strcpy(s,SoundexCode("billed"));
puts(s);
printf("%d",isSameSoundex(t,s));
getch();
return 0;
}
The output of the above client code is as follows.
b43
b43
1
So build and billed both have the same soundex code b430 (Blank means zero) and thats
because they are pronounced the same way. If you want to test the above algorithm for different strings,
visit Alan Coopers most extensive list of homonyms http://www.cooper.com/alan/homonym_list.html
The above algorithm works fine for almost all these strings listed here. The algorithm doesnt work for
those homonyms that start with different letters and pronounced the same way somehow because it
retains the first letter of the word.
REVIEW QUESTIONS
1. What can be said about x from this statement x = split(L1-333-353,-);

2. What will be the output for trimleft() when applied like trimleft(12345.23,2);
3. How can trimright() be applied to get the whole part of a number with a decimal digit?
4. How can trimleft() be applied to get the decimal part of a number?
5. How can pad() be used to print the output in a fixed width pattern?
PROGRAMMING PROBLEMS
1. Write a function to check whether a string matches the single wildcard pattern or not.
2. Write a program to demonstrate Naïve string search algorithm. This is also known as Brute Force
Algorithm.
3. Write a program to demonstrate Karp-Robin Algorithm.
4. Write a program to demonstrate Boyer Moore string search algorithm.
5. Write a program to demonstrate Boyer Moore Horspool string search algorithm.
6. What do you mean by string distance?
7. Write a program to calculate Hamming distance of two strings.
8. Write a program to calculate the levensthian distance of two strings.
9. What do you mean by similarity of two strings?
10. Write a function ExtractDigits() that extracts the digits from a string.
11. Write a function isValidIdentifier() that accepts a string as a variable name and returns 1, if the
name can be a valid C Identifier else it returns 0.
12. Write a function isCamelCase() that returns 1, if the string passed as argument is a valid C identi-
fier written in Camel Case.
13. Write a function isPascalCase() that returns 1, if the string passed as argument is a valid C identi-
fier written in Pascal Case.
14. Write a function isAComment() that return 1, if the string passed is a valid C++ single line com-
ment or C Style single line comment. Otherwise the function should return 0.
15. Write a function GetTense() that returns the tense of the sentence that is passed as the argument.
For example, the call like GetTense(I shall have been learning PHP next year by this time) will
return Future Perfect Continuous and a call like GetTense(I shall have finished my dinner by
then) will return Future Perfect.
16. Write a function Metaphone() to find the metaphone of a string.
5
Recursion
Time and Again!
INTRODUCTION
Recursion as the name suggests means re occurrence of the same method. Something that is occurring
over and over again is recurrence. In this chapter we will learn about different types of recursion and
then we will see how this technique is applied to solve different types of problems starting from solving
quadratic equations to creation of recursive fractals like Serpinski triangle, Monge Sponge, etc.
5.1 DIFFERENT TYPES OF RECURSION

Binary Recursion A recursive function which calls itself twice during the course of its execution.
Linear Recursion Recursion where only one call is made to the function from within the func-
tion (thus if we were to draw out the recursive calls, we would see a straight, or linear, path).
Exponential Recursion Recursion where more than one call is made to the function from
within itself. This leads to exponential growth in the number of recursive calls.
Circularity In terms a recursion, circularity refers to a recursive function being called with the
same arguments as a previous call, leading to an endless cycle of recursion.
Mutual Recursion A set of functions which call themselves recursively indirectly by calling
each other. For example, one might have a set of two functions, is_even() and is_odd(), one defined in
terms of the other.
Nested Recursion A recursive function where the argument passed to the function is the func-
tion itself. Ackermanns function is defined as a Nested Recursion. Q Number generation program is a
good example of Nested Recursion.
Recursive Definition A definition defined in terms of itself, either directly (explicitly using
itself) or indirectly (using a function which then calls itself either directly or indirectly).
Recursion (Time and Again!) 209
Tail Recursion A recursive procedure where the recursive call is the last action to be taken by the
function. Tail recursive functions are generally easy to transform into iterative functions.
5.2 PITFALLS OF RECURSION..

Recursion brings a mixed blessing. It can make simple work of otherwise complex and enormously
iterative tasks. It can also be a nightmare that brings the system to its knees by hogging huge amounts of
memory.
The down side of recursion starts to sink in when you realize that the functioning of the code is not
always immediately apparent on inspection, so another programmer who is unfamiliar with your code
might find it difficult to work with.
Debugging recursive routines can be maddeningly difficult. It can take great patience and skill to
have success fixing broken recursive code.
Recursive programs tend to have very tight code, so making modifications to an existing design can
prove difficult, even impossible. In fact, its often easier to rewrite a recursive function than it is to patch
in changes.
Lastly, perhaps most importantly, recursion can be a resource hog, using up precious memory re-
sources rather quickly. For systems that have scant memory resources (Such as DOS in real mode), the
programmer may elect to avoid using recursion unless there is no other choice.
Example 5.1 Write a program using recursion that finds the factorial of a number.
Solution Lets start with a simple example. The following program calculates the factorial of a number.
int fact(int n)
{
if(n==0 || n==1)
return 1;
else
return fact(n-1)*n;
}
Example 5.2 Write a program using recursion that finds the binomial coefficient.
Solution The value of Binomial Coefficient is given explicitly by nCk = n!/(nk)! k!
int nCk(int n,int k)
{
return fact(n)/(fact(n-k)*fact(k));
}
This function can be used in several other problems where binomial coefficient is a building block.
Notice how the recursive function fact( ) is being used in the function nCk( ).
5.3 FIBONACCI NUMBERS AND GOLDEN RATIO

Example 5.3 Write a program to find the nth Fibonacci Number.
Solution Fibonacci numbers are not a number series,
rather a rule that says add the two seeds provided and
you will get the next number and carry on these process
with two latest numbers. This series was first created by
the Italian mathematician Leonardo di Pisa, or Pisano,
known also under the name Fibonacci in 1202. It is a
deceptively simple series, but its ramifications and ap- Fig. 5.1
plications are nearly limitless.
In words: you start with 0 and 1, and then produce the next Fibonacci number (Fn) by adding the two
previous Fibonacci numbers:
Fig. 5.2
Fibonacci numbers have some very interesting properties. Here are some:
Lucas Theorem
Fm gcd Fn = F(m gcd n)

[ gcd = greatest common divisor ]
Cassinis Formula
Fn+1 ◊ Fn1 (Fn)2 = (1)n
A variant
Fn2 ◊ Fn+1 Fn1 ◊ Fn = (1)n1
Simsons Relation
Fn+1 ◊ Fn1 + (1)n1 = (Fn)2
Shifting Property
Fm+n = Fm ◊ Fn+1 + Fm1 ◊ Fn
#include <stdio.h>
int fibo(int num)

{
if(num==0)
return 0;
if(num==1||num==2)
return 1;
else
return fibo(num-1)+fibo(num-2);
}
Example 5.4 Write a program that calculates the numbers of a Fibonacci type series. Write a
function that will accept three values. The first two are the seeds (Like for Fibonacci numbers the
first two are 0 and 1) and the number of terms up to which the loop rotates.
Solution
#include <stdio.h>
int fibogen(int num,int first,int second)

{
if(num==1)
return first;
if(num==2)
return second;
else
return fibogen(num-1,first,second)+
fibogen(num-2,first,second);
}
If this function is called with initial values as 2, 1 respectively in place of first and second then we get
a series known as Lucas Series. First few numbers of Lucas Series are
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 .
The relation between Lucas Numbers and Fibonacci Numbers is
Ln = Fn 1 + Fn + 1
Example 5.5 Write a program to find the greatest common divisor of two numbers, using
Euclids algorithm.
Solution Almost 2500 years ago, Euclid discovered an algorithm to find the greatest common factor
or the test common divisor of two numbers.
int gcf(int x,int y)
{
if(y ==0)
return x;
else
return gcf(y,x%y);
}
Notice that this is a Tail Recursive Algorithm.
Example 5.6 Write a program to find the GCD using Joseph Steins Algorithm. This method is
also known as binary method.
Solution Euclids algorithm involves division and thus it is computationally expensive. A quite differ-
ent GCD algorithm specially suited for the binary number was first proposed by Joseph Stein is given by
If u and v are both even then
GCD(u,v) = 2* GCD(u/2,v/2)
If u is even and v is odd then
GCD(u,v) = GCD(u/2,v)
If u and v are both odd then u-v is even so,
GCD(u,v) = GCD(u-v,v)
Here is the code in C

int jsgcf(int u,int v)
{
if(u%2==0 && v%2==0)
return jsgcf(u/2,v/2);
if(u%2==0 && v%2!=0)
return jsgcf(u/2,v);
else
return jsgcf(abs(u-v),v);
5.4 RANDOM NUMBER GENERATION USING RECURSION

Example 5.7 Write a program to create a random number sequence using recursion.
Solution D.H.Lehmer came up with a scheme in 1949 to generate a pseudo random number sequence.
This is by far the most popular random number generator even today. The algorithm uses four magic
integers. They are
M, the modulus 0<m
a, the multiplier 0<=a<m
c, the increment 0<=c<m
Xo the starting value 0<=Xo<m
The desired sequence of random numbers (Xn) is obtained by
Xn+1 = (aXn + c) mod m, n>=0
This method is known as Linear Congruential Method. There are many varieties of this method.
Here is the C code.
void linrand(int a,int m,int c,int x,int n)
{
if(n!=0)
{
printf("%d\n",(a*x+c)%m);
n--;
x = (a*x+c)%m;
linrand(a,m,c,x,n);
}
else
return;
}
Notice that the function linrand() is also tail recursive.
Example 5.8 Write a program to generate random numbers using quadratic congruent method.
Solution To do a genuine improvement of linear congruent sequence we have to make it a quadratic in
nature. An interesting quadratic method was proposed by R.R.Coveyou. In this random number genera-
tor the value of m is a power of 2. Here we have used e as the power of 2.
Here is the code to generate Coveyou sequence
void coveyou(int a,int m,int c,int x,int n)
{
const int eto2 = (int)pow(2,M_E);
if(n!=0)
{
printf("%d\n",(x*x+x)%eto2);
n--;
x = (x*x+x)%eto2;
coveyou(a,m,c,x,n);
}
else
return;
}
5.5 HOW TO GENERATE PSEUDO RANDOM NUMBERS(PRNs) USING

VON NUMANNS MIDDLE SQUARING METHOD
Von Numann used one way to create random numbers. The technique is known as Middle Extraction
Technique. First a number is taken as the seed. Then that number is squared and the middle part of the
number is extracted and is used for the next seed. For example, if the starting number is 1234, then the
next seed will be middle digits of the square of 1234 which is 5227 because
12342 = 01522756
If the square of the initial seed or any seed in the process has odd number of digits then zeros are
padded to the left so that the next seed can be extracted.
This method is simple but has couple of drawbacks.
1. After some iterations the PRNs start to repeat themselves and is dependent on the initial seed. It
may be possible for different seeds we get different sequences where some numbers are frequently
occurring.
2. If all the digits in the middle suddenly become zero then the method fails to execute anymore.
Here is a C code that generates PRNs using this middle extract method:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
int extractmiddle(char *n)

{
//12321 -> 232
int i,j=0;
char s[4];
for(i=1;;i++,j++)
{
s[j]=n[i];
if(j==3)
break;
}
s[j]='\0';
return atoi(s);
}
int von(int n)
{
unsigned long s = n*n;

char x[20];
ultoa(s,x,10);
return extractmiddle(x);
}
Here is a client main() function to call the above program.
int main()
{
int i=0;
int seed = 123;
for(;i<40;i++)
{
printf("%d --> %d\n",i,seed);
seed = von(seed);
}
getch();
return 0;
}
Here is the output of the above program.
0 --> 123
1 --> 512
2 --> 621
3 --> 856
4 --> 327
5 --> 69
6 --> 761
7 --> 791
8 --> 256
9 --> 553
10 --> 58
11 --> 364
12 --> 324
13 --> 49
14 --> 401
15 --> 608
16 --> 696
17 --> 844
18 --> 123
19 --> 512
20 --> 621
21 --> 856
22 --> 327
23 --> 69
24 --> 761
25 --> 791
26 --> 256
27 --> 553
28 --> 58
29 --> 364
30 --> 324
31 --> 49
32 --> 401
33 --> 608
34 --> 696
35 --> 844
36 --> 123
37 --> 512
38 --> 621
39 --> 856
The seed is chosen such that the repetition characteristics of PRNs generated through this scheme can
be well proved. If you notice the above curves and highlighted entries, you will find that each of the
PRN is repeating itself at every 18th iterations. Or in other words 1st and 18th iteration values are same,
2nd and 20th iterated values are same. (Look at the above output).
Ideally the seed should not have any zero amongst its digits, because that will kill the sequence even
faster. Here is an example output where the seed was 108:
0 --> 108
1 --> 166
2 --> 755
3 --> 700
4 --> 900
5 --> 100 (Border Line PNR)
6 --> 0
7 --> 0
8 --> 0
9 --> 0
See anything after 5th iteration is zero.
Even using nonzero digits in the initial seed doesnt guarantee a good sequence. See the following
example output generated with seed 222.
0 --> 222
1 --> 928
2 --> 611
3 --> 733
4 --> 372
5 --> 383
6 --> 466
7 --> 171
8 --> 924
9 --> 537
10 --> 883
11 --> 796
12 --> 336
13 --> 128
14 --> 638
15 --> 70
16 --> 900
17 --> 100
18 --> 0
19 --> 0
5.6 HOW TO GENERATE THE ACKERMANNS FUNCTION

Ackermanns function is a function of two parameters whose value grows very fast.
Formal Definition:
l A(0, j) = j+1 for j ≥ 0
l A(i, 0) = A(i-1, 1) for i > 0
l A(i, j) = A(i-1, A(i, j-1)) for i, j > 0
This function grows very fast. In compiler design this function is used to check how a compiler can
handle recursion problems. Here is the code to generate Ackermanns Number.
int ack(int m,int n)
if(m==0 && n!=0)
return n+1;
if(n==0 && m!=0)
return ack(m-1,n);
if(m!=0 && n!=0)
return ack(m-1,ack(m,n-1));
}// This is also a tail recursive function.
Have you noticed the bold line above in the code? This type of calling is known as Nested Recursion
because one of the arguments in this call actually calls the ack() function again.
5.7 WHAT IS INVERSE ACKERMANNS FUNCTION?

a (m,n) = min{i ≥ 1: A(i, Îm/n˚) > log2 n} where A(i,j) is Ackermanns function.
The line above defines the Inverse Ackermanns function. Unlike Ackermanns function this function
grows very slowly. This function is also known as alpha function.
The half brackets in the above expression denote the ceiling of the value m/n. Have you noticed that
the inverse Ackermanns Function is defined in terms of Ackermanns function?
Can you use Ackermanns function defined above and generate the reverse Ackermanns Function?
5.8 HOW TO GENERATE TAK FUNCTION FOR GIVEN VARIABLES

TAK function was discovered by I. Takeuchi in 1978. This definition of the function is as follows.
TAK(x,y,z) = z , unless y > x
Else
TAK(x,y,z) = TAK(TAK(x-1,y,z), TAK(y-1,z,x), TAK(z-1,x,y))
int TAK(int x,int y,int z)
if (x<=y)
return z;
else
return TAK(TAK(x-1,y,z), TAK(y-1,z,x), TAK(z-1,x,y));

}
Both Ackermann function and TAK Functions are used as a benchmark for language with optimiza-
tion for recursion.
Example 5.9 Write a program to find the solution for Tower of Hanoi.
Solution In this function n is the number of disks. The other three variables denote the number of the
shafts that will be used as from, to and the temporary shaft number.
void hanoi(int n,int from,int to,int temp)
{
if(n==1)
printf("Move disc from %d to %d\n",from,to);
else
{
hanoi(n-1,from,temp,to);
printf("Move disc from %d to %d\n",from,to);
hanoi(n-1,temp,to,from);
}
}
Example 5.10 Write a program to achieve the following. When the user inputs any number,
show that in words. For example, if the user enters 99458 then the program will display Ninety-Nine
Thousand Four Hundred and Fifty-Eight.
Solution
#include <stdio.h>
int countdigits(int number)

{
int digits=0;
while(number!=0)
{
number/=10;
digits++;
}
return digits;
}
void Number2Words(number)
{
char *one2nine[9]=
{
"ONE",
"TWO",
"THREE",
"FOUR",
"FIVE",
"SIX",
"SEVEN",
"EIGHT",
"NINE"
};
char *tens[10]=
{
"TEN",
"TWENTY",
"THIRTY",
"FOURTY",
"FIFTY",
"SIXTY",
"SEVENTY",
"EIGHTY",
"NINETY"
};
char *teens[9]=
{
"ELEVEN",
"TWELVE",
"THIRTEEN",
"FOURTEEN",
"FIFTEEN",
"SIXTEEN",
"SEVENTEEN",
"EIGHTEEN",
"NINETEEN"
};
char *modifiers[]={"HUNDRED","THOUSAND"};
int copy=0;
int digits;
int dig[5];
int i=0;
int isTeens=0;
int isZero=0;
int noZeros=0;
int isAlreadySet=0;
copy = number;
digits = countdigits(number);
if(number==0 && isAlreadySet==0)
{
printf("ZERO");
isAlreadySet=1;
}
if(digits==1 && isAlreadySet==0)
{
printf("%s ",one2nine[number-1]);
isAlreadySet=1;
}
if(digits==2 && (number>10 && number <20) &&

isAlreadySet==0)
{
printf("%s",teens[number%10-1]);
isAlreadySet=1;
}
if(digits==2 && (number%10==0) && isAlreadySet==0)
{
/
printf("%s",teens[number%10-1]);
isAlreadySet=1;
}
if(digits==2 && (number%10==0) && isAlreadySet==0)
{
printf("%s",tens[number/10-1]);
isAlreadySet=1;
}
while(number!=0)
{
dig[i]=number%10;
if(dig[i]==0 && digits>2 && isAlreadySet==0)
{
noZeros++;
isZero=1;
}
number/=10;
i++;
}
if(digits==2 && isZero==0 && copy>=21
&& copy<=99 && isAlreadySet==0)
{
printf("%s %s",tens[dig[1]-1],
one2nine[dig[0]-1]);
isAlreadySet=1;
}
if(digits==3 && isAlreadySet==0)
{
if(dig[1]==1)
isTeens=1;
if(digits==3
&& isTeens==0
&& isZero==0
&& isAlreadySet==0)
{
printf("%s HUNDRED AND %s %s ",
one2nine[dig[2]-1],
tens[dig[1]-1],one2nine[dig[0]-1]);
isAlreadySet=1;
}
if(digits==3
&& isTeens==1
&& isZero==0
&& isAlreadySet==0)
{
printf("%s HUNDRED AND %s ",
one2nine[dig[2]-1], teens[dig[0]%10-1]);
isAlreadySet=1;
}
if(digits==3
&& noZeros==2
&& isAlreadySet==0)
{
if(dig[0]==0 && dig[1]==0)
{
printf("%s HUNDRED ",one2nine[dig[2]-1]);
isAlreadySet=1;
}
}
if(digits==3 && noZeros==1 && isAlreadySet==0)
{
if(dig[1]==0)//102
printf("%s HUNDRED AND %s ",
one2nine[dig[2]-1],
one2nine[dig[0]-1]);
if(dig[0]==0)//210
printf("%s HUNDRED AND %s
",one2nine[dig[2]-1],
tens[dig[1]-1]);
isAlreadySet=1;
}
}
}
int main()
{
int number=0;
do
{
int number=0;
printf("Enter a number :");
scanf("%d",&number);
if(number>100000)
{
Number2Words(number/100000);
printf("LAKH ");
number=number%100000;
}
if(number>1000)
{
Number2Words(number/1000);
printf("THOUSAND ");
number=number%1000;
}
if(number>0)
{
Number2Words(number);
}
}while(1);
}
Have you noticed that the program only has code to handle up to 3 digit number but it recursively
calls itself so that it can work properly to convert the bigger integers.
5.9 SOLVING NON-LINEAR EQUATIONS USING RECURSION

Example 5.11 Write a program to find the nth root of a number.
Solution There are n roots of the equation y = xn. Now the principal nth root of y = f (x) = A is a positive
real number x such that
xn = A.
There is an algorithm living till the time of Babylonians to get the principal root of a number.
It is given by the following recursive relation.
1È
xk + 1 = ( n - 1) xk + A ˘
n Í n -1 ˙
Î xk ˚
In order to find the square root of a number n = 2 and then the above formula reduces to
xk +1 = ÊÁ xk + A ˆ˜
1
2Ë xk ¯
Here is the C code:
#include <stdio.h>
#include <conio.h>
#include <math.h>
double root(int A,double Xo,int n,int iter)

{
double r;
r = ((n-1)*Xo+A/pow(Xo,n-1))/n;
iter--;
if(iter==0)
return r;
else
r = root(A,r,n,iter);
return r;
}
int main()
{
printf("Root is :%f",root(18,4,2,20));
return 0;
}
Example 5.12 Write a Program to find
the root of a function using NewtonRaphson
Method. This method is recursive in nature.
Solution When the derivation of f (x) is a sim-
ple expression and easily found, the real roots
of f (x) = 0 can be computed rapidly by a process
called Newton-Raphson method as shown in the
above figure:
#include <stdio.h>
#include <conio.h>
#include <math.h>
Fig. 5.3
double fun(double x)
{
//Define your Function here
return pow(x,3)-x-4;
}
double dfun(double x)
{
//Define the derivative of the function here
return 3*pow(x,2)-1;
}
double NewtonRaphson(double Xo,int iter)

{
Xo=Xo-fun(Xo)/dfun(Xo);
printf("%f\n",Xo);
iter--;
if(iter==0)
return Xo;
else
//Tail recursive call
Xo = NewtonRaphson(Xo,iter);
return Xo;
}
int main()
{
printf("Root is : %f",NewtonRaphson(2,10));
return 0;
}
Example 5.13 Write a program to find the root of a
function using bisection method.
Solution The method of bisection to find the roots of non-
linear equations is old and trivial and in a way inefficient. If
for two values of x, a and b the two values of y, y(a) and y(b)
have different signs, then, there exists a root of f (x) between a
and b. As the name suggests, method of bisection, bisects this
span and the point of bisection replaces either a or b depend-
ing on the sign of f (x) at point of bisection. For example if
f (a) is positive and f (b) is negative then there is a root be-
tween a and b. According to bisection method the close ap-
proximation of the root is x = (a+b)/2. Now if f (x) is positive
then a will be replaced by else b will be replaced by x. If f (x)
= 0, then x is a perfect root of f (x).
#include <stdio.h>
#include <conio.h>
#include <math.h> Fig. 5.4
double fun(double x)
{
//Define your Function here
return pow(x,3)-x-4;
}
double bisection(double a,double b, int iter)

{
double fa=fun(a);
double fb=fun(b);
double c = 0.5*(a+b);//Calculating the approximate root
if(fun(c)*fa<0)
b=c;
if(fun(c)*fb<0)
a=c;
iter--;
if(iter==0)
return c;
else
c = bisection(a,b,iter);
return c;
}
int main()
{
printf("Bisection :%f\n",bisection(1,2,10));
return 0;
}
Example 5.14 Write a program to find the root

using RegulaFalsi method.
Solution The oldest method for computing the real
roots of a numerical equation is the method of false
position, or regula falsi. In this method we find two
numbers xa and xb (as shown in the figure above)
between which the root lies. These numbers should
be as close as possible since the root lies between xa
and xb the graph for y = f (x) must cross the x axis
between x = xa and x = xb and y(a) and y(b) must
have opposite signs.
Now since the portion of a smooth curve is practi-
cally straight for a short distance, it is ok to assume
that changes in f(x) is same as changes in x for a
short interval. The method of false position is based
on these principles cause it assumes as per the above Fig. 5.5
figure, that the graph f(x) is a straight line between
(a, f(a)) and (b, f(b) and it crosses the x axis at x1. But we can clearly see that x1 is not the solution. As
per the above figure x1 is still left to the root and closer to it than xa. So now xa will be replaced by x1
and the same process will follow further in a recursive manner.
//This code finds
double RegulaFalsi(double x0,double x1,int iter)
{
double x2=x0-(fun(x0)*(x1-x0))/(fun(x1)-fun(x0));
iter--;
//We might find a perfect root or
//we might end up our desired number of iterations.
//Either way we come out of the loop.
if(iter==0 || fun(x2)==0)
return x2;
else
{
if(fun(x2)>0)
x1=x2;
if(fun(x2)<0)
x0=x2;
x2=RegulaFalsi(x0,x1,iter);//Tail Recursion
}
return x2;
}
Here is a graph that shows the performance summary for these tree methods.
From this graph we can predict that almost after 5 to 6 iterations all these methods start to give the
same result. But rate of convergence towards the correct result is highest for Newton Raphson method
provided the starting point is supplied properly. From the above figure we can conclude that perform-
ances of these methods are in the order:
Bisection Method < RegulaFalsi Method < NewtonRaphson Method
Example 5.15 Write a program to find the value of a function using Inverse Quadratic Interpo-
lation.
Fig. 5.6
Solution This method is not used individually but is used in hybrid numerical in Dekkers and Brents
method. The concept here, is first the inverse quadratic interpolation found at a point starting from three
initial guesses xn,xn-1 and xn-2 using Lagranges distribution. Let that point be f ^(1) (y) then the solu-
tion for y = f (x) = 0 is given by the following equation.
f n -1 f n fn - 2 fn
xn+1 = xn - 2 + xn -1
( f n - 2 - f n -1 ) ( f n - 2 - f n ) ( fn -1 - fn - 2 ) ( fn -1 - fn )
fn - 2 fn -1
+ x
( fn - fn - 2 ) ( fn - fn -1 ) n
Heres the function that calculates the value of Xn+1
double inversequad(double a,double b,double c)
{
double first=0,second=0,third=0,next=0;
double ab=
first=(fun(b)*fun(c)*a)/(((fun(a)-fun(b))*((fun(a)-fun(c)));
second=(fun(a)*fun(c)*b)/(((fun(b)-fun(a))*((fun(b)-fun(c)));
third=(fun(a)*fun(b)*c)/(((fun(c)-fun(a))*((fun(c)-fun(b));
next = first+second+third;
return next;
}
Note that fun() is the function that evaluates the function. You can
write your own functions.
Example 5.16 Write a program to find the root of a function using Secant Method.
Solution Newtons formula has a basic disad-
vantage. It involves differentiation of the func-
tion being sought. A secant or a chord of a curve
is defined as a straight line that intersects the
curve at least twice. This method calculates the
root of a nonlinear equation using the secant.
See in the above figure, the secant through x0
and x1 meets the x axis at x2. This will be the
new approximation of the root of the curve. This
process continues until we reach the desired level
of accuracy. The recursive relation in the figure
above gives the n+1th approximation of the root.
As you can probably understand from the fig-
ure above that if x0 and x1 are actually close to
the actual root, the rate of convergence will be
very high. Secant method is the base for Mull-
ers method which tries to approximate the curve
by a parabola instead of a straight line. Thus
Muller method is more accurate and its conver- Fig. 5.7
gence rate is comparable to that of Newton
Raphsons method which is really fascinating.
Here is the C function that solves the secant method.
double SecantMethod(double xn_1, double xn, int m)
{
double d;
d = (xn - xn_1)* fun(xn) / (fun(xn) - fun(xn_1)) ;
m--;
if(m==0)
return xn;
else
{
xn_1 = xn;
xn = xn - d;
d = SecantMethod (xn_1,xn,m);
}
return xn;
}
This method is highly dependent on the initial inputs.

Example 5.17 Write a program to find the root of an equation using Mullers Method.
Fig. 5.8
Solution Mullers method is a close cousin of secant method where at each iteration the curve is tried
to be mapped using a parabola that passes through the three points. xk, xk 1 and xk 2. Using Netwons
divided difference formula the curve can be approximated as the following equation below.
y = f (xk) + (x xk) f [xk, xk 1] + (x xk) (x xk 1)f [xk, xk 1, xk 2]
where f [xk, xk 1] and f [xk, xk 1, xk 2] denote divided differences. This can be rewritten as
y = f (xk) + w(x xk) f [xk, xk 1, xk 2](x xk)2
where
w = f [xk , xk 1] + f [xk, xk 2] f [xk 1, xk 2]
The next value in the iteration process is given by the root of the quadratic equation y = 0. This yields
the recurrence relation
2 f ( xk )
xk + 1 = xk -
w ± w 2 - 4 f ( xk ) f [ xk , xk -1 , xk - 2 ]
Note than xk + 1 should be one step close to the sought root than xk. So the denominator value for the
right half should be maximum. The sign + or is chosen depending on this logic.
Here is the C code. Here we are trying to solve the same equation as above.
double divdiff2(double x1,double x2)

{
return (fun(x1)-fun(x2))/(x1-x2);
}
double divdiff3(double x0,double x1,double x2)

{
return (divdiff2(x2,x1)-divdiff2(x1,x0))/(x2-x0);
}
double omega(double x0,double x1,double x2)

{
return
fun(divdiff2(x2,x0))+fun(divdiff2(x2,x1))+fun(divdiff2(x1,x0));
}
double max(double a,double b)

{
return a>b?a:b;
}
double Muller(double x0,double x1,double x2,int iter)

{
double z=pow(omega(x0,x1,x2),2)-
4*fun(x2)*fun(divdiff3(x2,x1,x0));
double x_3=x2-(2*fun(x2))/(max(omega(x0,x1,x2)
+sqrt(z),omega(x0,x1,x2)-sqrt(z)));
iter--;
if(iter==0)
return x_3;
else
{
x0=x1;
x1=x2;
x2=x_3;
x_3=Muller(x0,x1,x2,iter);
}
return x_3;
int main()
{
printf("Muller :%f\n",Muller(0,1,2,10));
return 0;
}
Graph comparing NewtonRaphson and Mullers method.
Fig. 5.9
The most fascinating fact about Mullers method is that it achieves almost the same level of conver-
gence as that of Newton-Raphson method without the need of differentiation. So from a computation
point of view, Mullers method is the best of all these methods discussed above. Muller method acquires
up to 2 decimal place accuracy fairly quickly (maximum by 5 iterations). In the above figure we see that
values from Newton-Raphson method are slightly more but the difference between values we get from
Newton-Raphson and Mullers method become steady after 4 iterations. If we notice carefully we will
see that Newton-Raphson method also took that time to stabilize. So we can conclude that Mullers
method accuracy and stability is comparable with Newton-Raphsons method and as an advantage it
doesnt require the knowledge of derivative of the function whose roots are being sought.
5.10 PATTERN GENERATION USING RECURSION

Example 5.18 Write a program to check whether a Number is happy or not.
Solution Suppose there is a number n. If n is squared then the digits of this square number is squared
separately and added. This sum of the square of the digits becomes the new number (new n). The same
process is repeated again until we reach any of these numbers 1,4,16,20,37,42,58,89 or 145. If the sum
is 1 then we conclude that the initial number n is happy else it is not. A number which is not happy is
known as unhappy. A happy number which is also a prime number is known as happy prime like 79.
Here is the C code that checks whether a number is Happy or not.
#include <stdio.h>
#include <conio.h>
#include <math.h>
int count=0;
int squareextractsum(int n)
{
int s=0;
int sum=0;
if(count==1)
s=n*n;
else
s = n;
while(s!=0)
{
sum+=(int)pow(double(s%10),2);
s/=10;
}
return sum;
}
int isHappy(int n)
{
if(n==1)
return 1;
if(n==4 || n==16 || n==20
||n==37 || n==42 || n==58
||n==89 || n==145)
return 0;
else
{
n=squareextractsum(n);
return isHappy(n);//Tail Recursive call
}
}
int main()
{
printf("%d \n,isHappy(230));
return 0;
}
This will output 1 as 230 is a happy number.
Try Yourself: Try to write a program that prints all happy numbers in a given range.
Example 5.19 Write a program to generate a section number pattern.
Say there are 2 big sections in a chapter and under each big section there are 5 small sections.
Write a program for printing the pattern
1.1
1.2
:
:
:
2.5
Solution Here is the C code which recursively generates the pattern:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int big=0,small=0;
int i=1,j=1;
int count=0;
FILE *fp;
void generateSectionNumberFile(char *file,int bg,int s)

{
/*big = 4, small = 5
1.1
1.2
1.3
1.4
1.5
2.1
2.2
2.3
2.4
2.5
and so on
*/
fprintf(fp,"%d.%d\n",i,j);
j++;
if(j<=small)
generateSectionNumberFile(file,i,j);
if(j>small && i<big)
{
j=1;
i++;
generateSectionNumberFile(file,i,j);
}
if(i>big && j>small)
fclose(fp);
int main()
{
char file[20];
printf("Number of Big sections :");
scanf("%d",&big);
printf("Number of sections under each Big sections :");
scanf("%d",&small);
printf("Enter the file name :");
fflush(stdin);
scanf("%s",file);
fp = fopen(file,"a");
generateSectionNumberFile(file,1,1);
return 0;
}
As you can see, this function can be extended to any level of hierarchy. For example this method can
be enhanced to generate a pattern like
1.1
1.1.1
1.1.2
1.2
1.2.1
1.2.2
The output of the above program when run with 2 and 4 as the inputs for Big and small will generate
a file with pattern
1.1
1.2
1.3
1.4
2.1
2.2
2.3
2.4
5.11 HOW TO WRITE A RECURSIVE FUNCTION TO GENERATE THE

NUMBERS OF THE PASCAL TRIANGLE
It will accept two numbers, one for row and the other for column and then it will display the pascal
number at that position of the Pascal Triangle
The Pascal Triangle also known as Yanghui Triangle in China is
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
The construction of Pascal Triangle is governed by the following rule:
Each subsequent row is obtained by adding the two entries diagonally as given above.
int compute_pascal(int row, int position)

{
//For matching the first column entries
if(position == 1)
{
return 1;
}
//for matching the last column entries
else if(position == row)
{
return 1;
}
//In between any row and any column
else
{
return compute_pascal(row-1, position) +
compute_pascal(row-1, position-1);
}
}
5.12 WHAT IS THE RELATIONSHIP BETWEEN PASCAL TRIANGLE

NUMBERS AND FIBONACCI NUMBERS?
The shallow diagonals of Pascals triangle sum to
Fibonacci numbers, i.e.
1=1
1=1
2=1+1
3=2+1
5=1+3+1
8=3+4+1
and, in general,
[ n/2 ]
Ên - kˆ Fig. 5.10
Â Á ˜ = Fn +1
k =0 Ë k ¯

NUMBERS OF THE BELL TRIANGLE. TO ACCEPT TWO NUMBERS, ONE
FOR ROW AND THE OTHER FOR COLUMN
The Bell Triangle is the triangle formed by Bell Numbers. This triangle looks like
This triangle is also known as Aitkens Array or Pierce Triangle
1
This triangle is obtained by beginning the first row with the number one,
1 2
and beginning subsequent rows with last number of the previous row. Rows
2 3 5
are filled out by adding the number in the preceding column to the number
5 7 10 15
above it
15 20 27 37 52
int compute_bell(int row,int position)
{
if(row==1)
return 1;
if(row == 2 && position ==1)

return 1;
else
{
if(position == 1)
return compute_bell(row-1,row-1);
else
return compute_bell(row,position-1)+
compute_bell(row-1,position-1);
}
}
5.14 APPLICATION OF BELL NUMBERS

Bell Numbers, or Bells Numbers, are the sequence {1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147....}. The
numbers count the ways that N distinguishable objects can be grouped into sets if no set can be empty.
For example the letters ABC can be grouped into sets so that:
(1) A, B, and C are in three separate sets;
(2) A and B are together and C is separate;
(3) A and C are together and B is separate;
(4) B and C are together and A is separate;
(5) or A, B, and C are all together in a single set.
Thus when N = 3, there are five partitions, so the third Bell number is 5.
The Bell numbers are also the coefficients of the Maclauren expansion
Ê x x2 5 x3 ˆ
e e = e Á1 + 1 + 2
x
+ + ...˜
Ë 1! 2! 3! ¯

NUMBERS OF BERNOULLI TRIANGLE
It will accept two numbers, one for row and the other for column and then it will display the pascal
number at that position of the Bernoulli Triangle. 1
Bernoulli triangle is a triangle containing the Bernoulli numbers. 1 2
The rule to get a Bernoulli number is to sum the number above it with 1 3 4
the number in the previous row and previous column. For example if 1 4 7 8
you see the number 7 on the 4th row 3rd column in the triangle, you 1 5 11 15 16
will notice that it is nothing but the sum of 4 and 3. 4 is right above it 1 6 16 26 31 32
and 3 is in the previous column and previous row.
Here is the code that generates the Bernoulli Triangle Pattern. First a function is written that gener-
ates the Bernoulli number at any given location and then it uses a loop to print those numbers in the
pattern.
int compute_bernoulli(int row,int position)
{
if(row==1)
return 1;
if(position==1)
return 1;
if(row==2 && position ==2)
return 2;
else
return
compute_bernoulli(row-1,position-1)
+compute_bernoulli(row-1,position);
}
void display_bernoulli(int rows)

{
for(i=1;i<=rows;i++)
{
for(j=1;j<=i;j++)
printf("%d ",compute_bernoulli(i,j));
printf("\n");
}
}

NUMBERS OF CATALANS TRIANGLE
It will accept two numbers; one for row and the other for column and then it will display the pascal
number at that position of the Catalans Triangle.
Catlans Triangle is a triangle where each element is the sum of one above and one to the left. The last
element of each row of Catalans Triangle is the summation of
the previous row elements. Here is the code that generates the 1
Catalans Triangle Pattern. 1 1
First 7 rows of Catalans Triangle are 1 2 2
1 3 5 5
void display_catalan(int rows)
1 4 9 14 14
{
for(i=1;i<=rows;i++) 1 5 14 28 42 42
{ 1 6 20 48 90 132 132
for(j=1;j<=i;j++)
printf("%d ",compute_catalan(i,j));
printf("\n");
}
}
int compute_catalan(int row,int position)

{
if(row==1)
return 1;
if(position==1)
return 1;
if(row==2 && position==2)
return 1;
else
{
if(row==position)//Last element
return catalan_sum(row-1);
else
return compute_catalan(row-
1,position)+compute_catalan(row,position-1);
}
}
int catalan_sum(int r)
{
int i=1;
int sum=0;
for(i=1;i<=r;i++)
sum+=compute_catalan(r,i);
return sum;
}
5.17 WHAT IS THE RECURSIVE RELATION THAT GENERATES

A CATALAN NUMBER?
Catalan Number follows a recursive relation among themselves as follows:
Cn + 1 = (4n + 2)Cn/ (n + 2) and C0 = 1 is the initial value.
where Cn + 1 is the n+1th Catalan Number.
Catalan number is also closely related with binomial coefficient as
1 Ê 2 nˆ ( 2 n )!
Cn = Á ˜ = for n ≥ 0
n + 1 Ë n ¯ ( n + 1)!n !
Here is the C Program that will generate nth Catalan Number:
int Catalan(int n)
{
return nCk(2*n,n)/(n+1);
}
5.18 SOLVING EULERS POLYGON DIVISION USING A CATALAN NUMBER

Catalan Number was generated from a problem known as Eulers Polygon division problem, that is of
finding in how many ways En a plane convex polygon of n sides can be divided into triangles by diagonals.
Euler first proposed it to Christian Goldbach in 1751, and the solution is the Catalan number En = Cn 2.
This above solution comes from a recurrence relation known as Segners recurrence relation:
En = E2.En 1 + E3.En 2 + + En 1.E2
5.19 DYCK PATH AND CATALAN NUMBER
Fig. 5.11
A Dyck Path is a staircase walk from (0, 0) to (n, n) that lies strictly below the reverse diagonal which
is inclined at 45 degree to the horizon. The number of Dyck paths of order n is given by nth Catalan
Number. See the above image to understand the concept better.
The first box in the above image corresponds to a staircase where there is only one stair. So the
number of Dyck path is 1 for n = 2 it is the second catalan number 2, and for 3 it is the third Catalans
Number = 5, and so on.
5.20 BALLOT PROBLEM AND CATALAN NUMBER

Suppose A and B are candidates for office and there are 2n voters, n voting for A and n for B. In how
many ways can the ballots be counted so that B is never ahead of A? The solution is a Catalan number Cn.
Please note using the function Catalan() defined above we can solve these type of problems. Catalan
numbers find their usage in several combinatorial problems.

NUMBERS OF LOSANITSCHS TRIANGLE
It will accept two numbers; one for row and the other for column and then it will display the pascal
number at that position of the Losanitschs Triangle.
Losanitschs triangle is a number triangle for which each term is the sum of the two numbers immediately
above it, except that, numbering the rows by n = 0, 1, 2, ... and the entries in each row by k = 0, 1, 2, ... n.
Here is a code that generates Losanitschs Triangle:
int compute_Losanitsch(int row,int position)
{
if(row==1)
return 1;
if(position==1)
return 1;
if(row==position)
return 1;
return 1;
if(row ==4 && (position==2 || position == 3))
return 2;
if(row==5 && (position==2 || position==4))
return 2;
return 4;
else
{
if(row%2==0 && (position==2 || position==row-1))
return compute_Losanitsch(row-
1,position)+compute_Losanitsch(row-1,position-1);
if(row%2!=0 && (position==2 || position==row-1))
return compute_Losanitsch(row-1,position);
else
return compute_Losanitsch(row-
1,position)+compute_Losanitsch(row-1,position-1);
}
void display_losanitsch(int rows)

{
{
for(j=1;j<=i;j++)
printf("%d ",compute_Losanitsch(i,j));
printf("\n");
}
}
Here is how the output looks:
1
1 1
1 1 1
1 2 2 1
1 2 4 2 1
1 3 6 6 3 1
1 3 9 12 9 1 1
1 4 12 21 21 10 2 1
1 4 16 33 42 31 12 1 1
1 5 20 49 75 73 43 13 2 1
1 5 25 69 124 148 116 56 15 1 1
1 6 30 94 193 272 264 172 71 16 2 1
Losanitschs triangle is given such a name after Serbian chemist Sima Lozanic who researched it in
his investigation into the symmetries exhibited by rows of paraffins.
NUMBERS OF THE LEIBNITZ HARMONIC TRIANGLE
It will accept two numbers, one for row and the other for column and then it will display the Pascal
number at that position of the Leibnitz Harmonic Triangle
This triangle below is Leibnitz Harmonic Triangle.
1
1
1 1
2 2
1 1 1
3 6 3
1 1 1 1
4 12 12 4
1 1 1 1 1
5 20 30 20 5
In this triangle each fraction is the sum of numbers below it and the initial and final entries in the nth
row are given by 1/n.
The terms are given by the recurrences
1
an ,1 =
n
an , k = an - 1, k - 1 - an , k - 1
Here is the code to generate numbers of this triangle.

double compute_Leibnitz(int row,int position)
{
if(position==1)
return (double)1/(double)row;
if(row==2 && (position==1 || position==2))
return 0.5;
else
{
return compute_Leibnitz(row-1,position-1)
-compute_Leibnitz(row,position-1);
}
}
This function calculates Leibnitz Harmonic Number at row and position.
Example 5.20 Write a program to find the Entringer numbers using recursion.
Solution
E(n,k) = E(n,k-1) + E(n-1,n-k)
This relation gives the number of
Where, E(0,0) = 1 and E(n,0) = 0
Here is the C code to generate the Entringer numbers.
int compute_Entringer(int n,int k)
{
if(n==0 && k==0)
return 1;
if(k==0)
return 0;
else
return compute_Entringer(n,k-1)
+compute_Entringer(n-1,n-k);
}
Example 5.21 Write a program to display the numbers of Hofstadter Conway $10,000 Sequence.
Solution Hofstadter Conway discovered a sequence which is recursive in nature and is given by the
following equation:
A(n) = A(A(n-1)) + A(n-A(n-2))
Where A(1) = A(2) = 1

So the first few values are 1,1,2,2,3,4,4,4,5,6 etc
Here is the C code that recursively generates the numbers of Hofstadter Conway Sequence..
int compute_HConway(int n)
{
if(n==1 || n==2)
return 1;
else
//Tail Recursive Call
return compute_HConway(compute_HConway(n-1))
+compute_HConway(n-compute_HConway(n-1));
}
void display_HConway(int n)
{
for(i=1;i<=n;i++)
printf("%d \n",compute_HConway(i));
}
Write functions to generate and display the numbers of the Mallows Sequences
int compute_Mallows(int n)
{
if(n==1 || n==2)
return 1;
else
return compute_Mallows(compute_Mallows(n-2))
+compute_Mallows(n-compute_Mallows(n-2));
}
void display_Mallows(int n)
{
for(i=1;i<=n;i++)
printf("%d \n",compute_Mallows(i));
}
Example 5.22 Write a program to generate Hofstadters Q Sequence. These numbers are also
known as Q- Numbers.
Solution This is a recursive sequence and generated by the recurrence equation
Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))
with Q(1) = Q(2) = 1 . The first few values are 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, .
Here is the C code to generate and display the Q-number
int computeQ(int n)
{
if(n==1 || n==2)
return 1;
else
{
return computeQ(n-computeQ(n-1))
+computeQ(n-computeQ(n-2));
}
}
void display_Q(int n)
{
f (i 1 i i )
for(i=1;i<=n;i++)
printf("%d \n",computeQ(i));
}
Example 5.23 Write a program to generate Serpinski Fractal Pattern.

Use the fact that Serpinski Triangle Pattern can be generated by using Pascals Triangle. In place
of each even number in Pascals triangle put 1 and in place of each odd number put 0 to generate the
Serpinski Triangle Pattern. Here is the code and output.
Solution
void display_serpinski(int rows)
{
int n=0;
int m=0;
{
for(m=0;m<(51/2)-i;m++)
printf(" ");
for(j=1;j<=i;j++)
{
n = compute_pascal(i,j);
if(n%2==0)
{
printf("%c ",'1');
}
else
{
printf("%c ",'0');
}
}
printf("\n");
}
}
Note that we have used compute_pascal( ) function described above.
This program generates a pattern like
Fig. 5.12
An image of the fractal Serpinski Triangle looks like
Fig. 5.13
Can you find similarity between the generated pattern and the fractal image?
5.23 L-SYSTEM, RECURSION AND MORE FRACTALS

L-System is a system developed by Aristid Lindenmayer in 1968 to describe the
growth of self similar plants like fern etc. L-System is a formal grammar and recur-
sive in nature. Thus, nowadays L-System is used to generate many recursive fractals
like Koch curve, Koch snowflakes, etc.
A self similar structure can be modeled using an L-System. Every system that is
being designed using an L-System will be needed to have the following.
Alphabet Which is the building block of the L-System representation of the
fractal
Rules Which makes the fractal to grow or diminish
Constants Something that remains constant throughout the process
Initial Conditions What are the initial conditions of the process?
Special Conditions (this is optional) Is there any special condition that can modify a rule?
Lindmeyer originally tried to model the growth of an algae using the L-System as follows:
Alphabets: A B
Constants: none
Initial Condition: A
Rules: (A Æ AB), (B Æ A)
Special Condition: None
which produces:
n = 0: A
n = 1: AB
n = 2: ABA
n = 3: ABAAB
n = 4: ABAABABA
A Æ AB means A will be replaced by AB and B Æ A means B will be replaced with A.
If you notice carefully you will find that this algee growth model discussed using L-System can be
easily modeled using recursion. All we have to do is to pass the iterated string to the system.
char* algee(char start[10])
{
char temp[10];
for(int i=0,j=0;i<strlen(start);i++)
{
if(start[i]=='A')
{
temp[j]='A';
j++;
temp[j] = 'B';
j++;
}
if(start[i]=='B')
{
temp[j] = 'A';
j++;
}
}
if(strcmpi(start,"ABAABABA")==0)
//The function is Tail-Recursive
return algee(start);
}
int main()
{
puts(algee("A"));
getch();
return 0;
}
Many recursive fractals or some of their variations can be generated using this L-System.
5.24 FRACTAL GENERATION USING RECURSION

Fractals have structural self-similarity on multiple scales. That means a piece of a fractal will often look
like the whole part. Fractals are used in computational geometry for rendering realistic looking scenery
for computer games. Next to this section, an algorithm is shown how to generate terrains using fractal
algorithm.
5.25 KOCH CURVE

Generation of Koch Curve
l A Straight line is transformed
n The line is split into three equal sizes
n Middle part is removed
n Middle is replaced with two lines of the same length
(1/3 of original line)
l For each straight line in the transformed line, repeat the
process.
l At some point the changes are no longer visible (if we
keep our viewing scale constant)
The length of the curve at depth d is (4/3)^d as shown in the
figure. Fig. 5.14
5.26 KOCH SNOWFLAKE
Koch Snowflake is a fractal that starts from an equilateral triangle. Then
each arm of the equilateral triangle is subdivided into three sections as
shown in the second image above. This process continues as long as
there is no perceptible change occurs between two consecutive struc-
tures, as long as we want. The more we break the lines, the structure will
have more details.
This is a recursive process to construct such a structure. As the struc-
ture looks like a snowflake, thats why it is called Koch Snowflake in
honor of the mathematician Helge Von Koch who first described this
pattern in 1904.
Inspired by the beauty of these fractal structures they are now used in
ornaments. Fractal ornaments are getting popularity these days. Fig. 5.15
5.27 RECURSION IN NATURAL SCENE GENERATION

Terrain Generation using Recursion
Fig. 5.16
One dimensional mid-point displacement is a great algorithm for drawing a ridgeline, as mountains
might appear on a distant horizon. Here is how it works.
Start with a straight line as shown in the figure above
Repeat for a sufficiently large number of times
{
Repeat over each line segment in the scene
{
Repeat Find the mid point of the line segment
Repeat Displace the midpoint in Y by a random amount
Repeat Reduce the range for random numbers,
}
}
How much we want to reduce the range for random numbers depends on how rough we want the
mountain to look like. The more we reduce it in each pass through the loop, the smoother the resulting
ridgeline will be.
Note two things about the above algorithm. First, it is recursive in nature; and secondly, it can create
fairly complex image with very low level details in
few simple steps.
The realization that a small, simple set of instruc-
tions can create a complex image has lead to research
in a new field known as fractal image compression.
The idea is to store the simple, recursive instructions
for creating the image rather than storing the image
itself. This works great for images which are truly
fractal in nature, since the instructions take up much
less space than the image itself. Chaos and Fractals, New Frontiers of Science 3 has a chapter and an
appendix devoted to this topic and is a great read for any fractal nut in general.
Without much effort, you can read the output of this function into a paint program and come up with
something like this:
REVISION OF CONCEPTS
Some Key Facts about Recursion

l Recursion means re-occurring of the same function or method.
l Any function can call any function.
l Some people think that main() cant be called from any other function. That is a misconception.
Any function can be called from any function. As because main() is a function so it can be called
from any function.
l When a function calls another function and the called function in turn calls the calling function,
which is called Mutual Recursion. For example, say there is a function called Menu() that is being
called from the main() function. And from Menu() again, main () is being called. Then we can say
that main() and Menu() are mutually recursive.
l When a function calls itself then that phenomenon is called as Self Recursion. And when we say
recursion we mean Self Recursion unless otherwise mentioned.
l Recursion can be used to replace loops. Thats why it is sometimes called as virtual loop.
l Whenever recursion is used the exit, criterion should be there.
l Recursion is a good technique to generate number sequences.
l Recursion is also used to generate some recursive Fractal Pattern like Sierpinski triangle, which
can be used to model chaotic objects like clouds, etc.
l An unusual use of recursion in a definition comes from Professor Seymour Papert, Professor of
Media Technology, at MIT (The Massachusetts Institute of Technology) and the inventor of the
graphical programming language LOGO. Here are Paperts instructions on how to make a circle.
First, take a step forward, then turn a little to the right, then make a circle. His description is a very
unusual one because it describes a circle as a process rather than as a static geometric shape. His
description is recursive because making a circle is defined in terms of making a circle. Recursion
is often used to define functions.
l Recursion is used to generate numbers sequences.
l Recursion is used to generate batrachions (A special class of curves defined only for integer se-
quence) Example includes Q number sequence, mallows sequence.
REVIEW QUESTIONS
1. What is nth Ackermanns number? Where n is the product of two consecutive primes starting with
1,2.
2. What is Hilbert Curve. What are the steps to create one recursively.
3. What is the L-System representation of Koch Snowflake?

4. What is the L-System representation of Serpinsky Triangle?
5. What is the L-System representation of Monge Sponge?
6. What is the L-System representation of Koch Curve?
PROGRAMMING PROBLEMS
1. Write a program to check whether a number is prime or not.

2. Write a program to generate prime numbers within a given range.
3. Write a program to generate al the combinations of a word.
4. Write a general algorithm to re-write a recursive algorithm in a non-recursive way.
5. Write a Program to generate Delannoy numbers given by the recurrence relation D (a, b) = D (a
1, b) + D (a, b 1) + D (a 1, b 1) with initial value D(0, 0) = 1.
6. Write a program to generate random numbers using primitive polynomials.
7. Write a program to generate random numbers using the famous blum-blum-shub recursive algo-
rithm.
8. Write a program to solve a non-linear equation using Brents method.
9. Rewrite the function to solve the root of a non-linear equation using Newton Raphson method.
Pass the tolerance level instead of the number of iteration.
10. Rewrite the function to solve the root of a non-linear equation using Bisection method. Pass the
tolerance level instead of the number of iteration.
11. Rewrite the function to solve the root of a non-linear equation using Regula-Falsi method. Pass the
12. Rewrite the function to solve the root of a non-linear equation using Secant method. Pass the
13. Rewrite the function to solve the root of a non-linear equation using Mullers method. Pass the
14. Write a program to print all the anagrams of a given string.
15. Write a program to find out whether there is a path between two locations in a maze or not.
16. Write a program to find whether there is a path between two nodes in a maze or not.
17. Write a program to find the root of a non-linear equation using Brents method.
18. Write a program to find the highest Fibonacci number within the range INT_MAX.
19. Compare a recursive relation with Ackermans function.
20. Compare a recursive relation with Tak function.
21. Demonstrate how LOGO is recursive, specifically speaking tail recursive in nature.
22. Show how Koch Curve can be generated using recursion.
23. Show how Serpinskys triangle can be generated using recursion.
6
Stack
One upon Another
INTRODUCTION
Some real-life scenarios can be modeled easily with a first in, last out list. In these types of situations a
stack will be the ideal data structure. A stack can be designed either by using arrays or by using linked
list. The basic operations possible on a stack are popularly known as push and pop. All these operations
are described in this chapter. Stack is a simple data structure but it has tremendous usages in the software
industry. Starting from a simple postfix calculator to a complicated XML reader, stacks find their way.
All these diverse applications of this simple data structure have been discussed at length in this chapter.
6.1 MODEL A STACK AS A STRUCT

Stack organizes elements one above another. So to model a stack in C we need two variables. We can use
arrays to hold the values of the stack. The other variable will hold the number of elements currently in
the stack. So, we can use a structure to represent stack. Given below is such a structure that represents an
integer stack that can hold 10 integers.
#define MAX 10
typedef struct MyStack

{
int data[MAX];
int count;
}MyStack;
Here data [MAX] is an integer array that can hold 10 integers in the stack. Count is the variable that
holds the current number of elements in the stack. Typedef has been used so that from now on MyStack
can be used as a built-in data type.
6.2 HOW TO INITIALIZE THE STACK MODELED ABOVE

Here we use arrays internally to store the Stack. Since array index starts from zero, to indicate an empty
stack, the count variable of the stack is set to 1. After push or pop operation, the count value is modified,
and the stack is reinitialized before any further operation. A global variable is kept and that is incremented
by unity while pushing, and decreased by unity while popping elements to and from the stack.
Here the global variable is named as sc. Here is the code to initialize the stack.
int SC = 1;
void initMyStack(MyStack *st)
{
st->count=sc;
}
By pushing we mean adding an element to the top of the stack. Until count reaches the maximum
number that the stack can hold, the elements added will be appended at the top of the stack. Pointer to
structure will be used to push an element. Here is the code for the method push(). Assume that we are
operating on the stack defined above. Here is the figure that explains the push and pop operation associ-
ated with a stack.
Fig. 6.1
int push(MyStack *st)

{
if(st->count==MAX-1)
Stack (One upon Another) 249
{
printf("MyStack is full!\n");
return 0;
}
else
{
printf("Enter the number :");
scanf("%d",&st->data[st->count]);
sc++;
printf("Successfully pushed");
return 1;
}
}
Since the counting of the elements for the stack starts from 1 (Empty Stack), the total number of
elements in the stack when the stack is full is given by MAX 1. This method returns 1 in case the
pushing of elements is successful, otherwise it returns 0. In case, the stack is not full, the element entered
is put at the last of the array in the location st->count.
Here the method itself asks for the element to be added at the top of the stack. But we can pass the
element to the method.
6.3 HOW TO POP THE MRA ELEMENT FROM THE ABOVE STACK
Deleting the last element from the stack is popularly known as popping of Most Recently Added(MRA)
element. If the stack is empty and we want to pop the MRA element, then the system will display the
message Stack is empty, Underflow Error. Otherwise it will pop the last element. from the Stack. Here
is the code to pop the last element from the stack defined above.
int pop(MyStack *st)
{
if(st->count<0)
printf("MyStack is Empty!\nUnderflow Error");
else
{
printf("Last number is popped\n");
sc--;
}
return st->data[st->count-1];
}
This method returns the popped element to the calling method.
6.4 HOW TO DISPLAY THE STACKTOP ELEMENT

The element at the stack top is of interest. To display the element at the top of the stack, we have to
display the last element of the array. Here is the code to display the stack top using the stack defined
above.
void display_MyStack_top(MyStack *st)
{
if(st->count<0)
printf("MyStack Empty\n");
else
printf("Top = %d\n",st->data[(st->count)-1]);
}
Now it checks whether the Stack is empty or not. If the Stack is not empty, then it displays the last
element of the array.
6.5 HOW TO SWAP THE TOP TWO ELEMENTS

Sometimes you may need to swap the top two elements of the stack. Here is the code to swap the last two
elements from our stack.
void swap(MyStack *st)
{
if(st->count<1)
printf("Swapping can't be done\n");
else
{
int temp=st->data[st->count-1];
st->data[st->count-1] = st->data[st->count-2];
st->data[st->count-2] = temp;
printf("Swapped Successfully!\n");
}
}
If there is only one element, then the count is 0, and swapping is not possible.
6.6 PUTTING IT ALL TOGETHER USING ARRAYS

Here is the source code putting all these methods together.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 10

{
int data[MAX];
int count;
}MyStack;
MyStack ms;
MyStack *s = &ms;
int sc=-1;
void initMyStack(MyStack *);

int push(MyStack *);
void display_MyStack_top(MyStack *);
void display_MyStack(MyStack *);
int pop(MyStack *);
void swap(MyStack *);
//Copy and paste each methods code here that are listed above
void initMyStack(MyStack *st)

{
st->count=sc;
}
//Now call these methods from within main as below

int main()
{
int choice;
do
{
initMyStack(s);
printf("\n1.Push\n");
printf("2.Pop\n");
printf("3.MyStack Top\n");
printf("4.Is Empty\n");
printf("5.Swap\n");
printf("6.Exit\n");
printf("Choice [1-6] :");
scanf("%d",&choice);
switch(choice)
{
case 1:push(s);break;
case 2:pop(s);break;
case 3:display_MyStack_top(s);break;
case 4:s->count<0?printf("Stack is empty"):printf("Stack is not
empty");break;
case 5:swap(s);break;
case 6:exit(0);
}
}while(1);
return 0;
6.7 MODEL A STACK USING A LINKED LIST

The main limitation of using the array to build stack is that we have to fix the size of the array in design
time. If we use linked list to design our stack, then the size of the stack can increase or decrease in the
design time. So in real time applications whenever we need to use stack, we will model that using a
linked list. Here we have modeled an integer stack using a linked list.
typedef struct link
{
int info;
link *next;
}link;
This structure above represents a particular node of the linked implementation of the stack.
6.8 PUSHING AN ELEMENT
Fig. 6.2
When we represent the stack using a linked list, pushing an element onto the top of the stack involves
two activities. First of all, we have to create enough space using malloc() method to insert one more
node in the list. Then the next address of the new node is assigned with the previous last node. This is
done because stack is a LIFO list, so MRA element will be at the top. Here is the code of the function
that pushes an element on to the stack top.
Stack * push(Stack *rec)
{
Stack *new_rec;
printf("Enter the value to push :");
new_rec = (Stack *)malloc(sizeof(Stack));
scanf("%d",&new_rec->info);
new_rec->next=rec;
rec = new_rec;//The old is now new
return rec;
}
This method returns the pointer to the last node. malloc() returns a void * . So it needs to be type
casted to the Stack * type.
6.9 HOW TO POP AN ELEMENT FROM THE STACK

Popping from a stack that is modeled using linked list requires the memory segment to be freed manu-
ally. The method free() is used for deleting the MRA element. Here is the code for popping the top
element from a stack designed with a linked list.
Stack * pop(Stack *rec)
{
Stack *temp;
Fig. 6.3
if(rec==NULL)
printf("Stack is Empty");
else
{
temp=rec->next;
free(rec);//Freeing up memory space
rec = temp;
}
return rec;
}
From this method also the pointer to the top element is returned.
6.10 HOW TO PEEP AT THE STACK TOP

Peeping at the top element of the stack requires the least amount of code. We just need to check whether
the stack is empty or not. If it is not empty, then the MRA element is shown. Here is the method.
void peep(Stack *rec)
{
if(rec==NULL)
printf("Stack is empty.");
else
printf("Stack Top Element = %d",rec->info);
6.11 HOW TO SWAP THE TOP TWO ELEMENTS

Swapping the top two elements involve swapping the values of the nodes. Here is the code for swapping
the top two elements of the stack.
Fig. 6.4
Stack * swap(Stack *rec)

{
int temp;
if(rec->next==NULL||rec==NULL)
printf("Swapping can't be done. Too few elements");
else
{
//Swapping the values of the top 2 nodes
temp = (rec->next)->info;
(rec->next)->info = rec->info;
rec->info = temp;
}
return rec;//returning the pointer to the top element
Example 6.1 Write a program using stack to evaluate a postfix expression. Assume that the
postfix expression can only take +,-,*,/ and all the parameters are from 0 to 9. The program will work
as follows. A postfix expression will be entered from the console by the user and then the program
will calculate the value of the expression and displays that on console. But the program doesnt check
whether the supplied postfix expression is valid or not. Model the stack
using linked list.
Algebraic expressions such as (A+B)/(CD) have an inherent tree-
like structure. For example, the figure below is a representation of the
expression in equation (A+B)/(CD). This kind of tree is called an ex-
pression tree.
If we travel the tree in-order we get infix notation. If we travel the tree
in post-order then we get the postfix expression. Verify that the expres-
sion tree values and the postfix expression match below. Fig. 6.5
Fig. 6.6
Solution
//This shows how to use a Stack to evaluate the given postfix
//expression.
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <ctype.h>
typedef struct Stack

{
int info;
struct Stack *next;
}Stack;
Stack *start;
Stack* push(Stack *,int);

Stack* pop(Stack *);
int peep(Stack *);
int peep(Stack *rec)

{
if(rec==NULL)
else
return rec->info;
}
Stack * push(Stack *rec,int c)

{
Stack *new_rec;
new_rec->info=c;
new_rec->next=rec;
rec = new_rec;
return rec;
}

{
Stack *temp;
if(rec==NULL)
else
{
temp=rec->next;
free(rec);
rec = temp;
}
return rec;
//This method checks whether the character read is an Operator or

//not. These are the basic 4 mathematical operators. You can write
int isop(char o)
{
if(o=='+'||o=='-'||o=='*'||o=='/')
return 1;
else
return 0;
}
int main()
{
char *postfix;
int first=0;
int second=0;
int i=0;
int result=0;
int temp=0;
clrscr();
printf("Please enter a Postfix Expression :");
scanf("%s",postfix);
for(i=0;i<strlen(postfix);i++)
{
if(!isop(postfix[i]))
{
printf(Enter value of %c,postfix[i]);
scanf(%d,&temp);
start = push(start,temp);
}
else
{
second = peep(start);
start = pop(start);
first = peep(start);
start = pop(start);
if(postfix[i]=='+')
{
result=0;
result+=(first+second);
start = push(start,result);
}
if(postfix[i]=='-')
{
result=0;
result+=(first-second);
}
if(postfix[i]=='*')
{
result=0;
result+=(first*second);
}
if(postfix[i]=='/')
{
result=0;
result+=(first/second);
}
//Add your own custom defined operators
//Like ^ for exponentiation and so on
}
}
printf("Result is = %d",peep(start));
getch();
return 0;
}
A sample run of the program.
Please enter a Postfix Expression :ab+cd-/
Enter value of a 80
Enter value of b 20
Enter value of c 5
Enter value of d 1
Result is = 25
6.12 HOW TO WRITE A PARENTHESIS MATCHER USING STACK

Compilers make use of stack structures. This example shows a simple illustration of the way a stack can
be used to check the syntax of a program. It uses the stack class you have created. In the example, a stack
is used to check that the braces {and} used to mark out code
l The source file is read character by character.
l Each time a { is read an object (any object, it doesnt matter what) is pushed onto the stack.
l Each time a } is read an object is popped from the stack.
l If the stack is empty when a } is read then there must be a missing { .
l If the stack is not empty at the end of the file then there must be a missing } .
Here is the Pseudo code for this. Assume that we are using the predefined MyStack structure.
printf("Enter the File Name :");
fflush(stdin);
gets(file);
printf("%s",file);
FILE *fp = fopen("C:\\tezt.c","r");
while(!feof(fp))
{
c = fgetc(fp);//reading character by character
printf("%c",c);
if(c=='{')
push(s);
if(c=='}')
{
if(isEmpty(s))
printf("Missing {\n");
pop(s);
}
}
}
if(!isEmpty(s))//We have reached the end of file
printf("} Missing\n");
6.13 SWITCHBOX ROUTING PROBLEM

Example 6.2 Write a program that accepts the pin numbers of a switchbox or IC and then states
whether the pin numbers are routable or not. A switchbox is routable by that we mean that there will
be no cross connection if we connect the given pin numbers. (See Fig. 6.7.)
Solution As you can see in the figure below, the internal connection inside a IC/PCB/switchbox is
similar. Suppose we have to connect pin number 1 to pin number 4 and like that, but no overlapping is
allowed because that will cause short-circuit.
A stack can be used to find out whether a switchbox is routable or not as shown in the following figure.
Fig. 6.7
Fig. 6.8
Here is the code in C to solve the problem using stack.
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <ctype.h>
#include <stdlib.h>

{
int info;
struct Stack *next;
}Stack;
Stack *start;
void display(Stack *);

Stack* push(Stack *);
int peep(Stack *);
Stack* swap(Stack *);
Stack * swap(Stack *rec)

{
int temp;
if(rec->next==NULL||rec==NULL)
printf("Swapping can't be done. Too few elements");
else
{
temp = (rec->next)->info;
(rec->next)->info = rec->info;
rec->info = temp;
}
return rec;
}
void display(Stack *rec)
{
if(rec==NULL)
else
{
while(rec!=NULL)
{
printf("Info = %d Address : %u Next Address :
%u\n",rec->info,rec,rec->next);
rec = rec->next;
}
}
}
int peep(Stack *rec)

{
if(rec==NULL)
else
return rec->info;
}
int isempty(Stack *rec)

{
if(rec==NULL)
return 1;
else
return 0;
}
Stack * push(Stack *rec,int info)

{
Stack *new_rec;
//scanf("%d",&new_rec->info);
new_rec->info = info;
new_rec->next=rec;
rec = new_rec;
return rec;
}
{
Stack *temp;
if(rec==NULL)
else
{
temp=rec->next;
free(rec);
rec = temp;
}
return rec;
int main()
{
int i;
int pins;
int net[]={1,2,3,4,5,6,7,4};
printf("How many pins :");
scanf("%d",&pins);
for(i=0;i<pins;i++)
{
if(isempty(start))
{
start = push(start,i);
}
else
{
if(net[i]==net[peep(start)])
{
printf("%d",peep(start));
start = pop(start);
}
else
{
start = push(start,i);
}
}
}
if(isempty(start))
printf("Switchbox is routable");
else
printf("Switchbox is not routable");
return 0;
}
Example 6.3 Write a program to find out whether a given string is a palindrome or not using a
stack. Ignore white space and other characters. Check your program with the following inputs .
Madam I am Adam and was it a cat I saw and Level. The program should be case insensitive.
Solution Here is the code that uses stacks to find whether the string entered is a palindrome or not.
The program skips all the white spaces. The stack is modeled using a linked list, because the string can
be of any length. Three stacks are used to perform this operation
Here is the illustration. People speak about so many palindromes. I have used one of my favorites.
Fig. 6.9
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <ctype.h>
#include <stdlib.h>

{
char info;
struct Stack *next;
}Stack;
Stack *start;
Stack *rstart;
Stack *cstart;
Stack* push(Stack *);

char peep(Stack *);
int isaplha(char c)
{
//Checking whether c is a alphabet or not.
//White space is also not allowed. ASCII of space is 32
//by writing c!=32 I mean that ASCII of c will not be 32.
if(((c>='a' && c<='z') || (c>='A' && c<='Z')) && (c!=32))
return 1;
else
return 0;
}
//This function will display the Stack top element.

char peep(Stack *rec)
{
if(rec==NULL)
else
return rec->info;
}
//This function will check whether the Stack is empty or not

int isempty(Stack *rec)
{
if(rec==NULL)
return 1;
else
return 0;
}
Stack * push(Stack *rec,char info)

{
Stack *new_rec;
new_rec->info = info;
new_rec->next=rec;
rec = new_rec;
return rec;
}

{
Stack *temp;
if(rec==NULL)
else
{
temp=rec->next;
free(rec);
rec = temp;
}
return rec;
int main()
{
char c;
int flag=0;
printf("Enter the characters :");
do
{
c = getche();
if(isalpha(c))
{
start = push(start,c);
cstart = push(cstart,c);
}
}while(c!=13);//Untill Enter is pressed
while(!isempty(start))
{
rstart = push(rstart,peep(start));
start = pop(start);
}
while(!isempty(rstart))
{
if(toupper(peep(rstart))==toupper(peep(cstart)))
flag = 1;
else
{
flag=0;
break;
}
rstart = pop(rstart);
cstart = pop(cstart);
}
if(flag==1)
printf("The string is a palindrome");
else
printf("The string is not a palindrome");
return 0;
}
Try this program with the following inputs:
Mom
LiriL
Brother
Was it a cat i saw!
Madam I m Adam
A Man, A Plan, A Canal, Panama!
6.14 SAGUARO STACK

The saguaro stack or cactus stack is a kind of stack where there can be more than one stack at the top of
another stack. In a saguaro stack, one stack cant be popped unless the stack at its top is empty. This
stack looks like the saguaro cactus. Thus it got its name.
A saguaro cactus
This type of stack can be very useful. For example say the URL entered in internet explorer contains
some illegal characters, using saguaro stack we can extract the invalid characters. Branches of this URL
stack are www , the company name and the domain(.com, .edu., .org etc..) See the figure below for more
explanations.
A saguaro stack can be thought as the combination of stacks. Here is the structure that is used to
represent the stack.
{
int data[MAX];
int count;
}MyStack;
typedef struct SaguaroStack

{
MyStack Stacks[MAX];
int count;
}SaguaroStack;
A Saguaro Stack cant be empty until all its branches are empty.
How to Push an Item in a Saguaro Stack
int push(SaguaroStack *st,int whichStack,int whattopush)
{
if(st->Stacks[whichStack].count==MAX)
{
printf("The specified Stack is full!\n");
return 0;
}
else
{
st->Stacks[whichStack].data[st->Stacks[whichStack].count] =
whattopush;
st->Stacks[whichStack].count++;
sc++;
printf("Successfully pushed");
return 1;
}
}
How to Pop an Item from a Saguaro Stack

int pop(SaguaroStack *st,int whichStack)
{
if(st->Stacks[whichStack].count<0)
printf("Specified Stack is Empty!\nUnderflow Error");
else
{
printf("Last number from Stack %d is
popped\n",whichStack);
sc--;
}
return st->Stacks[whichStack].data[st-
>Stacks[whichStack].count-1];
}
6.15 HOW TO WRITE THE ALGORITHM TO USE A SAGUARO STACK TO

CHECK A WRONGLY ENTERED URL
This algorithm will work for URLs like www.yahoo.com and will not work for URL like www.google.co.in
1. Accept the URL from the user.
2. Add the characters of the URL one by one in a stack called URL.
3. Pop this URL stack 4 times and add the values to another stack known as domain Stack.
4. Now pop the URL stack till it is empty and put the values in another stack called temp.
5. Now pop the Temp stack 4 times and put the values in another stack known as WWW.
6. If the last element of the WWW stack is anything other than . (Dot) then the URL is not valid.
7. If any of the element of WWW stack apart from the last element is not w, then the URL is not valid.
8. If the domain stacks last element is anything other than . Then the url is not valid.
9. Whatever is left in the temp stack is the company name. This can only contain alphabets numeric
digits (09) and _(Under score) or (Hiphen) and no other characters. In case it contains any
other characters then the URL is not valid.
Here is a figure to illustrates the above algorithm.
Fig. 6.10

Strings Code

Uploaded by

Copyright:

Available Formats

Strings Code

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Strings Code

Uploaded by

Copyright:

Available Formats

4

4.1 SOME KEY FACTS ABOUT STRINGS IN C

4.2 C-STYLE STRING

The Null Character

4.3 HOW TO INITIALIZE AT THE TIME OF DECLARATION

4.4 HOW TO INITIALIZE STRINGS USING USER-DEFINED VALUES

4.5 HOW TO INITIALIZE ONE STRING WITH ANOTHER STRING

4.6 HOW TO INITIALIZE A STRING USING CHARACTER VALUES

4.7 HOW TO INITIALIZE A STRING USING ASCII VALUES

The following program prints these patterns.

4.8 INTRODUCTION TO SOME BUILT-IN TURBO C STRING LIBRARY

char *familyname= Gottamann;

The output of this program will be John Gottamann

4.9 DESIGNING UTILITY TOOLS USING THESE TWO FUNCTIONS

Here is the output of the program.

4.10 A TOOL FOR CHANGING CASE OF FEW CHOSEN ABBREVIATIONS IN

4.11 HOW TO REVERSE A STRING

This will display

4.12 HOW TO SET CHARACTERS OF A STRING WITH ANOTHER

4.13 HOW TO FIND THE FIRST OCCURRENCE OF A CHARACTER

4.15 HOW TO CREATE THE DUPLICATE OF A STRING IN A

4.16 HOW TO TOKENIZE A GIVEN STRING

4.17 WHAT DO YOU MEAN BY PREFIX OF A STRING?

4.18 WHAT DO YOU MEAN BY SUFFIX OF A STRING?

4.19 WHAT DO YOU MEAN BY SUBSEQUENCE OF A STRING?

How to Check whether a Word Ends with a given Suffix or not.

String* push_back_String(String *last,char *s)

//This function splits the given string by the provided delimeter.

When called with the following client code

String *words = split(cs," ");

How to Display Text in a Word Wrap Mode

typedef character* string;

How to Display such a String Represented by a Linked List

How to Pad a String with a Specified Character and an Alignment Choice

char *pad(char *word,int totalwidth,char c,int allignment)

And here is the output of this code..

int isValidUPC(char *UPC)

return (EvenSum + 3 * OddSum)%10==0;

4.20 HOW TO CHECK WHETHER A STRING IS A VALID ISBN OR NOT

int isValidISBN(char *ISBN)

4.21 HOW TO CHECK VALIDITY OF A SOCIAL INSURANCE NUMBER (SIN) CODE

return (EvenSum + OddSum )%10==0;

4.22 HOW TO CHECK WHETHER A GIVEN CREDIT CARD NUMBER IS

int isValidCreditCard(char *type, char *ccn)

4.23 HOW TO CHANGE THE CASE OF A SENTENCE TO SENTENCE CASE

4.24 HOW TO TOGGLE THE CASE OF THE LETTERS OF A SENTENCE

strcpy(t,"Anger is never without a reason but it is seldom with a good

The following output is generated for this client call.

typedef struct CharacterWithFrequency

int isAnagram(char *phrase,char *diffcomb)

//there is some character in one of the string

Here is a client code that tests two functions defined above.

1. What can be said about x from this statement x = split(L1-333-353,-);

5.1 DIFFERENT TYPES OF RECURSION

5.2 PITFALLS OF RECURSION..

5.3 FIBONACCI NUMBERS AND GOLDEN RATIO

Fm gcd Fn = F(m gcd n)

int fibo(int num)

int fibogen(int num,int first,int second)

Here is the code in C

char *familyname= Gottamann;

String* push_back_String(String last,char s)

char pad(char word,int totalwidth,char c,int allignment)

int isValidCreditCard(char type, char ccn)

int isAnagram(char phrase,char diffcomb)

1. What can be said about x from this statement x = split(L1-333-353,-);

5.6 HOW TO GENERATE THE ACKERMANNS FUNCTION

5.7 WHAT IS INVERSE ACKERMANNS FUNCTION?

Graph comparing NewtonRaphson and Mullers method.

5.18 SOLVING EULERS POLYGON DIVISION USING A CATALAN NUMBER