CS140 -- Lab 7

Lab Objective

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

Lab Materials

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.