ITEC 320: Program 3

Submit command: submit itec320-01 do_calcs.adb stackpkg.adb any.other.files.you.might.write

Due by 11:59:59 p.m. on Sunday 4/5/2020

Due by 11:59:59 p.m. on Thursday 4/2/2020

1. 2020 Mar 30 10:37:49 PM: Changed due date to Sunday night
2. 2020 Mar 04 08:22:28 AM: Assignment checker up and running.
3. 2020 Mar 02 08:48:47 AM: Do you really need variant records? Perhaps not.

This assignment gives you an opportunity to work with records, variant records, generic packages, and look_ahead..

Write a calculator that handles the five basic math operations, plus parentheses, in both left to right and in operator precedence order. Expressions in parentheses are always done first.

Main routine: Your main routine should essentially be the following:

      c : Calculation;
   begin
      while not end_of_file loop
         get_calc (c);
         put_calc (c, left_to_right (c));
         put_calc (c, op_precedence (c));
      end loop; 

Input: Your program is to read a series of calculations from standard input, ending at end of file.

A calculation is an expression followed by a single equal symbol (ie '=') marking the end of the calculation. An expression is an alternating sequence of operands and operators, beginning with an operand and ending with an operand. An operand is either a single integer or an expression enclosed in parentheses. (This is a recursive definition: what's the base case?) Integers in the input can be positive or negative.

An operator is one of the five arithmetic operators: +, -, *, /, and **. The minus sign can denote either binary or unary minus. You do not have to handle "-(", as in "2+-(3+4)=", and I will not test for it.

A calculation will have a total of 100 or fewer operands, operands, and parentheses. There can be any amount (including none) of white space (ie blank, tab, or newline) surrounding the operands and operators, except that there will be no white space after the final calculation.

Operation: All calculations are to be done using integer operations, and there are no floating point numbers. Division is integer division, truncating toward 0 (ie 11/4= gives 2 and -11/4= gives -2, the Ada default). Exponentiation is given by ** (eg 2 ** 3 is 8 and -2 ** 3 is -8). A second operand that is negative for ** gives a result of 0 (eg 2 ** -3 is 0).

Your calculator is to perform the operations in left to right order (ie 2 + 3 * 5 is 25) and in normal precedence order (ie 2 + 3 * 5 is 17 and 2 - 3 * 2 ** 3 is -22). Follow Ada's precedence order (ie ** highest). All operations, including **, are left associative [ie 2-3-4 means (2-3)-4, not 2-(3-4)].

Output: Output should simply be the formatted calculation, followed by its value. This should be done for both left to right and operator precedence order. There should be no prompts: Each line of output is the evaluation of an expression in the input.

Sample Run: If the file p3.txt contains:

 
2+3*5=           

2 * 3 + 5=       
2 - 4 * 2 ** 3 =

10+3*5=           
-2 + -2 =         
2 * (3 + 4)  =          
2 + (3 + 4) *5 =          
-2--3=
(1+2) * (3 * (5 + 5) + (6 * 7)) * 7  =          
      2            
    + 
    2 
    =               

3 =               

2-5=  16/3=     

1 + 2 + 3 + 4 + 5 + 6 =

 >do_calcs < p3.txt
2 + 3 * 5 = 25
2 + 3 * 5 = 17
2 * 3 + 5 = 11
2 * 3 + 5 = 11
2 - 4 * 2 ** 3 = -64
2 - 4 * 2 ** 3 = -30
10 + 3 * 5 = 65
10 + 3 * 5 = 25
-2 + -2 = -4     
-2 + -2 = -4     
2 * (3 + 4)  = 14
2 * (3 + 4)  = 14
2 + (3 + 4) * 5 = 45       
2 + (3 + 4) * 5 = 37       
-2 - -3 = 1
-2 - -3 = 1
(1 + 2) * (3 * (5 + 5) + (6 * 7)) * 7  = 1512
(1 + 2) * (3 * (5 + 5) + (6 * 7)) * 7  = 1512
2 + 2 = 4        
2 + 2 = 4        
3 = 3
3 = 3
2 - 5 = -3      
2 - 5 = -3      
16 / 3 = 5
16 / 3 = 5
1 + 2 + 3 + 4 + 5 + 6 = 21
1 + 2 + 3 + 4 + 5 + 6 = 21

Operator Precedence: To evaluate in operator precedence order, your program should use two stacks to do the following.

1. Each operand is immediately put on the operand stack


2. Each operator, except for the right parenthesis, is eventually pushed onto the operator stack, but some other action might be required before it is pushed, as follows:


1. If the top of the operator stack contains an operator that is equal or higher precedence than the operator in the input, then your program must immediately evaluate the operator on the top of the stack.
• To evaluate the operator that is on top of the stack, follow these steps: pop the operator and its operands from their stacks, perform the operation, and put the result back on the operand stack.


2. Continue evaluating the operator on the top of the operator stack until the operator on top is lower precedence than the operator in the input or until the operator stack is empty. When this occurs, push the operator from the input onto the operator stack.
• In other words, an operator is not pushed as long as the stack contains a higher or equal precedence operator.


3. A "(" is always immediately put onto the stack.


4. A ")" is never put onto the stack. Instead, operators are evaluated (as described above) until a "(" is found on the stack. The "(" is then popped and both parentheses are discarded.


5. An "=" causes the operator stack to be evaluated until it is empty


6. As already stated, "**" has highest precedence, and "+" and "-" have the lowest. When "(" is in the input its precedence it is considered to be very high (ie it is immediately stacked); and when a "(" is on the stack, its precedence is considered very low (ie "*" and "+" are immediately pushed onto it). The "=" and ")" each essentially has a precedence that is so low that it is never pushed.

Example Operator Precedence Evaluation: A typical sequence of evaluation looks like this:

   2 + 3 * (4 + 5) + 6 =
   push 2, push +, push 3, push *, push (, push 4, push +, push 5
   pop 5, pop 4, pop +, perform +, push 9, pop (
   pop 9, pop 3, pop *, perform *, push 27
   pop 27, pop 2, pop +, perform +, push 29
   push +, push 6, 
   pop 6, pop 29, pop +, perform +, giving a final result of 35

In the context of this example, "pop" means save the top element (so that it can be used later) and then pop it off the stack.

Left-to-Right Evaluation: To evaluate in left to right order, slightly modify the instructions above. In essence, always clear the stack before pushing an operator. Handle parentheses the same as in operator precedence.

Stacks: To create your stacks, you are to use the generic stack package whose specification is given here. To do this, you will need to write the implementation (ie stackpkg.adb) for the generic stack specification stackpkg.ads (and prettified). Do NOT modify stackpkg.ads because I will test your stackpkg.adb using this specification.

Other points: You may want to use look_ahead and variant records on this assignment. Make good use of other types, subtypes, and range constraints. Your main program will be quite short, as specified above. Remember: no global variables.

Standard Input and Redirection: Your program should read from standard input, not from a file whose name is coded in your program. To cause standard input to read from a file named, for example, foo, use redirection as follows:

do_calcs < foo

Style: In coming up with your Ada solution to the following problem, please follow my style guide. In particular, please note the use of consistent indentation, named constants, and descriptive constant and variable names. Please remember 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). Also remember to keep your lines less than 80 characters long. Not only does this mean that printouts won't run off the side of the page, but it also makes your programs look neater on an 80 column wide window (a popular size). If you are unsure of an element of programming style, please ask, as I would be more than happy to show you what I want.

Submit: Use the submit command to turn your program in for grading. You may submit as many times as you like, but only the last submission is kept. In particular, be aware that since only the last submission is kept, if the last one is late, then your assignment is late and will thus receive a late penalty. Also remember that you must be on rucs for submit to work.