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. of FRIDAY 3/23/2018

Due by 11:59:59 p.m. of Tuesday 3/20/2018


Last modified:
Updates:
  1. 2018 Mar 22 09:36:20 PM: Corrected Assignment Checker: did ** in correct order and checked for overflow
  2. 2018 Mar 22 09:36:20 PM: get and put for calculations can be given names such as read and print
  3. 2018 Mar 20 03:53:46 PM: I will not test for -(, as in 2+-(3+4)=
  4. 2018 Mar 20 03:53:46 PM: Added a missing = to a calculation in the sample run
  5. 2018 Mar 15 04:24:40 PM: Changed due date and slightly cleaned up the wording of the section Stacks.
  6. 2018 Mar 02 09:46:04 AM: Set due date.
  7. 2018 Mar 02 09:46:04 AM: Started assignment checker, with suggested datasets, in order.
  8. 2018 Mar 02 09:46:04 AM: All operations, including **, are left associative.
  9. 2018 Mar 02 09:46:04 AM: Hint: You can use look_ahead to skip white and to determine what follows the white space (ie integer, operator, parenthesis, or equal).
  10. 2018 Mar 02 09:46:04 AM: You can assume that there will be no white space following the final calculation.
  11. 2018 Mar 02 09:46:04 AM: Your main routine must be as follows:
  12.       c: Calculation;
       begin
          while not end_of_file loop
             get(c);
             put(c, left_to_right(c));
             put(c, op_precedence(c));
          end loop; 
  13. 2018 Feb 26 03:12:48 PM: Corrected a few typos and order of output for 2 - 4 * 2 ** 3

Assignment checker now available (needs on campus or vpn connection). This version is more robust than yours needs to be.

This assignment gives you an opportunity to work with records and generic packages. Write a calculator that does the five basic math operations plus parentheses, in both left to right and in operator precedence order. Expressions in parentheses are always done first.

Input: 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. Note that this is a recursive definition: what's the base case? An operator is one of the five arithmetic operators: +, -, *, /, and **. Your program should read from standard input.

A calculation will have 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.

Input and 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).

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 =
 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 =
Then a sample run is as follows:
 >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
Errors: If your input is not valid, then your program can simply end with a message stating that the input is not valid or do anything else. I will not test your program with invalid input.

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.

    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.

    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 should be relatively short will be very short, as specified at the top. Remember to not use 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
Your program should continue execution until end of file is reached. When input is redirected from a file, end of file is automatically detected. However, when running your program interactively (ie standard input is reading from the keyboard) there is not file, and so you must enter a special character that indicates that your program should assume that end of file has been reached (even though there is no actual file). To do this in unix enter CTRL-D, and in windows enter CTRL-Z then RETURN. The notation CTRL-Z means to hold down the CONTROL key and press Z.

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.