CS 113: Introduction to Computer Science II with Introduction to C

Steve Homer---Spring 1999

Homework 4---due Thursday, April 1 before 10:00 PM

Reading: Standish, Chapter 6, pages 205-240; Chapter 7, pages 253-290

A Stack Implementation

typedef double stackElementT;

typedef struct stackNodeTag {
  /* You fill this in. */
} stackNodeT;

typedef struct {
  /* Top of stack, i.e., pointer to 1st node in list. */
  stackNodeT *top;
  /* Add any other fields you need. */
} stackT;

void StackInitialize(stackT *);
void StackDestroy(stackT *);
void StackPush(stackT *, stackElementT);
stackElementT StackPop(stackT *);
int StackIsEmpty(stackT *);

Your stack must be implemented using a linked list (an array implementation of a stack will be covered in lab). A linked list for this assignment looks conceptually something like:

 |
 v
---------     ---------     ---------
| 1.2 | -+--> | 0.3 | -+--> | 4.5 |0|
---------     ---------     ---------

Also, you need to keep track of the beginning of the linked list with a pointer.

The type stackNodeT should hold the data needed for a linked list node. The type stackT should hold the field(s) you need to keep track of a linked list.

Stack Operations

Roughly, each stack function will operate as follows:

• StackInitialize() sets up a new stack to be empty.
• StackDestroy() removes any remaining nodes (after the stack is no longer needed).
• StackPush() places an element at the top of the stack.
• StackPop() removes the element from the top of the stack. Note that popping from an empty stack is an error. In this case, you should print out a generic stack message and terminate the program (with library function exit() from stdlib.h).
• StackIsEmpty() reports a true or false value based on whether the stack is empty or not.

All functions take the stack (i.e., something of type stackT) by reference.

You must submit files h4stack.h, containing the interface, and h4stack.c, containing the implementation. Don't forget to wrap your header.

A simple test program, /cs/course/cs113/current/hw4/h4stacktest.c, is available for you to test your stack module. We suggest that you compile and run your stack module with this code to help ensure your code works properly.

A Calculator

In general terms, this stack calculator works as follows:

1. Gets a piece of data (operand or operator).
2. If the data is an operand, pushes it into the stack.
3. If the data is an operator, pops as many elements from the stack as needed, performs the operation, and pushes the result on the stack.

Your calculator should provide exactly the following operations: +, -, /, x (for multiplication), neg (i.e., the string "neg" represents negation), and ^ (raise to a power). All operations require 2 operands, except negation, which takes just one.

Operands are given to the calculator as either positive or negative numbers (i.e., you can put a + or - in front of them). Thus, examining the first character is not enough to distinguish a number from an operator. Also note that numbers may start with a decimal point (e.g., .50). As the interface shows above, you will use the type double for these numbers.

When the calculation is completed successfully, the program should print out the final result. The result should be printed with the format ``%g'' which displays floating point numbers in either regular (e.g., 3.14159) or scientific notation (7.8679e+10).

Error Handling

• Attempts to divide by zero.
• When there are not enough operands on the stack for an operation.

Note that the stack code prints something generic under error conditions (like popping from an empty stack); however, your program should prevent those errors from ever being reached. I.e., it should detect potential stack errors (by using the given stack functions) and print out its own, specific error messages.

Example Runs

Here are some example runs (make sure each operand and operator is separated by a space):

% h4calc 45.6 2.0 / 10.97 + neg 9 0.5 ^ x .69 -
The result is -102

% h4calc -6.7 4 x + 5.7 3 - 11.2 x neg
Error with "-6.7 4 x +": not enough operands for "+"

% h4calc 76.0 45.6 89 - 5.0 x 217 + / 42 neg -
Error with "76.0 45.6 89 - 5.0 x 217 + /": attempt to divide by zero.

Because you are probably more familiar with infix notation, where operators go in between operands, note that the first test run calculates:

(neg((45.6 / 2.0) + 10.97) x (9 ^ .5)) - .69

Note that commandline arguments are strings, so you must determine whether each argument is an operator or a number. If it is an operator, perform the operation. If it represents a real number operand, you can easily convert it to a double using a C library function like atof() (see the Manual Page for atof on how to use it and what header needs to be included for its prototype).

You may assume that input will be entered correctly, in the sense that only numbers and operators will be entered on the commandline.

A Make File

You should name your make file ``h4makefile'' and submit it as part of this homework. Since the utility make normally expects the makefile to be named ``Makefile'' or ``makefile'', you will have to run the make utility with:

make -f h4makefile

Test Runs

You script must show 6 test runs. Start out with the 3 listed in the Example Runs section and then add 3 more of your own that demonstrate each of the operations, plus all the error handling done by the main program.