Lab 6 - Trees

1. If the latest version of your work is not available on Bitbucket (or GitHub), create a commit at the beginning of the lab session and push it. If necessary, consult the materials from the first lab.
2. The teacher will assign you a partner.
   
3. Open your homework in an IDE. The tests must also run successfully, and the file TnodeTest.java must be present in Git.
4. Explain the working principles of your program to your partner. Your partner will do the same, after which you should compare your solutions and decide which one to use as the basis for the additional work.
5. There are two tasks to be completed next, and you may divide them between yourselves as you wish: development and testing. One partner (the “developer”) is responsible for the file Tnode.java, and the other partner (the “tester”) is responsible for the file TnodeTest.java.
   
6. Development: Extend the method buildFromRPN so that it also accepts the operations DUP, SWAP, and ROT in the input, with the following meanings:
   
   • DUP creates a new independent copy of the most recent subtree (it must be verified that such a subtree exists);
   • SWAP exchanges the two most recent subtrees (it must be verified that two subtrees exist);
   • ROT rotates the three most recent subtrees by moving the third one into the first position (it must be verified that three subtrees exist).
   Review the meaning of these operations in the guide for the defense of Homework 3. When the tree is evaluated, the result must be the same as the one produced by the method interpret for the same input.

Examples:

• "2 5 SWAP -" must swap the subtrees 2 and 5 and produce the tree -(5, 2)
  
• "3 DUP *" must copy the tree 3 and produce the tree *(3, 3)
  
• "2 5 9 ROT - +" must move the tree 2 into the first position and produce the tree +(5, -(9, 2))
  
• "2 5 9 ROT + SWAP -" must produce the tree -(+(9, 2), 5)
  
• "2 5 DUP ROT - + DUP *" must produce the tree *(+(5, -(5, 2)), +(5, -(5, 2)))
  
• "-3 -5 -7 ROT - SWAP DUP * +" must produce the tree +(-(-7, -3), *(-5, -5))
  

Implement the required changes in the method buildFromRPN. Be sure to test all of the examples above.

7. Testing: Write JUnit 4 tests for all the examples listed in the previous section (extend the file TnodeTest.java on the basis of the examples already provided there). In addition, include tests that check stack underflow conditions for the methods: DUP requires one element, SWAP requires two, and ROT requires three elements. Add at least three negative tests.
8. Create a new commit with the message "Developer: Surname, Tester: Surname" and push it to Bitbucket (or GitHub). Your partner must do the same with their code. Do this only after the testing part is working.
9. Demonstrate the working solution.
10. Complete the Moodle assignment “Homework 5 defense”.