C++ Programming Project 5

TITLE

IDENTIFYING PALINDROMES WITH TWO STACKS

INTRODUCTION

We've seen palindromes before: Strings in which the letters read identically in both directions, disregarding non-letter characters and capitalization. The most common example is probably

 A man, a plan, a canal, Panama. 

Another:

 Rats live on no evil star. 

DESCRIPTION

Design, implement, document, and test a program that reads a string of characters, uses two stacks to determine if the letters in the string form a palindrome, and reports its result.

INPUT

The program's input is a string of characters, entered from the terminal.

OUTPUT

The program's output, written to the terminal, reports whether or not the input string is a palindrome.

ERRORS

The program can assume that its input is a string of characters; it need not detect any errors.

EXAMPLE

Several runs of the program might look like this:

 Enter a string -> Pets nip instep. The string IS a palindrome. Enter a string -> Able was I ere I saw Elba. The string IS a palindrome. Enter a string -> This is another candidate string. The string IS NOT a palindrome. 

OTHER REQUIREMENTS

Implement a stack abstract data type in a class in which a typedef statement specifies the type of the stack's items. Use a sequential (array-based) stack implementation.

The client program will declare TWO stacks.

HINTS

Here's a strategy for the client program.

Begin by reading the input line, one character at a time. Push() all the letters into one of the stacks, using only upper case or lower case.

Note the size() of the stack, and pop() half that number of letters off the first stack and push() them onto the second stack. If the number of letters is odd, pop() the first stack one more time and discard that letter.

Now pop() both stacks and compare the pairs of letters that are returned. The input string is a palindrome only if the letters in every popped pair are the same.