submit itec320-01 rpn_calc.adb stackpkg.adb bignumpkg.adb bignumpkg-signed.adb
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
stackpkg.adb) for this generic stack specification: stackpkg.ads and prettified. You can reuse and resubmit the stack implementation from the previous assignment.
bignumpackage body (bignumpkg.adb and prettified) to implement the
toStringoperation, which is currently a stub. Your
toStringoperation should remove leading zeros. The specification for this package is in (bignumpkg.ads and prettified) See also the extra credit below.
bignumpkg-signed.adb) for this Signed Bignum specification and prettified.
rpn_calc.adb. Your program should use the packages that you write.
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:
new_lineafter 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 10 20+p 30 p 30 P 2 6 * p 12 4 p 4 + p 16 P 1 2 - p -1 P _1 _2 + p -3 P 9 8 * + raised RPN_CALC.SIGNED_BIGNUM_STACK.STACK_EMPTY
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
operation in the input.
In the above example the
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
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.
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
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.
plus_ov. The values returned in the parameters to
plus_ovare 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
you can re-implement the multiplication operation (
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
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
dc RPN calculator. Do
man dc to learn more
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.