[Solved] CSE222_505 HW4-Stack-Infix,Postfix-Dequeue,Recursion

Q1:

Convert the infix expressions given below to prefix and postfix, then evaluate them. Show your work step by step.

1. i) A + (( B C * D ) / E ) + F G / H ii) ! ( A && ! (( B < C ) || ( C > D ))) || ( C < E )

Write your solution by latex or word and upload it as a StudentNumber.pdf file.

Note: Before evaluation, you must assign values to variables.

Q2:

Implement a Deque class which implements Deque interface and can extend AbstractCollection.

Deque is a queue that supports adding or removing items from both ends of the data structure. To implement it, your class should keep two linked list. One for the elements in the deque and the other to keep the nodes removed. You should use a removed node, if any available, when a new node is needed instead of creating a new node. With this type of operation you can save time for constructing new nodes and garbage collection the nodes that are not used anymore.

You are not allowed to use any class in Collection hierarchy as a member. So, you need to define your own Node class to build a linked list. Note that you need to implement all required methods and Iterator class.

Write a Main class to test each method in your class.

Q3: Recursive functions

Define each of the following problem recursively:

• Identify the base case (or base cases) that stops the recursion
• Define the smaller problem (or problems)
• Explain how to combine solutions of smaller problems to get the solution of original problem

Write recursive methods for the problems.

1. Reversing a string. For example, if the input is this function writes the sentence in reverse, then the output should be reverse in sentence the writes function this.
2. Determining whether a word is elfish or not. A word is considered elfish if it contains the letters: e, l, and f in it, in any order. For example, whiteleaf, tasteful, unfriendly, and waffles are some elfish words.
3. Sorting an array of elements using selection sort algorithm.
4. Evaluating a Prefix expression
5. Evaluating a Postfix expression
6. Printing the elements of an array on the screen as in the example below.

Input:

Output: 1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10

RESTRICTIONS:

• Use only specified data types
• Can be only one main class in each question
• Dont use any other third part library

GENERAL RULES:

• For any question firstly use course news forum in Moodle, and then the contact TA.
• You can submit assignment one day late and will be evaluated over twenty percent (%40).

TECHNICAL RULES:

• Use given CSE222-VM to develop and test your Homeworks (your code must be working on CSE222-VM), CSE222-VM download link will be given on Moodle.
• Implement clean code standards in your code; o Classes, methods and variables names must be meaningful and related with the functionality.

o Your functions and classes must be simple, general, reusable and focus on one topic. o Use standard java code name conventions.

REPORT RULES:

• Add all javadoc documentations for classes, methods, variables etc. All explanation must be meaningful and understandable.
• You should submit your homework code, Javadoc and report to Moodle in a

studentid_hw3.tar.gz file.

• Use the given homework format including selected parts from the table below:

GRADING :