CS 213:  Assignment #2

Due:  Before class on Tuesday, February 23, 1999

Submission Procedure:

1. Code is to be emailed to the grader bbh4@cornell.edu.
2. Please refer to the email you received from the grader for submission details.   Email the grader with questions.

Problem #1:  A Desk Calculator  (1.5 hours)

Chapter 6, Section 1 of the textbook outlines a desk calculator and provides code.   Implement it.  You must include all of the features mentioned in the section including variable number of command line arguments.  You do not need to make the modifications described in chapter 8.

Note:  It is your responsibility to make whatever changes to the syntax are necessary to get the code to run on YOUR machine.

Notes:  When I wrote this up (on Visual C++ 6.0) I ran into the following problems:

• There is no "put_back" method for class string.  Replace string_value.push_back(ch) with string_value += ch.
• Need to include <sstream> to use the istringstream constructor.
• You must EXPLICITLY initialize all of the variables you use.  Do not assume a default initialization to 0.
• Compile in "Release" mode to eliminate template related warning messages.
• The book does not make the final necessary change to get_token().  Each instance of "cin" in that function must be changed to "input" to accomodate command line arguements.  Note that cin is an istream and input is a pointer to an istream - you must account for this in your modification.

Problem #2:  Solving a Linear System  (2.5 hours)

Write a function "Solve" that takes as parameters a two dimensional array of doubles of arbitrary size (A) and an array of doubles (b).  Overwrite b with a solution (x) to the equation Ax=b.  Assume A is square.  Assume b != 0.  If no solution exists, throw an exception that when caught reports an error.  You must use Gaussian Elimination with Partial Pivoting as your Algorithm.  You may overwrite A.  You may pass the dimension of the matrix A (and array b) as a separate explicit parameter.

Note:  Partial pivoting requires you to swap the rows of A at each iteration so that the row with the maximal absolute entry in the pivot column is in the pivot position.

Note:  When testing for a singularity, you might test for something equal to zero.   In floating point math this is often unreliable due to round off error.   Therefore instead of testing for a==0 test for a<=EPS where EPS is machine epsilon for doubles = 2.2204460492503131e-016.

Hint:  READ appendix C, section 7.

Problem #3:  A Stack  (1 hour)

Create a struct called Node that has entries for an int and a pointer to another node.  Create a second struct called Stack that contains an int Size and a pointer to a node.  Write the following functions.  Size indicates the number of nodes in the Stack.

Write the following functions:

1. int Push(Stack& s, int a)  Creates a "new" node with int a.  Puts the new node at the top of the stack.  Returns the new size of the stack.
2. int Pop(Stack& s)  Pops the top node off the stack and dumps it (use delete to reclaim the storage).  Returns the new size of the stack.  If the stack was already empty then this does nothing.
3. int Offset(Stack& s, int a)  Returns the value of the int in the node that is a deep in the stack.  Here a=0 implies the top of the stack.  If a > Size throw an exception that reports an error.
4. void Print(Stack& s)  Print each int on the stack, formatted as follows:  3 :: 23 :: 12 :: end.  In this example 3 is on "top" of the stack.

You need to pass the stack by reference in functions 1 and 2, otherwise the change to the pointer will not persist after the function call.  You may pass the stack either by value or by reference in functions 3 and 4.

Hint:  You may find it useful to implement a constructor for each of the two structs you will create.  An example of a struct constructor can be found in the chapter on exception handling.  (It is just a method in the struct with no return type and the struct name as the name of the method.  It usually takes parameters that are used to initialize members of the struct).

If you are feeling brave, you may attempt to implement this as a class.  Since I have not covered classes in class yet, this is not necessary.  If you implement this as a class you should make the int in the Node and Stack private, you must also implement a constructor for Node and Stack as well as whatever methods you need to extract and update the private data.

Last Updated:  Tuesday, December 14, 2004 12:17:55 PM