CS14 Assignment 2
Handed out: April 19th, 2001
Due: April 26th, 2001
1. How would you use a stack to reverse a string? Describe how, or write a function that does this.
2. How would you use a queue to echo a string? Describe how, or write a function that does this.
3. Evaluate the following RPN (postfix) expressions using a stack. Write down all Push() and Pop() steps and show the stack after each one.
a. 3 5 * 2 +
b. 3 5 + 2 *
c. 3 5 2 + *
d. 3 5 2 * +
e. 4 2 2 * / 3 3 * + 4 2 * -
*4. (Extra credit) Parentheses in an equation are said to be balanced if all left parens have matching right parens, and if, when scanning left to right, at any point the number of left parens encountered so far is greater o equal to the number of right parens.
For example, (a*(b+c)*(d+a)) is balanced, but (a+b)) and (d*))a+e( are not.
Which data structure (stack or queue) would you use to check of the parentheses in an equation are balanced? Describe how or write a function that does this.
5. Practice with linked lists. In all the examples, assume a linked list of integers.
Please note: this is a written exercise, but that should not prevent you from using the computer to check your work.
a. Given the head node of a linked list, write the code to delete all repetitions from the list.
For example, if the original list is <2,6,3,9,9,8,4,2,1,7,4, 5>, and the splitting value is 5,
then the two new lists are <2,3,4,2,1,4> and <6,9,9,8,7,5>.
c. Given the head node of an unordered linked list and a number, called the "splitting value", write the code to split the list into two new lists. One list will contain all nodes from the original list with data smaller than the number, the second will contain all the other nodes. The order and number of nodes from the original list should be preserved. This is different from part b in that no new nodes are created, and the original list is destroyed.