CSE
214, Spring 2013 (TA Version)
Recitation 4 – Stacks
1. [10 minutes] For the following infix expression: a*(b-d)/f*g
a. Convert expression to postfix.
answer: abd-*f/g* (use the stack method to resolve this answer if necessary)
b. Convert expression to prefix
answer (*(/(*a(-bd))f)g)
2.
a. [5 minutes] Evaluate the following postfix expression using stacks: 534+*63/21+-*
CHAR STACK
5 5
3 5, 3
4 5, 3, 4
+ 5, 7
* 35
6 35, 6
3 35, 6, 3
/ 35, 2
2 35, 2, 2
1 35, 2, 2, 1
+ 35, 2, 3
- 35, -1
* -35
b. [5 minutes] Specify the algorithm for evaluating a general postfix expression
For token c in the expression:
If c is an operator:
Pop the top 2 elements from the stack
Apply the operator to them
Push the result back onto the stack
Else:
Push c onto the stack
3. [3 minutes] Is it possible for a postfix expression to end in an operand? Prefix? Infix?
Postfix: only if the expression is just 1 operand, prefix: yes (must), infix: yes (must)
4. [15 minutes] Write java code for matching html tags.
Example:
<html>
<body>
</body>
</html>
public boolean
validHTML(String s){
StringTokenizer st = new StringTokenizer(s,’<’);
Stack stack=new Stack();
String tag;
while(st.hasMoreTokens()){
tag=
st.nextToken();
if(tag.charAt(0)==’/’)
//closing
tag
{
if(!tag.substring(1,tag.length()).equals((String)stack.peek()){
return false; //it does not
match.
}
else{
stack.pop();
//match
found, remove from stack
}
}
else{
stack.push(tag);
}
}
return true;
}
5. [15 minutes] Write a non-recursive function that takes a singly linked list (with head and tail references, so you have addLeft(), addRight(), removeLeft(), removeRight(), etc.) as input, and uses a stack to reverse the list while removing all odd numbers. Write it twice, with the odd number removal in 2 different places. Both should run in linear time.
public void reverse(LinkedList a){
Stack s = new Stack();
while (!a.empty())
if (a.getRight() % 2 != 1) //or == 0
s.push(a.removeRight());
else
a.removeRight();
while (!s.empty())
a.addRight(s.pop());
}
public void reverse(LinkedList a){
Stack s = new Stack();
while (!a.empty())
s.push(a.removeRight());
while (!s.empty())
if (s.peek() % 2 != 1) //or == 0
a.addRight(s.pop());
else
s.pop();
}