ITEC 320: Programming Assignment 4

Due date: 11:59:59 p.m. on Tuesday, November 28, 2017

Submit Command: submit itec320-01 bigcalc.adb stackpkg.adb bignumpkg.adb bignumpkg-signed.adb

Last modified:

  1. 2017 Nov 23 07:24:39 PM: Corrected the section on submit.
  2. 2017 Nov 16 04:23:06 PM: Corrected a few typos and added a few words of clarification.
  3. 2017 Nov 16 04:23:06 PM: Yesterday at 16:16 I updated bignumpkg.adb and added the implementation for procedure plus_ov.

You can see an example of this program at assignment checker (which uses gnoga to integrate the GUI, web server, and problem solution). On-campus or VPN session required.

You are to write an Ada program that implements a simple, interactive reverse Polish notation (RPN) calculator that operates on values of type Signed_BigNum. Specifically, you are to

It is important that you do not modify any of these specification files. I will test your ADT's using my copies of the specification files and my clients, and your package body will not compile and fail the test if you modify the package specification.

In the child package, type Signed_BigNum is derived from type BigNum. This means that all BigNum operations are inherited, but all of these operations are also overridden and this hides the ones in BigNumPkg.

Since Signed_BigNum is derived from BigNum, they share an implementation (ie both are arrays of the same length). This means that you can convert a value from one type to the other by simply using the type name and you can use the operations from package bignumpkg:

    b: BigNum;
    s, t: Signed_BigNum;
    b := BigNum(s);        --  Convert 
    s := Signed_BigNum(b);

    s := s + t;  -- addition from bignumpkg.signed

    b := BigNum(s) + BigNum(t);  -- addition from bignum

    s := Signed_BigNum (BigNum(s) + BigNum(t));  -- addition from bignum
This conversion does exactly nothing at runtime. The assignments simply copy s into b and b into s, without changing any values. The purpose of the conversion is to tell the compiler that the assignment is legal.

Your RPN calculator must provide six operations:

  1. addition (+),
  2. subtraction (*),
  3. multiplication (*),
  4. print (p).
  5. pop (P).
  6. quit (q).
The print operation prints the current top of the stack to standard output. Notice that output from the p command includes a new_line after the result. The pop operation pops the stack and does not produce any output. Negative numbers are input using underscore ("_") instead of a minus sign. A typical interactive session follows:

> bigcalc
  2   6   *   p
  4 p
+   p
1 2 - p
_1 _2 + p
9 8 * +

In this example, the output from the program consists of the lines containing 30, 12, 4, 16, -1, -3, and the exception. The other lines contain user input. Note that the output contains no prompts, blank lines, or any other text or explanation except that the print operation (p) produces the numeric result followed by a newline. The numbers in the output are displayed as a result of the p operation in the input. In the above example the BIGCALC.SIGNED_BIGNUM_STACK.STACK_EMPTY exception was raised because the stack only had a single entry when the last addition (+) operation was given. The calculator should halt when q is entered or if an exception occurs. You do not have write code to handle exceptions.

I recommend that you implement a procedure called something like procedure find_next; which will read from Standard Input and skip white space (ie blanks, tabs, and end of lines) and leave the input marker in front of the next non-white-space character or at end of file. Once find_next finds the next item to read, you can use Ada.Text_IO.Look_Ahead (notes) to examine the next input character, and then you can use the appropriate get to read either the next character or the next BigNum. Your program can assume that the input is valid. Your implementations of BigNum and your RPN calculator do not have to support floating point numbers. You may safely assume that all values are integers.

10's Complement Negative Numbers: For simplicity we will be working with 4 digit numbers. Represent your negative numbers using 10's complement: Numbers that have 5..9 in the first digit are negative and numbers that have 0..4 in the first digit are zero or positive. With 4 digits, negative 1 is 9999, the smallest negative number is 5000, and the largest positive number if 4999. In this representation, with 4 digit numbers, the range of positive and negative values is as follows:

10s Complement  Int   Name
     4999       4999  Last
     4998       4998 
     0001       0001  One
     0000       0000  Zero
     9999      -0001  Minus One
     9998      -0002
     5002      -4998
     5001      -4999
     5000      -5000  First
In this representation, a number is negated by subtracting it from the appropriate power of ten (10 ** d where d is the number of digits). An equivalent way, and for this assignment the best way, of doing this is taking the 9's complement of each digit and then adding one. For example, assuming 4 digit integers:

Negating 1234 gives 8766:
10000      9999
-1234     -1234
-----     -----
 8766      8765
           +  1

A number plus its negation naturally gives 10000:
     + 8766
Since we are working with 4 digits, we throw away the 1 and consider 10000 to be 0000 (see below on overflow).

Arithmetic Operations: It's easy to see that addition works as normal for 10's complement, whether the number is positive or negative, as long as the carry out of the sign digit is ignored.

      9999     -1      9999     -1
     +9998   + -2     +0003   +  3
      ----   ----     ----    ----
     19997     -3     10002      2
      9997     -3      0002      2
Subtraction can then be done by simply negating and then doing addition.
   2    0002   0002     -2   9998   9998     -1000   9000    9000
 - 3  - 0003  +9997   - -3  -9997  +0003   - -1000 - 9000  + 1000 
  --    ----   ----   ----   ----  ----    -------  -----  ------
  -1      -1   9999      1         10001                    10000
                                    0001                     0000

Overflow: With unsigned numbers, overflow occurs if there is a carry out of the most significant digit. With 10's complement, overflow occurs if the sign of the result is wrong. For example, -4000 + -4000 is 6000 + 6000 = 12000 which corresponds to a result of 2000, which is positive. (With 2's complement addition, another way of detecting overflow is if the carry into and the carry out of the sign digit are different.)

EXTRA CREDIT: In addition to implementing toString, you can reimplement the multiplication operation ("*") in the bignum package so that it uses the more classic grade school algorithm (which is also MUCH faster than the current implementation). The grade school algorithm involves repeated shifting and adding. I'd recommend that you get the rest of the assignment working before you revise the multiplication.

If you attempt multiply but are unable to complete it correctly, please leave the original, slow multiply in your body using the original name (ie "*"). You may also include your incorrect attempt in the body using the name "times". To facilitate grading, please do NOT submit a body with a non-working version of "*".

When testing, be sure to use lots of different examples. One way to do this, of course, is to supply test data at the keyboard (remembering to end the input with a ^D (linux) or ^Z (windows) at the beginning of a line). However, I'd recommend instead that you put all of your test data into one or more files and that you test your calculator by feeding it the contents of your data file(s) using redirection. To redirect the file test_data.txt into your program use the command bigcalc < test_data where the use of the redirection symbol < causes the contents of the file test_data to be fed into the program as if they had been typed in from the keyboard.

For your own amusement, you might want to compare the RPN calculator for this project with the Unix dc RPN calculator. Do man dc to learn more about dc.

As always, be sure to use good indentation, descriptive constant, variable, type, function, procedure, and package names. Use named constants when appropriate. Also use good commenting style, remembering that the first thing in any program file should be a comment that gives a brief overview of what the file contains (and should do). You might find these commenting guidelines helpful.

Use the submit command given above to turn your program in for grading. You should submit the package bodies for the stack and bignum packages.  I will use the package specifications given above when compiling. You may submit as many times as you like, but only the last submission is kept.

Dr. Okie's Home Page,