ITEC 320: Program 4

Due: 11:59:59 Monday 4/17/17

Due: 11:59:59 Thursday 4/13/17

Submit command: submit itec320-01 calc.adb calcpkg.adb stackpkg.adb wordpkg.adb

Last modified:

  1. 2017 Apr 15 12:03:12 PM: Added information, in Other Points, on making sure that you create your data file on the same OS as you are running.
  2. 2017 Apr 10 08:18:52 AM: Struck out the phrase "command line" from the assignment description. Write your program to work correctly when standard input is redirected from a file. You do not have to handle the complexities of standard input from the keyboard.
  3. 2017 Apr 04 06:02:17 PM: Changed due date.
  4. 2017 Apr 04 03:29:15 PM: Assignment checker now running.

Now available: 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.

Write a command line calculator that does 5 basic operations (+, -, *, /, **). Specifically, do the following:

You may add routines to any of the package specifications that you submit, but do not modify the signatures of, or remove, any public routines from these packages. You may submit additional packages if you want (eg stackpkg.utils).

Calculator Operation: The operations operate on and return integers, except for ** which requires a Natural exponent. Division is integer division. Calculations are left associative, are done in normal precedence order (ie ** is highest, * and / are middle, and + and - are low precedence), and can contain parentheses. The end of a calculation is marked by an =.

Calcpkg: Your program is to implement the package calcpkg which allows clients to work with calculations and which has the following (incomplete) specification:
package calcpkg is
   type Calculation is limited private;

   procedure get(c: out Calculation);
   procedure put(c: Calculation);

   function to_string(c: Calculation) return String;
   function length(c: Calculation) return Natural;

   function Result(c: Calculation) return Integer;
end calcpkg;

You may add routines to the package specification, but do not change the signatures of the given routines. You must, of course, complete the private section.

The routines operate as follows:

Input: In the input all pairs of operators and operands, including = and parentheses, will be separated by white space (so that wordpkg can be used for input). No calculation will contain a total of more than 50 operands and operators (including parentheses and the =).

Client and Sample Run: Your client (ie calc.adb) will be similar to the following:

   c : Calculation;
      exit when length(c) = 0;
      put_line(to_string(c) & result(c)'img);
   end loop; 
This input, when read from standard input:
11 + -2 =
  2 + 
    3 * ( 4 + 5 )
-2 ** 3 =
will produce the following on standard output:
11 + -2 = 9
2 + 3 * ( 4 + 5 ) = 29
-2 ** 3 = -8 

The lengths of the calculations above are 4, 10, and 4, respectively.

Wordpkg: Modify wordpkg specification and body so that wordpkg provides this function:

   function to_string (w : Word) return String;
with the obvious meaning.

Stack Package: To create your stacks, you are to use the generic stack package whose specification is given here (which you may not modify). To do this, you will need to write the implementation (stackpkg.adb) for this generic stack specification.

Other Points:

Operator Precedence Evaluation: To do the calculation you are to do operator precedence evaluation. This requires two stacks that hold pending operations: one for operands and one for operators (ie for arithmetic operators and left parentheses). The evaluation follows these rules:

  1. Operands and operators are examined in the order in which they appear in the input.

  2. After an operand is examined, it is immediately put onto the operand stack.

  3. After a left parenthesis is examined, it is put on the operator stack.

  4. When an arithmetic operator is examined, it will eventually be put on the operator stack, but some other action might be required first, as described next:

    1. An arithmetic operator (call it X) CANNOT be put on the stack if the operator currently on top of the stack (call it Y) is of equal or higher precedence than X. If there is an operator of equal or higher precedence on top of the stack, then you must repeatedly evaluate each operator on top of the stack until either the stack is empty or the top of the operator stack has an operator of lower precedence than X. At that point, the operator X is put on the stack.

    2. To evaluate an arithmetic operator that is on the stack, pop the operator and its operands, perform the operation, and push the result.

    3. As mentioned above, operator precedence is as follows: "+" and "-" are equal to each other and higher than "(" on the stack, "*" and "/ are equal to each other and higher than "+", and "**" is higher than "*". The precedence of the operator "(" effectively changes when that operator is moved from the input to the stack.

  5. When the operator being examined is a ")", then the operators on the stack should be evaluated until a "(" is found on the stack at which point the "(" is removed from the stack and the ")" is discarded. At this point, of course, the value on top of the operand stack is the value of the expression that was inside the parentheses.

  6. When an "=" is examined, the operations on the operator stack are evaluated until that stack is empty.

For this example input "2 + 3 * (4 + 5 * 6) + 7 =", the sequence of evaluation is this:

push 2, push +, push 3, push *, push (, 
push 4, push +, push 5, push *, push 6
pop 6, pop 5, pop *, perform *, push 30,
pop 30, pop 4, pop +, perform +, push 34, pop (
pop 34, pop 3, pop *, perform *, push 102,
pop 102, pop 2, pop +, perform +, push 104,
push +, push 7, 
pop 7, pop 104, pop +, perform +, push 111

At the end of the sequence given above, the operand stack contains only 111 and the operator stack is empty. For brevity this example does no specify which stack is being used, and it does not show the calls to top needed before the calls to pop.

Submit: Use the submit command to turn your program in for grading, following the submit command given at the beginning of the assignment. You may submit as many times as you like, but only the last submission is kept.