Sample Programming Assignment
Chapter 6
Stacks

I suggest that you use the EasyReader class to read the lines from the input file. A method along these lines will also help:

static double evaluate_line(EasyReader input)
// Postcondition: One line of the input file has been read (up to
// and including the newline character). The method has tried to
// interpret this line as a infix arithmetic 
// expression made up of nonnegative double numbers and the
// four operations + - * and /. If everything went okay, then
// the return value is the value of this expression; If there were
// problems, then the return value is Double.NaN.

The implementation of this method could convert the infix expression to a postfix expression and then evaluate it, but a better idea is to evaluate the expression directly, with this pseudocode:

1. Initialize one stack of characters to hold operation symbols and one stack of numbers to hold intermediate results.

2. Do the following until the line is completely read:
   • if the next input is a left parenthesis, then read it and push it onto the character stack;
   • else if the next input is a number, then read it and push it onto the number stack;
   • else if the next input is one of the operation symbols, then pop symbols from the character stack until one of three things happens: (a) the stack becomes empty, or (b) the next symbol on the stack is a left parenthesis, or (c) the next symbol on the stack is an opeation with lower precedence than the next input symbol. When you are done popping, then push the new input symbol onto the character stack.
   • else if the next symbol is a right parenthesis, then pop operations off the character stack until you reach a left parenthesis. Also pop and discard this left parenthesis.
   • else the next input symbol should be a space that you can discard.
   Within this loop, each time you pop a symbol from the character stack, you should apply that operation to the top two numbers on the numbers stack and push the answer back onto the numbers stack.

3. When the loop finishes, pop and process any remaining symbols on the character stack. There should then be one number on the numbers stack, and this number is the value of the expression.

There are several things that can go wrong in the pseudocode, such as not finding a left parenthesis on the character stack to match a right parenthesis that you have just read. Each of these potential problems should cause the method to read the rest of the input line and return the value Double.NaN.

You will find it useful to use the DoubleStack and CharStack classes from Chapter 6 of the textbook.