CS 112 B1 - Spring 2003: Homework 1

Due Friday, January 24 at 05:00 P.M.

Reading: Kruse and Ryba Chapters 1,2 and 4.

While you should skim through all of this material, you should read the following sections most carefully: 1.1, 1.3, 1.4, 1.6, 2.1, 2.2, 2.3, 2.5, 4.1, 4.2, 4.5, 4.6.

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.

Don't forget to sign up for our email list by typing csmail -a cs112b1 on csa. Instructions on forwarding your csa mail elsewhere are here.

PROBLEM 1:

1. A*(B+C)*D
2. A-(B-C)/(D/E)
3. ((A+B)*(C-D))/(E/G)*F
4. ((A*B)+C)/(A*(B/C))
5. ((A$B)@(C$D))~E (assume $,@ and ~ are arbitrary binary operations)

Submit your answer in a file called prob1.txt

PROBLEM 2:

• stack.h
• stack.cpp
• itemtype.h

The stack interface can be found in a file stack.h, and the ItemType has been defined in a file itemtype.h.

stack.cpp contains the following public methods:

• bool Init()
• bool IsEmpty()
• bool IsFull()
• bool Push(ItemType)

One method, Pop, has not been implemented for you and you need to implement this method in order for the stack code in the file stack.cpp to compile and run correctly. When you take a look at stack.cpp you will see where this short code segment goes. It is your assignment to add it to stack.cpp and test it to make sure it's correct.

You should test your stack by writing a main in a separate file. If you put in the main in teststack.cpp (the filename doesn't matter, you won't be submitting it), you can compile everything with
g++ -Wall -o teststack teststack.cpp stack.cpp
and run it with ./teststack (hopefully you all know this by now, this is just a refresher).

NOTE To enable you to do the rest of the assignment even if you cannot complete this part, we are providing the file stack.o that contains the compiled correct implementation of the stack (copy it using the above-mentioned method, or use "save as" in your browser). You may use it instead of your own stack.cpp if you are unsure of your implementation (in that case, simply replace stack.cpp with stack.o in the g++ commands for the other parts of this assignment).

PROBLEM 3:

Write a C++ function bool SecondFromTop(Stack *s, ItemType &item) that uses the above implementation of the stack and sets item to be the item which is second from the top of the stack pointed to by s, but always leaves the stack itself exactly as it was before the function was called. SecondFromTop returns true if the function worked correctly, and false otherwise. Note that SecondFromTop is NOT a method of the class stack, and so does NOT have access to the private part of the class.

For testing purposes, you should also write a main function that will declare and initialize a stack, and then call and use your SecondFromTop function.

Put your secondfromtop into a file called secondfromtop.cpp. Put your main into testsecondfromtop.cpp (or any other filename that's convenient--you will not be submitting it). To compile everything, type
g++ -W all -o teststack stack.cpp secondfromtop.cpp testsecondfromtop.cpp
and run it using ./teststack.

PROBLEM 4:

The expression is a string with the following syntax: it may contain the character ? followed by a floating point value, or the characters +, *, -, /, =, p, or q. If you see a ?, push the following floating point value onto the stack. If you see a +, *, -, or /, perform the appropriate operation, modifying the stack accordingly (output nothing to the screen). If you see a =, print the value on top of the stack (but keep the stack the same). If you see p, pop a value from the stack (output nothing to the screen). If you see q, quit the program. Spaces don't matter and will (fortunately for you) be ignored by C++, so you need not worry about them.

So the input to your program will be something like ?5?2.5/=?4?3.2?4.0++=p?1.5-=q and the output would be something like
2
11.2
0.5

In case of stack overflow, underflow, an illegal input, or any other illegal operation, you should print an error message and continue reading the string.

Write your program in a file called calculator.cpp. Your code should have its own main that will drive the whole thing, so that the grader can compile it using
g++ -W all -o calc calculator.cpp stack.cpp and run it.

To submit hw1:

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++.
3. Check that your .txt files are readable by printing them out to the screen using the more command.
4. Create a subdirectory called hw1, using the mkdir command.
5. Copy all files to be submitted and no others into this subdirectory. The following files (and ONLY these files) should be in subdirectory hw1:
   • prob1.txt
   • stack.cpp
   • secondfromtop.cpp
   • calculator.cpp
6. To submit the assignment, cd to the directory containing the hw1 subdirectory and type:
   gsubmit cs112b1 -cp hw1
   This should submit the entire hw1 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 "Hw1" will probably not be seen by the grader.