# CS140 -- Lab 7

### Lab Objective

This lab is designed to give you more experience with stacks and dllists.

### Lab Materials

• The makefile for the test files is in /home/cs140/www-home/spring-2005/labs/lab7/makefile.
• Executables for the test files are in the directory /home/cs140/www-home/spring-2005/labs/lab7. As usual, if you have questions about how these programs should work, try these.
• There are three example score files for histolist, in NL-hits.txt, KS-Bridge.txt, and PF-Bridge.txt.
• You will need to use Dr. Plank's stack and dllist libraries. You will also need to use his fields library for the histolist program.

### mydc

Write mydc which is an arithmetic calculator that operates on integers. The overall structure of mydc is a stacking (reverse Polish) calculator.

Input comes from standard input. The following input constructs are recognized:

```     number  Push a number onto the  stack.

+  - /  * %
The top two values on the stack  are:  added  (+),
subtracted   (-),  multiplied  (*),  divided  (/),
or remaindered (%).   The  two entries are popped off
the stack and the result is pushed in their place.
In the case of subtraction, division, and remaindering, the
topmose value is the rightmost value in the expression. For
example, if 3 and 7 are the top two numbers on the stack with
3 being the topmost element, then the subtract command will
produce 4 (7-3), the divide command will produce 2 (7/3), and
the remainder command will produce 1 (7%3).

d       Duplicate the top value on the stack.

p       Print the top value on the stack.  The  top  value
remains unchanged.

f       Print all values on the stack.

q       Exit the program.

c       Clear the stack (i.e. pop off all values)
```
Here are some example input sequences:
```     INPUT: 5 6 + p                 OUTPUT: 11

INPUT: 3 4 5 - * p 2 - p       OUTPUT: -3
-5

INPUT: c p f                   OUTPUT: main stack: empty
main stack: empty

INPUT: +                       OUTPUT: not enough operands

INPUT: + 1 2 + p               OUTPUT: not enough operands
3
INPUT: c 1 2 3 4 f             OUTPUT: main stack: 1 2 3 4

INPUT: c 6 d f * p             OUTPUT: main stack: 6 6
36
```
You should use Dr. Plank's stack library to implement your stack. It is fine to use scanf to read each input item.

### histolist

Write a program called histolist that divides scores into ranges and then prints each range and the scores in that range. histolist takes a single command line argument, n, which defines the size of each range. For example if n is 4, then the ranges will be 0-4, 4-8, 8-12, etc. In general the ith range will go from (i-1)*n to i*n. In the above example range 1 goes from 0 to 4.

The first range printed will be the range containing the minimum score and the last range printed will be the range containing the maximum score. For example, if the minimum score is 18 and the maximum score is 35, then the first range printed will be 16-20 and the last range printed will be 32-36.

histolist reads input from stdin. Each line starts with a name (which can be multiple words) and a floating point score. Lines may be blank but a line without a score at the end, or without a name should be flagged as an error. Negative scores should also be flagged as errors.

When your program prints the ranges, it should first print the range and then a list of all names with scores in that range.

Here are some examples:

```UNIX> cat PF-Bridge.txt
Kevin Wilson - Brad Vander Zanden            44.21
Randall Beatty - Ted McLellan                47.45
Linda Smith - Ron Smith                      53.94
Ann Rickard - Michael Oechsler               46.30
Carol Mims - Gloria Kilpatrick               54.86
David Shepler - Mark Harris                  42.59
Janet King - Herb Stappenbeck                61.11
Dorothy Jones - Virginia Wooten              49.54
Susan Plank - James Plank                    58.10
Brian Hingerty - Vincent Carcello            41.90

UNIX> histolist 5 < PF-Bridge.txt
Range: 40 - 45
Kevin Wilson - Brad Vander Zanden
David Shepler - Mark Harris
Brian Hingerty - Vincent Carcello
Range: 45 - 50
Randall Beatty - Ted McLellan
Ann Rickard - Michael Oechsler
Dorothy Jones - Virginia Wooten
Range: 50 - 55
Linda Smith - Ron Smith
Carol Mims - Gloria Kilpatrick
Range: 55 - 60
Susan Plank - James Plank
Range: 60 - 65
Janet King - Herb Stappenbeck

UNIX> histolist 3 < PF-Bridge.txt
Range: 39 - 42
Brian Hingerty - Vincent Carcello
Range: 42 - 45
Kevin Wilson - Brad Vander Zanden
David Shepler - Mark Harris
Range: 45 - 48
Randall Beatty - Ted McLellan
Ann Rickard - Michael Oechsler
Range: 48 - 51
Dorothy Jones - Virginia Wooten
Range: 51 - 54
Linda Smith - Ron Smith
Range: 54 - 57
Carol Mims - Gloria Kilpatrick
Range: 57 - 60
Susan Plank - James Plank
Range: 60 - 63
Janet King - Herb Stappenbeck

UNIX>
```

### Hints

Histolist should work in two phases. First, read each person/score into a struct, and put each struct on one big Dllist. While doing this, keep track of the minimum and maximum scores. Obviously, write this and test it.

Next, you need to find out how many ranges you'll have to keep track of. You do this with integer division. Figure it out for yourself. You will want to malloc() an array of this number of Dllist's. Test to make sure you have the right number of ranges.

Next, traverse your main Dllist, and for each person, figure out which range Dllist this person should go on, and append that person to that Dllist. Finally, for each range, traverse the range's Dllist and print out each person's name.