Index of /~jrs/61bf98/lectures/21
CS61b: Lecture 21
Monday, October 12
STACKS AND QUEUES
=================
Stack Application: Expression Parsing
--------------------------------------
Arithmetic expressions can be written in prefix, infix, or postfix. Infix is
the usual way of writing expressions that we're all familiar with: 3 + 4 * 7.
You're also familiar with prefix from Homework 5 and from Scheme; the same
expression is written + 3 * 4 7. In postfix, it's written 3 4 7 * +.
In postfix, we write an operator after its operands: 4 7 *. Each operand may
itself be any postfix expression. Hence, 1 2 + 3 4 + * is an expression whose
operands are 1 2 + and 3 4 +; we might parenthesize it (1 2 +) (3 4 +) *.
However, unlike in infix, parentheses are never necessary.
A postfix expression is easily evaluated by maintaining a stack of numbers.
We read a postfix expression from left to right. When we encounter a number,
we push it onto the stack. When we encounter an operator, we pop the top two
numbers off the stack, perform the operation on them (using the first number
popped as the _second_ operand), and push the result onto the stack.
| | | | | | |5| | | | | | | |5| | | | |
| | --> | | --> |7| --> |7| --> |2| --> | | --> |8| --> |8| --> |3| --> | |
| | 2 |2| 7 |2| 5 |2| - |2| * |4| 8 |2| 5 |2| - |2| * |6|
--- --- --- --- --- --- --- --- --- ---
Here's code that performs one such operation. Shortly, we'll use this method
as a subroutine in an expression evaluator. For reasons that will be explained
presently, assume that the operator is initially on a stack of its own.
NOTE: For brevity, the division operator and all error checking are omitted.
public class ParseInfix {
public static void operate(Stack numStack, Stack opStack) throws Underflow {
// Retrieve the operator and operands from the stacks.
char operator = ((Character) opStack.top()).charValue();
opStack.pop();
int operand2 = ((Integer) numStack.top()).intValue();
numStack.pop();
int operand1 = ((Integer) numStack.top()).intValue();
numStack.pop();
System.out.print(operator + " ");
// Perform the operation and push the result on the number stack.
if (operator == '+') { // Addition
numStack.push(new Integer(operand1 + operand2));
} else if (operator == '-') { // Subtraction
numStack.push(new Integer(operand1 - operand2));
} else if (operator == '*') { // Multiplication
numStack.push(new Integer(operand1 * operand2));
} else if (operator == '^') { // Exponentiation
int result = 1;
for (int i = 0; i < operand2; i++) {
result = result * operand1;
}
numStack.push(new Integer(result));
}
}
Infix expressions are more difficult to evaluate than postfix expressions,
largely because of precedence rules. Exponentiation (^) has precedence over
multiplication (*) and division (/), which have precendence over addition (+)
and subtraction (-). Another complication is that, if two operators have the
same precedence, they may be left-associative or right-associative. Addition,
subtraction, multiplication, and division are left-associateive: 2 - 3 - 5 =
(2 - 3) - 5. Exponentiation is right-associative: 2 ^ 3 ^ 5 = 2 ^ (3 ^ 5).
We can convert infix to postfix with a simple algorithm that uses a stack to
hold operators. The algorithm reads an expression from left to right. When
we encounter a number, we immediately print it out. When we encounter an
operator, we put it on a stack until an operator of lower or equal precedence
appears (in the case of exponentiation, only if it's lower), whereupon we pop
it and print it. Why does this work? Consider two cases:
- Suppose the newest operator has lower precedence; e.g., the string so far
is "3 * 2 +". The operands of "*" are "3" and "2" regardless of what comes
after the "+", so we write out the string "3 2 *".
- Suppose the newest operator has higher precedence; e.g., the string so far
is "3 + 2 *". "3" is one of the operands of "+", and the other operand
begins with "2 *", but is incomplete. We keep the "+" on the stack until
its second operand is complete.
Upon reaching the expression's end, we pop and print each remaining operator.
Here's how we convert infix "3 * 5 + 4 ^ 5 ^ 6" to postfix "3 5 * 4 5 6 ^ ^ +":
| | | | | | | | | | | | | | | | |^| |^|
| | --> | | --> | | --> | | --> | | --> | | --> |^| --> |^| --> |^| --> |^|
| | 3 | | * |*| 5 |*| + |+| 4 |+| ^ |+| 5 |+| ^ |+| 6 |+|
--- --- --- --- --- --- --- --- --- ---
Output: 3 5 * 4 5 6 ^^+
Weiss provides some ridiculously complicated code for evaluating a postfix
expression, and also for converting infix to postfix. Below, I've combined
the two chores in a method that evaluates an infix expression, and prints
both the corresponding postfix expression and the computed result. The
algorithm uses two stacks: one for numbers, and one for operators. Unlike
Weiss, I've pared the implementation down to essentials. (However, this code's
shocking neglect of error checking is not a good model for your own efforts.
The reading of input is also poor; only one-digit numbers can be input.)
public class ParseInfix {
public static void main(String[] args) throws Underflow {
StackLi numStack = new StackLi(); // Create a number stack
StackLi opStack = new StackLi(); // Create an operand stack
// Process each character of the first command-line argument.
for (int i = 0; i < args[0].length(); i++) {
char c = args[0].charAt(i);
if (Character.isDigit(c)) {
// Print each digit; push each digit on number stack.
System.out.print(c + " ");
numStack.push(new Integer(Character.digit(c, 36)));
} else if ((c == '+') || (c == '-') || (c == '*') || (c == '^')) {
// Before pushing an operator onto the operand stack, check if
// operators currently atop the stack have greater precedence.
while (!opStack.isEmpty() && (c != '^') &&
(precedence(((Character) opStack.top()).charValue()) >=
precedence(c))) {
// Perform the operation atop the operand stack.
operate(numStack, opStack);
}
opStack.push(new Character(c)); // Push new operation on operand stack
}
}
while (!opStack.isEmpty()) {
operate(numStack, opStack);
}
System.out.println(" result:" + ((Integer) numStack.top()).intValue());
}
}
The algorithm requires us to assign each operator a number that indicates its
relative precedence. We could easily add more operators later.
public static int precedence(char operator) {
switch (operator) {
case '^': return 3;
case '*': case '/': return 2;
case '+': case '-': return 1;
default: return 0;
}
}
Stack implementation
--------------------
class ListNode {
Object element;
ListNode next;
ListNode(Object theElement, ListNode n) {
element = theElement;
next = n;
}
}
public class StackLi implements Stack {
private ListNode topOfStack;
public StackLi() { topOfStack = null; }
public void push(Object x) { topOfStack = new ListNode(x, topOfStack); }
public void pop() throws Underflow {
if (isEmpty()) {
throw new Underflow("Stack pop");
}
topOfStack = topOfStack.next;
}
public Object top() throws Underflow {
if (isEmpty())
throw new Underflow("Stack top");
return topOfStack.element;
}
public Object topAndPop() throws Underflow {
if (isEmpty()) {
throw new Underflow("Stack topAndPop");
}
Object topItem = topOfStack.element;
topOfStack = topOfStack.next;
return topItem;
}
public boolean isEmpty() { return topOfStack == null; }
public void makeEmpty() { topOfStack = null; }
}
This list-based stack implementation (taken from pages 423-424 of Weiss) is
easy, given our thorough familiarity with lists. Note that StackLi.topOfStack
is declared "private", and the fields of ListNode (element and next) are
declared package (by default), so the data structure is properly encapsulated.
All operations take O(1) time. Weiss also gives an array-based implementation,
which is worth understanding.
Queue implementation
--------------------
Weiss' list-based queue implementation (pages 425-427) is nearly as simple as
the stack implementation. It's worth noting that pointers are maintained to
both the front and back of the queue, so that all operations can be performed
in O(1) time. This makes enqueue() slightly trickier than push().
Weiss also gives an array-based implementation.
public class QueueLi implements Queue {
private ListNode front;
private ListNode back;
public QueueLi() { makeEmpty(); }
public void enqueue(Object x) {
if (isEmpty()) {
back = front = new ListNode(x);
} else {
back = back.next = new ListNode(x);
}
}
public Object getFront() throws Underflow {
if (isEmpty()) {
throw new Underflow("QueueLi getFront");
}
return front.element;
}
public Object dequeue() throws Underflow {
if (isEmpty()) {
throw new Underflow("QueueLi dequeue");
}
Object returnValue = front.element;
front = front.next;
return returnValue;
}
public boolean isEmpty() { return front == null; }
public void makeEmpty() {
front = null;
back = null;
}
}