GIT Department of Computer Engineering
CSE 222/505 - Spring 2020
Homework 4
This assignment consists of 3 questions.
Q1:
Convert the infix expressions given below to prefix and postfix, then evaluate them. Show your work step by step.
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Output: 1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10
