15-121 SPRING 2010 [CORTINA]

LAB 5

In this lab, you will implement a new version of the ArrayStack class and then test it with the applications given in lecture.

EXERCISES

Download the Stacks.zip project file discussed in lecture.

Create a new class named ArrayStack2 that implements a stack where the top of the stack is always stored in position 0 of the array. When an element is pushed on this stack, the elements on the stack must be shifted to make room for the new element. Likewise, when an element is popped from this stack, the elements on the stack must be shifted the opposite direction to fill in the gap left by the removed element. Your class should implement the LIFOStack interface so it must include all of the required methods specified by that interface in the project.
Test your ArrayStack2 class by changing the PostfixEvaluator class so that it uses a stack of type ArrayStack2 instead of ListStack.
Create a new class Calculator that contains a main method that asks the user for an expression in infix notation and computes its value by first converting it to postfix and then evaluating its value. The infix expression must be input with spaces between each token. (This should not require a lot of code... THINK.)
The postfix evaluator and infix-to-postfix generators can handle input of multiple digit positive integers as operands. How does it know if a token is an integer? What happens if someone enters a token like 7UP that looks like an integer initially but really isn't? Modify the infix-to-postfix converter to deal with this case by throwing a syntax error exception. Catch this in your calculator and ask the user to input a valid infix expression until the user finally does.

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

Add the exponential operator (^) to the postfix calculator and the infix-to-postfix converter. The exponential operator has higher precedence than multiplication and division, however if more than one appears in the expression, they should be evaluated right to left, not left to right. Thus 2^3^5 is 2^3⁵, not (2³)⁵.
Create a GUI for the calculator that contains a text field that allows the user to input an infix expression, and then displays the value of the infix expression in another text field if the user clicks a button in the window that says EVALUATE.