CS 112 - Spring 2004: Homework 1

Due Thursday, September 23 at 11:59 P.M.

Reading: Chapters 1,2 and 4, pages 1-76 and 112-137.

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.3.

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.

Please keep in mind the policy on collaboration:
Homeworks should be completed without collaboration or assistance from other sources. You may discuss the general nature of the problems with others in the class, the instructor, or the TF, but if you do so, you must indicate this at the bottom of the problem. The actual solution to each problem must be an individual effort.
Copying part or all of somebody else's program or solution to a problem, or making your solution available to another student will be considered academic misconduct, and will be dealt with very harshly by the B.U. administration.

PROBLEM 1:

Transform these expressions into postfix notation.
  1. (A+B)*(C-D)
  2. ((A-B)/C)/(D/E)
  3. ((A-B)*(C+D))/(E/(G*F))
  4. (A$(B@(C$D)))~E (assume $,@ and ~ are arbitrary binary operations)
Transform these postfix notation expressions into infix (i.e.regular) notation.
  1. XY+Z*W/
  2. XYZW++-
  3. XYZ/+AB-*

Submit your answer in a file called prob1.txt

PROBLEM 2:

A stack has been implemented using the definitions given in class. You can copy the following files in order to make use of the stack implementation we have constructed for you. In stack.cpp is the source code for the stack definition and methods which are compiled in stack.o .

Note-- You MUST use the Save option in your browser to download these - cutting and pasting will not work!!!

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:

(i). 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.

(ii). Using the stack described above, write a C++ function bool CopyTop(Stack *S) which increases the size of the stack by one by duplicating the top item on the stack and and leaving the duplicate as the top item in the stack.
CopyTop returns true if the function worked correctly, and false otherwise.
You should also write a main function which will declare and initialize a stack, and then call and use your CopyTop function. Main should use our Stack class.
Note - CopyTop is NOT a method of the class, and so does NOT have access to the private part of the class.

Submit your Pop function by adding it to stack.cpp and submitting that file. You need not submit the main function you used to test out CopyTop. We will test it out ourself using our own program.

Submit your function CopyTop in a file called copytop.cpp

You need not submit a separate documentation file for this function. However, as with every program you write in this class, your CopyTop function should follow good coding standards and contain internal documentation (See the "Coding and Documentation Standards" link on the course web page).

PROBLEM 3:

Use a stack to implement a calculator which takes as input a postfix (reverse Polish) expression and which calculates the value of the expression.

The expression can contain the usual arithmetic operators and ?, ! and = as well. The meaning of ? is push the value, ! is a binary operator which means "take the minimum of the two operands," and the meaning of = is to print the top of the stack.

You may want to make use of the stack implementation given in problem 2.

So the input to your program will be something like ?3.2?4.0+=?2.1-= with output 7.2 5.1, or ?8.1?2.5+?2/?6.8!= with output 5.3.

Write your program in a file called calculator.cpp . Your code should follow the usual coding standards and have sufficient internal documentation.

You also need to also write a documentation file for calculator and name it calculator.txt This file needs to contain a clear concise explanation of how a user would make use of the calculator program. You should include examples as needed.

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 documentation and .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:

    To submit the assignment, cd to the directory containing the hw1 subdirectory and type:
    gsubmit cs112a1 -cp hw1
    This should submit the entire hw1 subdirectory.
    For further details on gsubmit, see the submit documentation.

    Good luck!