|
|
CS 2213/2211
Advanced Programming
Spring 2005
Recitation 3
Palindromes
Week 3: Feb 1-3
Due (on time):
2005-02-08 23:59:59
Due (late):
2005-02-13 23:59:59
|
Recitation 3 should be submitted
following directions at: submissions with deadlines
- 2005-02-08 23:59:59 (that's Tuesday, 8 February 2005, 11:59:59 pm)
for full credit.
- 2005-02-13 23:59:59 (that's Sunday, 13 February 2005, 11:59:59 pm)
for 75% credit.
|
Introduction:
This recitation works on five areas:
- Writing a C program using separate files for objects.
- Studying array-based stacks and queues.
- Translating a program (code for a queue) from Java to C.
- Working with a char-by-char copy program.
- Application of the above to recognize input palindromes.
1. Writing a C program using separate
files for objects: The program for this recitation
should use 5 separate files:
- stack.h and
stack.c:
header and implementation files for a stack.
- queue.h and
queue.c:
header and implementation files for a queue.
- palin.c:
file with a main
function that uses the others to recognize input palindromes.
2. Studying array-based stacks and queues:
Here is a description of the stack and the queue to use:
For the stack of this recitation, you should use an extension of the
"stripped-down" stack in
Array-based stack.
You should add code to check for underflow and overflow of this stack,
calling the full()
and empty() functions.
The code here already gives you the header and implementation
files, with some slight additions needed to the implementation file.
For the queue, you should start with a queue written
in Java: Array-based queue.
This is a standard "circular" queue, where the "next" array index
after the largest one is simulated to be the Oth index.
3. Translating a program (code for a queue)
from Java to C:
Notice that for this recitation, you are required to translate
the given Java queue into C, and not write queue code from scratch
or retrieve queue code from somewhere else. You are to work with
this queue. In particular, your C code should have variables
fp,
rp, and
qs, each initialized to 0.
4. Working with a char-by-char copy program:
As part of the skeleton for the main work of the recitation, you
need to use C code that reads a text file line-by-line.
You can find this at the end of the web page about copying:
Copy programs.
5. Application of the above to recognize
input palindromes: This recitation's goal is to
recognize input palindromes, that is, sequences of characters
that read the same forwards or backwards. I am interested here
in "standard" palindromes such as:
- Madam I'm Adam. (Adam to eve)
- Name no one man. (Eve's reply)
- Ah, Satan sees Natasha.
- Damn! I Agassi miss again. Mad!
- I prefer Pi.
- Tulsa night life: filth, gin, a slut.
- Swap God for a Janitor. Rot in a jar of dog paws.
Notice that punctuation is ignored, as is the distinction between
upper- and lower-case.
There are many ways to check for a palindrome, but you are
required to use the method given here.
(This may seem artificial, but we are also practicing the use
of a stack and a queue.)
- Read each char of an input line.
- If the char is a letter, change it to lower-case
(if it's not already lower-case), push it onto the stack
and insert it into the queue.
- When done with the reading, pushing and inserting,
repeatedly pop an char off the stack and remove a char
from the queue. Until the stack and queue are empty,
check if these chars are equal. If any pair are not
equal, it is not a palindrome; if all pairs are equal,
it is a palindrome.
What you should submit:
Refer to the submissions directions and to
deadlines at the top of this page. The text file that you submit
should first have Your Name, the Course Number,
and the Recitation Number. The rest of the file
should have the following in it, in the order below, and clearly labeled,
including at the beginning the appropriate item letters:
a, b, c, etc.
|
Contents of email submission
for Recitation 1:
Last Name, First Name; Course Number; Recitation Number.
a. Source for the files:
stack.h,
stack.c,
queue.h,
queue.c, and
palin.c.
b. Result of a run with the file:
palindata.txt.
Be sure that your software says which are palindromes
and which are not. The output should look something like
the following: outdata.txt.
Notice that your program should stick extra quotes around each palindrome
|
Key ideas:
The best way to represent objects in C is to use separate
files, with header files for consistent cross-communication.
Revision date: 2005-01-25.
(Please use ISO
8601, the International Standard.)
Copyright © 2011, Neal R. Wagner. Permission is granted
to access, download, share, and distribute, as long as this notice remains.
