Homework 4 - A Calculator

Homework 4
A Calculator - Programming Project 6, page 375

Due: Monday, May 3 at 11:59pm

Assignment

You will write a program that acts as a simple calculator, reading and evaluating one arithmetic expression at a time until the user chooses to terminate the program. The expressions are ordinary arithmetic expressions expressed using infix notation. The expressions need not be fully parenthesized. If an entered expression is not well-formed, the user is asked to re-enter the expression.

Outcomes

After successfully completing this assignment, you will be able to...

Use the stack template class
Implement the stack-based algorithms for evaluating an arithmetic expression.

Before Starting

Read all of Chapter 7, with particular attention to Section 7.2. Read Appendix F, pp. 756 - 760, for information about reading from standard input.

Pre-grading for assignments completed early

Assignments submitted by Tuesday, April 27 at 11:59pm will be graded by the TAs during lab on Wednesday, April 28. In order to have your assignment pre-graded, you must attend your lab session on April 28. Pre-grading will not include a grade on the documentation, just on the functional part of the assignment (documentation grades will be assigned later).

What you should do

Create a directory to hold your hw4 files, and cd to that directory.
Copy the files from the class directory to your hw4 directory:
```
      cp /cs/cs2005/hw/hw4/* .
```
Your hw4 directory should now contain these files: stack1.h and stack1.template. You should not make any changes to these files. Reminder: since this is a template class, it is not separately compiled. Instead, your main program simply includes "stack1.h". With this include statement in place, the client program can declare and use any kind of stack.
Write the client program (the calculator), which should meet the specifications described below. Name your client hw4.cxx.
When you have thoroughly tested your program, submit your client program, and the header and template files for the stack class, using the following turnin command:
```
      /cs/bin/turnin submit cs2005 hw4 hw4.cxx stack1.h stack1.template
```

Specifications

As described above, the purpose of the main program is to read and evaluate arithmetic expressions, and print their values to cout.

The expressions consist of numbers of type double, together with the binary operators +, -, *, /. The input numbers are non-negative (your program does not have to be able to handle the unary - operator). Your program should be able to detect the character 'q' as the first character in a line of input, but otherwise you may assume that input consists only of numbers, operators, parentheses, spaces, and newlines.
The expressions are entered in infix notation.
Expressions need not be fully-parenthesized.
Any number of spaces may be included within an expression.
The program should be able to detect expressions that are not well-formed and should prompt the user to re-enter a correct expression
The program should be able to detect division by zero and should prompt the user to re-enter a correct expression
The output of the program should be formatted as shown in the Sample Execution

Sample Execution

Enter an arithmetic expression, or 'q' to quit
> 4+3
= 7
> 4  + 3
= 7
> (4) + 3
= 7
> (4+3)
= 7
> 4+3)
Error in expression, please enter it again
> (4+3
Error in expression, please enter it again
> (4+3))
Error in expression, please enter it again
> ((4) + 3
Error in expression, please enter it again
> 4/0
Error in expression, please enter it again
> .4+.3
= 0.7
> 4+3-2*12-16
= -33
> q

Algorithm

Here is an algorithm you can use to evaluate an infix expression. The algorithm uses two stacks, one to hold the operators (Operators) and one to hold the numbers (Numbers). A "token" can be either a number, or one of the symbols (, +, -, *, /, ).

  for each token in the input line
  {
    if (token is a number)
       push token on Numbers

    else if (token is a left parenthesis)
       push token on Operators

    else if (token is one of the operators +,-,*,/)
       if (Operators is empty)
           push token on Operators
       else if (token has higher precedence than the operator on the top of Operators)
           push token on Operators
       else
       {
          while (Operators is not empty and the precedence of token is <= the
                 operator on the top of Operators)
                evaluate_stack_tops      // see pp 349 - 351
          push token on Operators
       }

    else if (token is a right parenthesis)
    {
      while (operator on the top of Operators is not a left parenthesis)
             evaluate_stack_tops
      pop Operators 
    }
   }  // end for

   while (Operators is not empty)
      evaluate_stack_tops

(When the algorithm terminates, the result of the expression will be on top of Numbers.)

Note that this algorithm does not take care of any error checking (you will need to add that yourself). When implementing this algorithm, you should define subordinate functions where appropriate.

Grading

(100 points)

Functionality (70%), Documentation (30%) The homework will be graded on its ability to recover from the stated error conditions, and its ability to generate the correct output given valid input. Programs must compile to earn points for functionality. No exceptions. The algorithm given above is complicated; we will look carefully at the comments in your source code and grade them based on clarity and completeness. All functions must be documented with pre- and post-conditions.