ITEC 320: Programming Assignment 5

Due Date: 11:59:59 p.m. 5:00 p.m., Friday 4/27/2018

Late programs NOT accepted after 11:59:59 p.m. Saturday

Submit command: submit itec320-01 yarc.adb stackpkg.adb stackpkg-print.adb tree_pkg.adb


Last modified:
Updates:

  1. 2018 Apr 27 12:15:13 PM: Added a tip about adding "pragma ada_2012" to the tree package body to avoid a weird compiler error.
  2. 2018 Apr 26 01:37:23 PM: Changed the due time! Added a Tips section below.
  3. 2018 Apr 21 11:20:17 PM: Finalized assignment and assignment checker. Added a couple of "Other points" on error checking.
  4. 2018 Apr 20 09:29:23 PM: Corrected typos in the submit command above
  5. 2018 Apr 20 09:57:53 AM: Added pragma_Ada_2012 to treepkg and comments to package specs, prettified them, made a few formatting changes and started (draft) assignment checker
  6. 2018 Apr 18 12:22:14 PM: Made changes to all 3 ads files. Make sure that you have a current version, and that you don't have a cached version.
  7. Note: the command j/J may change letters.
  8. I may add some exceptions to the tree package.

[Available now] 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.

Tips:
  1. The statement "pragma Ada_2012" may be needed in the tree package body as well as in the tree package specification. On some compilers, having the pragma in the spec and not in the body causes a weird compiler error.

  2. The child stack package (stackpkg.print) needs to be instantiated using the instantiated parent stack package, not stackpkg. See these notes on child generic packages.
  3. Since the stack is a stack of Trees, it is a stack of pointers to Tree nodes. When two Trees are popped from the stack and used to create a new oper Tree node, it is references that are removed from the stack and stored in the new Tree node. A diagram showing this is in last picture (20180425_110002.jpg) from Wednesday.
  4. Make sure that your pop routine and your clear routine do not create garbage.

You are to write an Ada program whose input is RPN calculations, along with certain other commands. Your program will use a stack implemented with linked lists, and it will also use a linked tree structure to store a calculation.

Sample Run: This input:

        2 3 4 * + 14 RTIJ q
        
produces this output:
2 3 4 *  +
14
+
   2
   *
      3
      4
14
(2+(3*4))
14
   2
+
      3
   *
      4
14
See the assignment checker for more on the commands. Try h and H for help.

Input comes from standard input and consists of rpn integer calculations using +, -, *, / (integer division), and (maybe) ^ (exponentiation). Commands to the calculator include the following:

  1. c - clear the top top element from the stack
  2. C - clear all elements from the entire stack

  3. e - evaluate and print the expression tree on top of the stack
  4. E - evaluate and print the expression trees on the entire stack

  5. h - help (condensed)
  6. H - help

  7. i - print the current top of the stack, as an infix expression
  8. I - print the entire stack, as a list of infix expressions

  9. j - print the current top of the stack, as an infix tree
  10. J - print the entire stack, as a list of infix trees

  11. n - print number of nodes in the element on the top of the stack
  12. N - print total number of nodes on all elements of the stack

  13. p - pretty print (as an expression tree, same as t) the top of the stack
  14. P - pretty print the entire tree (same as T)

  15. r - print the stack top as an rpn expression
  16. R - print the entire tree as rpn expressions

  17. s - print the size of the stack (ie number of stack elements)
  18. S - same as s - print the stack size

  19. t - print the current top of the stack, as an expression tree
  20. T - print the entire stack, as a list of expression trees

  21. q - quit
Print a newline after each command result.

You must implement a dynamic implementation of a stack and a calculation tree, using these stack (and prettified) and stack.print (and prettified) and tree package specifications (and prettified).

It is important that you do not make any changes to these specification files. Also make sure that you have a current version, and not a cached copy, of these routines.

Other points:

You will want to structure your program well and make good use of language features. 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.

When testing, be sure to use lots of different examples. You can either supply test data at the keyboard (remembering to end the input with a ^D at the beginning of a line), or by feeding the contents of a file to it (e.g. calc < test_data) where the use of the UNIX redirection symbol < causes the contents of the file test_data to be feed into the program as if they had been typed in from the keyboard.

When debugging programs, run-time exceptions are a common occurrence. One way to find the line at which an exception occurs is to place put statements in your program so you can follow it's execution. Another way is to use the gdb debugger (ie gnu debugger): these instructions show you how. Note that you can also use gvd (the gnu visual debugger) to debug your program and find the source of an exception as well as other information.

Use the submit command to turn your program in for grading. You may submit as many times as you like, but since only the last submission is kept, if the last one is late, then your assignment is late. Always remember to use the -ls option of submit to check that your submission was received. To submit your work you can use the command at page top.