submit itec320-01 bigcalc.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. Specifically, you are to
stackpkg.adb) for this generic stack specification: stackpkg.ads and prettified. Your stack implementation will be almost identical to the stack we covered in class.
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)
bignumpkg-signed.adb) for this Signed Bignum specification and prettified.
bigcalc.adb. Your program should use the packages that you write.
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 bignumThis 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:
new_lineafter 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 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 BIGCALC.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
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
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.
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 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 FirstIn 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 ----- 8766 A number plus its negation naturally gives 10000: 1234 + 8766 ---- 10000Since 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 2Subtraction 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.)
In addition to implementing
you can reimplement 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.
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
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.