HTW Berlin Fachbereich 4 Internationaler Bachelor Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Summer Term 2023

Finger Exercises
 
Please have these completed before coming to the lab.

1. Make sure that you understand postfix evaluation.
   
2. Łukasiewicz 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
   2. 1 + 2 * 3
   3. 1 + 2 - 3 ^ 4
   4. 1 ^ 2 - 3 * 4
   5. 1 + 2 * 3 - 4 ^ 5 + 6
   6. ( 1 + 2 ) * 3 + ( 4 ^ ( 5 - 6 ) )
   7. 1 + 2 + 3 / 4 + 5 + 6 * ( 7 + 8 )
   8. 9 - 1 - 2 - 3 * 2 - 1
       
3. For the infix expression a + b ^ c * d ^ e ^ f - g - h / ( i + j ), do the following:
   
1. Show how to generate the corresponding postfix expression.
2. Show how to evaluate the resulting postfix expression.

Lab exercise:

Read through all of the exercises before starting! This exercise will not be done with pair programming, but with pairs working in parallel. Choose your partner yourself. First agree on your interface in exercise 1. Then one person should get exercise 2 to work while the other one starts exercise 3. Then you exchange your code, and voilà, it works! Now you can get back together to do the fourth exercise, but without the gong. Include in your report a reflection on the differences in the tightly regulated pair programming and working together like this.

1. First agree on a Java interface for Stack. What methods do you need? What parameters will they take? What will they return? This is an abstract data type, so don't make it too specific to your exact needs, but what do you expect a Stack to offer. You should call the interface Stack.java.
2. Implement a class StackAsList.java as discussed in the lecture, using a linked list of objects that you implement yourself! Don't use the Stack or LinkedList that is available by default in Java. Try and type it in yourself, not just copy the handout. How will you test this? Your class should include both an exception on stack underflow as well as stack overflow. Will you really need both exceptions? Why or why not? Override the toString() method to provide a useful way of printing a stack. Now make it generic, so it can take values of any type.
   
   
3. Implement a class Postfix.java that has a method
   
   public int evaluate (String pfx) {...}
   
   that takes a String representing a postfix expression and determines the value represented by that expression. You will need to access the individual characters of the string and store them in a stack. This is necessary for the evaluation, luckily your partner is currently in the process of making one. 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!
   
   
4. Now add another method to the Postfix.java class
   
   public String infixToPostfix (String ifx){...}
   
   that converts an infix expression which is presented as a String to a String representing a postfix expression! Throw an exception if your input is not well-formed.


5. Now add another method that reads an infix string from the console, evaluates the result and prints the result to the console.
   

For the bored:

5. Once this works for digits, go on and parse multi-digit 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).
   
6. How can you convert infix to prefix? Prefix to postfix? Find algorithms and implement them. Can you handle unary operators like - or ! as well?

Your report is due by 10.00 pm the evening before your next lab! As in Informatics 1, we are more interested in process than in product, although we are now getting more interested in products as well. Your report should include any collaborators, summarize what you learned, and note the time you invested in this exercise. How many lines of code did you write for each exercise? Record this in your report.