ITEC 320: Programming Assignment 4

Due date: 11:59:59 p.m. on Tuesday, April 10, 2018

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

Last modified:

  1. 2018 Apr 06 05:25:00 PM: Fixed some errors in the assignment checker.
  2. 2018 Apr 05 02:34:48 PM: Removed "DRAFT", set due date, made lots of wording changes.
  3. 2018 Apr 05 09:40:35 AM: Corrected an error in the definition of the constant minus_one.

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, as defined below. Specifically, you are to

Notice that the package BignumPkg defines the type BigNum, and the child package BignumPkg.Signed defines the type SignedBigNum. Be careful to distinguish, then, between the packages and the types that are defined in these packages.

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 if you modify the package specification then your package body will not compile and thus fail the test.

In the child package, type Signed_BigNum is derived from type BigNum:

    type Signed_BigNum is new BigNum; 
Because Signed_BigNum is a derived type, it inherits all of the operations from its parent type, BigNum. However, the inherited operations do not do what we want for Signed_BigNums, and so they are all redefined in package BignumPkg.Signed. You will implement these redefined operations in the body of BignumPkg.Signed.

In redefining the operations, you will want to access and use the original operations from the parent package. To do this, you can use type conversion, as shown below. Notice that the operation that is called is determined by the type of the parameter, not by specifying the package.

    b: BigNum;
    s, t: Signed_BigNum;

    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

Your RPN calculator must provide six operations:

  1. addition (+),
  2. subtraction (-),
  3. multiplication (*),
  4. print (p).
  5. pop (P).
  6. quit (q).
There is no exponentiation or division operation. The print operation prints the current top of the stack to standard output, along with a new_line after the result. The pop operation pops the stack and does not produce any output. Negative numbers are input using an adjacent, leading underscore ("_"), not a minus sign.

Sample Run: A typical interactive session follows:

> rpn_calc
  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 RPN_CALC.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. Your client does not need to handle exceptions (although the assignment checker does handle them).

As in the previous assignment, you may want to implement a procedure called something like procedure find_next; which reads from Standard Input and skips 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 Signed_BigNum.

Your program can assume that the input is valid. Your client does no have to check for erroneous input and for overflows, but your arithmetic operations in your package body do need to raise Signed_BigNumOverFlow when it occurs. Your implementations of Signed_BigNum and your RPN calculator do not have to support floating point numbers. You may safely assume that all values are integers.

Sign+Magnitude Negative Numbers: For simplicity this explanation will use 4 digit numbers. Represent your negative numbers using Sign+Magnitude. In this representation, numbers that have 0..4 in the first digit represent zero or positive numbers, and numbers that have 5..9 in the first digit represent zero or negative numbers. With 4 digits, positive numbers 0001 to 4999 are represented as 0001 to 4999, as expected. Negative 1 is represented as 5001, and the smallest negative number is -4999, represented as 9999. Thus it is impossible to represent a number outside of the range -4999 .. 4999.

There are two representations for zero: positive and negative. Negative zero is equal to positive zero, and it is printed without a sign, the same as positive zero, In this representation, with 4 digit numbers, the range of positive and negative values can be seen as follows:

Sign+Magnitude  Int   Name
     0000       0000  Zero
     0001       0001  One
      ...       ...   
     4998       4998 
     4999       4999  Last (the largest Signed_BigNum)
     5000       0000  Negative Zero
     5001      -0001  Negative One
     5002      -0002
     ...        ...
     6000      -0001  Negative 1000
     6001      -0001  Negative 1001
     ...        ...
     9998      -4998
     9999      -4999  First (the smallest Signed_BigNum)
In this representation, a number X that is less than 5000 represents itself, and if X > 5000, then it represents the number 5000 - X. Similarly, a number can be negated by adding 5000 to positive numbers and subtracting 5000 from negative numbers. When using Signed Magnitude, special rules are needed for arithmetic operations.

Addition: The sign of the operands determines how to perform addition and how to check for overflow.

Addition of two positive SBNs can be done using regular BN addition, but if the result is negative, then overflow has occurred. Addition of 2 negative numbers can easily be done by negating each number, adding them, checking for overflow, and then negating the result.

Addition of numbers of differing sign is done using subtraction.

Subtraction Operands: The rules below define subtraction of two positive numbers. The rules also apply for addition of numbers of differing signs, and these should be converted to subtraction of the same sign. Similarly, subtraction of numbers of differing signs should be converted to the equivalent addition of numbers of the same sign. Subtraction is not done using the normal grade school rules of borrowing; instead it uses nines-complement (9C).

Nines-Complement: The 9C of digit D is 9-D. The 9C of number of several digits is the 9C of each digit. So the 9C of 0, 3, 9, 20, and 123 are 9, 6, 0, 79, and 876, respectively. If we need a fixed number of digits, then we use leading zeros. For example, using three digits, the 9C(2) = 9C(002) = 997.

Subtraction Rules: To use 9C to subtract X - Y, where X > 0 and Y > 0 and both are 4 digits, follow these rules.

  1. Sum = X + 9C(Y)
  2. Result = (If Sum < 10_000 then 5_000 + 9C(Sum) else Sum + 1 - 10_000)
Note that in step 1, the sum can be 5 digits (ie it can overflow), and so you will need to use plus_ov. The values returned in the parameters to plus_ov are also useful in step 2 since you cannot represent 10_000 with 4 digit numbers.

To use 9C to subtract X - Y, where X < 0 and Y < 0 and both are 4 digits, you can use negate(negate(X)-negate(Y)) or negate(Y)-negate(X).

Note that subtraction of two numbers of the same sign cannot cause Signed_BigNum overflow. Finally, you may want to define functions add_pos and sub_pos, and call them as needed by your general addition and subtraction functions.

Multiplication: Multiplication of X and Y is as follows: calculate abs(X) * abs(Y) using BigNum's times operator, check for overflow, and adjust sign as needed. If the sign of the product is wrong, then overflow has occurred.

Extra Credit (10 points): In addition to implementing toString, you can re-implement 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.

Other Points: 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 rpn_calc < 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,