CS 112 B1 - Spring 2003: Homework 3

Due Thursday, February 27 at 11:59 P.M.

Reading: Kruse and Ryba Chapters 7 and 10.1, 10.2, 10.3. Get started on Chapter 8.

Please keep in mind the policy on collaboration, as described on the syllabus.

Your code will be graded for style as well as correctness and should conform to the following style guidelines.

PROBLEM 1:

The following program should output an integer square root of its input. That is, given an unsigned integer x, it should find the largest integer y such that y*y<=x. Implement the missing code using binary search.

• binsqrt.cpp

PROBLEM 2:

The following program should take as input a bunch of strings and print them upon request in ascending and descending order. The user can input

• ? followed by a string, at which point the program takes in the string, or
• a, at which point the strings should be printed in ascending order, or
• d, at which point the strings should be printed in descending order, or
• q, at which point the program should quit.

You need to implement this using a binary search tree to store the strings in order. Some code is already provided for you; fill in the missing code. It may be handy to know that the > and < operators work on strings.

• strings.cpp

Note: If you call your executable "strings", then be sure to type
./strings
in order to run it, because there is another Unix command "strings" that may run instead if you just type "strings."

PROBLEM 3:

Modify the RPN calculator from HW 1 to do the following. Instead of performing the operation requested, the calculator should create and push on the stack the expression tree representing the operation requested. Upon receiving the command =, the calculator should print out the infix version of the expression, then evaluate it and print out the result. Here is a sample input and output:
? 5 ? 2.5 / = ? 4 ? 3.2 ? 4.0 + + = p ? 1.5 - = q
(5 / 2.5) = 2
(4 + (3.2 + 4)) = 11.2
((5 / 2.5) - 1.5) = 0.5
Please be sure to follow the output format exactly (including parentheses, spaces around the operators and the equal sign, etc.) or we may take off points.

You may use any stack implementation you want (see solutions to hw1 or hw2). Whiechever you use, however, please to call the files stack2.cpp and stack2.h, respectively, so that your include file is correct.

Your itemtype.h will look as follows:
class TreeNode;
typedef TreeNode * ItemType;


Much of the implementation is provided, you need only fill in the missing code:

• postfixinfix.cpp

PROBLEM 4:

We want you to use a make file for this assignment, and from now on. If you download this sample Makefile and run command make it will make targets binsqrt and strings, but will not work for postfixinfix. Add target postfixinfix, which should depend on stack2.o and postfixinfix.o, and targets stack2.o and postfixinfix.o (think about dependencies there). Once you are done with this part, make should compile your entire assignment. You may find the Labs web page helpful.

To submit hw3:

1. You must be logged onto csa, and all files must be on the csa computer.
2. Test that your program works by compiling it with g++ -Wall.
3. Create a subdirectory called hw3, using the mkdir command.
4. Copy all files to be submitted and no others into this subdirectory. The following files (and ONLY these files) should be in subdirectory hw3:
   • binsqrt.cpp
   • strings.cpp
   • postfixinfix.cpp
   • Makefile
5. To submit the assignment, cd to the directory containing the hw2 subdirectory and type:
   gsubmit cs112b1 -cp hw3
   This should submit the entire hw3 subdirectory.

Important: Please follow all instructions about file names and how to submit assignment exactly, or there is a very real chance that your assignment will not be accepted! For example, a directory named "Hw3" will probably not be seen by the grader.