The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Lab #8
For labs meeting the Oct. 17-19, 2000

Now that you have an implementation (from Lab #7) of Stacks_Generic, you can do somethng interesting with this package. Recall the Bauer-Samelson algorithm we discussed in class last Thursday. This is described on p. 297 of the text. Your task is to use this algorithm in a little program to emulate a Hewlett-Packard calculator. Instantiate the stack package for Float. THe user will enter input in RPN form, one value per line. The expression (3.52 * -25.79) / (24 + 17) would be entered as

3.52
-25.79
*
24
17
+
/
=

The basic algorithm will then be:

LOOP
  Read a value from the keyboard
  IF this value is a Float quantity THEN
    Push it on the stack
  ELSIF this value is '=' THEN
    EXIT
  ELSE this value is an operator (+, -, *, /) so (we'll assume input is always "good")
    Pop the stack twice into two variables, and apply the operator to these variables
    Push the result back into the stack
  END IF;
END LOOP;
Display the final result

You can use the following clever scheme to read the values. Declare a Float variable F and a character variable C, then refine the above
into

LOOP
  BEGIN -- try to read a Float; if we can't, try to read an operator character
    Read a line (value followed by ENTER) into a string Line
    Ada.Float_Text_IO.Get(From => Line, Item => F, Last => TokenLength);
    Push F onto stack  -- no exception was raised
  EXCEPTION
    WHEN Ada.Text_IO.Data_Error =>
      C := Line(1); -- it's an operator; the first Get left it in the input
      IF the value is '=', THEN
        EXIT;
      ELSE
        Pop stack twice and apply operator
        Push result back into stack
      END IF
  END -- exception block
END LOOP
Display final result

Enjoy!