2
Could I please have the solutions to the following problems
1. (4 points) Your friend has to write code to make sure that the parentheses in an arithmetic expression are balanced, i.e. for every left parenthesis there is a matching right parenthesis. She wants to use a tree to do this. You argue that if all you want to do is match parentheses, then a stack will work fine. How will you use a stack to do this?
2. (6 points) A palindrome is a string that reads the same forwards as backwards.
Describe how you would implement a function that, given a string, determines whether it is a palindrome. Your function can use only one stack and one queue. Your function should return true if the string is a palindrome and false otherwise.
For example:
palindrome( “abba”) true
palindrome( “bbba” ) false
3. (20 points) For this question you are to implement a two-ended stack of ints. We will define a two-ended stack as a list in which entries can be pushed or popped from either the first or last position of the list, but no changes may be made elsewhere in the list. We will define the fundamental operations on a two-ended stack to be:
push_front – pushes an item on the front of the two-ended stack
push_back - pushes an item on the back of the two-ended stack
pop_front – removes and returns an item from the front of the two-ended stack
pop_back – removes and returns an item from the back of the two-ended stack
Your assignment is to implement the TEStack (two-ended stack) methods listed below using a singly-linked list. You should use the header file provided below. You do not need to implement copy constructors, destructors, or operator= for these classes, but otherwise the routines you implement should handle memory management appropriately.
a) (2 points) Implement the constructor for TEStack.
b) (6 points) Implement your push_back method.
c) (6 points) Implement your pop_back method.
d) (6 points) Implement your pop_front method:
4. (12 marks) Recursion
Consider the following recursive program.
//n is any positive integer
//m is a positive integer between 2 and 9
void fun(int n, int m)
{ if (n<m)
cout << n;
else { fun(n/m, m);
cout << n%m;
}
}
a) (3 marks) What is the output for fun(15, 2)?
b) (3 marks) Given the following recursive code. Point out the possible errors in the code.
//num is a positive integer
int fac(int num)
{ if (num_1)
return 1;
else {return num*fac(num+1);
}
}
c) (6 marks) Given the following function which computes Fibonacci numbers using recursive function, write a non-recursive version of function fib.
//num is a positive integer
int fib(int num)
{ if (num==0) return 0;
if (num==1) return 1;
return (fib(num − 1)+fib(num − 2));
}
5. a) (3 points) Draw the binary search tree created by inserting these values in this order:
3 4 0 2 8 6 5 1 7 9
b) (2 points) Give a pre-order traversal of your tree shown above:
c) (2 points) Give a post-order traversal of your tree shown above:
d) (3 points) Delete the root of the tree shown above using one of the two methods described in class. Draw the new tree.
6. (20 points) Tower of Hanoi
We are given a tower of n disks, initially stacked in decreasing size on one of three pegs, say A.
The objective is to transfer the entire tower to one of the other pegs, say C, using the other, say B, as a temporary peg, and obeying the following two rules of the game:
• only one disk at a time can be moved
• a larger disk can never be moved onto a smaller one
Implement the Towers of Hanoi using recursive data structures in C++. State all the assumptions you may decide to make.
