1. Lukasièwicz was a Polish logician, so his notation for parentheses-free expressions is often called Reverse Polish Notation. To get your brain in gear, convert the following expressions to RPN! What are the values of the expressions?
1. 1 + 2 - 3 ^ 4
2. 1 ^ 2 - 3 * 4
3. 1 + 2 * 3 - 4 ^ 5 + 6
4. ( 1 + 2 ) * 3 + ( 4 ^ ( 5 - 6 ) )
5. 1 + 2 + 3 / 4 + 5 + 6 * ( 7 + 8 )
6. 9 - 1 - 2 - 3 * 2 - 1

 
2. For the infix expression a + b ^ c * d ^ e ^ f - g - h / ( i + j ), do the following:
1. Show how the operator precedence parsing algorithm generates the corresponding postfix expression.
2. Show how a postfix machine evaluates the resulting postfix expression.

 
3. Explain, in general terms, how unary operators can be incorporated into the expression evaluators. Assume that the unary operators precede their operands and have high precedence.

Lab exercises

Read through all of the exercises before starting! Oh dear, this is a lot of work. I guess we can't play one-person-types-while-the-other-looks-on this week.... I would strongly suggest that one person get exercise 1 to work while the other one starts exercise 2. Then you exchange code, and voilà, it works! Now you can get back together to do the third exercise. Do not waste time in the lab! You need to be at your computer, with it turned on and all books and pens ready to work at the start of class!

1. Implement a class Stack.java as discussed in the lecture, using an array of objects! The code is available under reading materials. Extend the class to include both an exception on stack underflow as well as stack overflow.
2. Implement a class Postfix.java that has a method
   public static int evaluate (Stack pfs){...}
   that takes a Stack of Characters representing a postfix expression and determines the value represented by that expression. Build a test class and check the postfix expressions you did in the finger exercises. If there is a difference between the value computed and the value expected, either you were wrong, or the implementation is wrong or both. Do not go on before you are sure that this is working right!
3. Now add another method to the Postfix.java class
   public static Stack infixToPostfix (Stack ifs){...}
   that converts a Stack representing an infix expression to a Stack representing a postfix expression!
4. (For the bored) Add another method 
   public static Stack stringToInfix (String s){...}
   that parses a String into a Stack that represents the infix notation. Once this works for digits, go on and parse multidigit Integers out of the String. Can you do it for double values as well? If you are still bored, parse mixed expressions (doubles and ints in the same expression).