Lab 7: Stack

Objectives

Assignment

1. Using your list_t class (acting as a stack; you cannot use the STL's list class), provide the implementation of the infix expression evaluator described in the text (pp. 97–102).
2. Your code should be able to evaluate the expression suggested in the text, e.g.,

   1 + 2 * 3 + ( 4 * 5 + 6 ) * 7
   	

3. Your code should handle all operators *, /, +, - as well as (one level) of () nesting
4. Your program must output the postfix experssion followed by its evaluation
5. Use q or ctrl-d to quit (either should work)
6. Sample output:
   

   1 + 2 * 3 + ( 4 * 5 + 6 ) * 7
   1 2 3 * + 4 5 * 6 + 7 * + 
   189
   8 + (2 * 6)
   8 2 6 * + 
   20
   20 / 10 + 2
   20 10 / 2 + 
   4
   q
   	

Hints

1. One way to implement the simple expression evaluator is to use two stacks: one to convert the infix input to a postfix string, the second to process the postfix expression.
2. A good way to test your program is to first implement it with the STL std::list acting as a stack, then simply commenting out these stack declarations and substituting your list_t in place of the STL stack.

Turn in

1. A README file containing
   1. Course id--section no
   2. Name
   3. Lab description
   4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
   5. Lessons learned, identified interesting features of your program
   6. Any special usage instructions
2. Makefile
3. source code (.h headers and .cpp source)
4. object code (do a make clean before tar)

How to hand in