Stack: collection of items stored in insertion order such that items can be inserted or removed only at one designated end (the top). Implements LIFO.

Liken to spring-loaded device that holds cafeteria trays.

Textbook ObjectStack class is focus. See author's documentation at

http://www.cs.colorado.edu/~main/docs/edu.colorado.collections.ObjectStack.html

Author also provides a family of stack classes, one for each primitive type. As an example, see author's documentation for IntStack class at

http://www.cs.colorado.edu/~main/docs/edu.colorado.collections.IntStack.html

Author provides separate classes for array and linked-list implementation. The linked list implementations are named by replacing "...Stack" in class name with "...LinkedStack".

Java provides a class for stack of Objects: java.util.Stack. See Sun's documentation at http://java.sun.com/products/jdk/1.3/docs/api/java/util/Stack.html. This Stack class is implemented using a Vector.

Stacks are used extensively by compilers, interpreters, source code analyzers, etc.

Parentheses are broadly defined as (, ), [, ], {, and }. However each can match another only of its own kind.

To be balanced:

- each left paren must be followed eventually by a matching right paren

- every subexpression within matching parentheses must itself be balanced.

(note recursive definition)

For example:

[ ( ) ] is balanced

[ ( ] ) is not balanced

subexpressions can be nested arbitrarily deeply.

[ { } ( ) { [ [ [ ] ( ) ] ] } ] is balanced

The static boolean isBalanced method demonstrates how a stack is utilized to determine balance.

Basic algorithm is this:

1. Loop iterates over each character in expression until unbalance detected or end of expression reached.
2. For each character:
   - If left paren of any type, push onto stack.
   - If right paren, then if stack empty or if popped item is not of same type, then is unbalanced.
   - Ignore all other characters
3. After exiting loop, return true if unbalance not detected AND stack is empty. Otherwise false.

See source code at http://eccentric.smsu.edu/download/CSC132/001/chap6/IsBalancedDemonstration.java

Program to read arithmetic expression from keyboard, evaluate it, and output its value. For this example, assume expression is fully parenthesized.

Think about how you would use stacks to implement this.

Evaluate this one by hand: ( ( 3 * 2 ) + 8 )

Evaluate this one by hand: ( ( 7 + 4 ) * ( 9 - ( ( 6 - 3 ) / 3 ) ) )

In what order did you evaluate subexpressions?

Probable reduction:

( ( 7 + 4 ) * ( 9 - ( ( 6 - 3 ) / 3 ) ) )

( 11 * ( 9 - ( ( 6 - 3 ) / 3 ) ) )

( 11 * ( 9 - ( 3 / 3 ) ) )

( 11 * ( 9 - 1 ) )

( 11 * 8 )

At each line of this reduction, observe the position of the first ")" and relate that to the subexpression evaluated at that step.

One possible solution is "zig-zag" scan. (I call it zig-zag due to step 2)

Repeat until no parentheses remain:

1. scan until first ")" is seen,
2. back up to closest previous "(",
3. evaluate what's between them,
4. replace that subexpression, including "(" and ")" with the evaluation

Note what is happening.

Each time scan encounters ")" an action occurs. What action? The closest previous operator is applied to the two closest previous operands. Sounds like a LIFO operation!

How could stacks be used to do this in one continuous scan?

Assume that the only things that appear in the scan are numbers (consider whole numbers not individual digits) and the characters '+', '-', '*', '/', '(', ')'.

Answer these four questions and you've got it licked. Hint: you need two stacks.

1. What do you do when you scan a number?
2. What do you do when you scan a '+', '-', '*', or '/'?
3. What do you do when you scan a '('?
4. What do you do when you scan a ')'?
5. What should the stacks contain at the end of the scan?

Textbook solution available at http://www.cs.colorado.edu/~main/applications/BasicCalc.java.

The textbook solution uses EasyReader to read and scan input one character at a time. We will consider an alternative method for reading and parsing the expression.

A token is an item of interest to a language, e.g. a word, number or symbol. An input stream (or string) can be partitioned into tokens for processing. All compilers and interpreters do this.

For example the line: sum = value + 6;

is scanned in by javac and converted to the token stream:

<id_token> <assign_token> <id_token> <plus_token> <int_token> <semicolon_token>

Java provides two "tokenizer" classes. Java documentation on StringTokenizer class

http://java.sun.com/j2se/1.3/docs/api/java/util/StringTokenizer.html

To use this, simply read the input line into a String, create a StringTokenizer for that string (a tokenizer is similar to an iterator). Each call to "nextToken()" will return the next token in a String. Continue until "hasMoreTokens()" returns false.

For StringTokenizer to work properly, it needs to know which symbols serve as "delimiters" (e.g. separate tokens from each other). By default, several are used: ' ' (space), '\n' (newline), '\t' (tab) and a couple others. There is also a second constructor which allow you to specify delimiters.

For this case, we'll go with the default, recognizing that the tokens in the expression will need to be separated by one or more spaces.

You can use EasyReader's "stringInputLine()" method to get a String containing one line of keyboard input. That string is then used as parameter to StringTokenizer constructor. All this can be done in one line of code:

Infix arithmetic expression: (3 + 4) * 2

Postfix arithmetic expression: 3 4 + 2 *

Prefix arithmetic expression: * + 3 4 2

• The result of all three is the same, but pre- and postfix do not require the ( ).
• Prefix often called Polish Notation, developed by Lukasiewicz (lu-ka-SHA-vech)
• Postfix often called Reverse Polish Notation.

For each operator encountered in a left to right scan of the expression:

1. apply that operator to the two operands that immediately precede it.

2. replace all three items with the result.

When the scan of a valid expression is complete, only the final result remains.

Example:

3 4 + 2 * -- first operand is +, apply it to 3 and 4, replace all three with 7

7 2 * -- next operand is *, apply it to 7 and 2, replace all three with 14

14 -- scan is complete, only result remains.

What does this have to do with stacks? Check it out:

Create a stack called operand_stack.
For each token in a left-to-right scan of the expression
{
	if (current token is an operand)
	{
		operand_stack.push(token);
	}
	else //current token is an operator
	{
		second = operand_stack.pop( );
		first  = operand_stack.pop( );
		result = first  <operator>  second; // appropriate operator: +-*/
		operand_stack.push(result);
	}
}
final_result = operand_stack.pop( );

Example:

3 4 + 2 *

How would you augment algorithm to account for:

• too many operators? 3 4 + *
• too many operands? 3 4 5 *
• malformed expression? e.g. 3 4 - * 5 6 +

 Two part strategy:
1. use one stack to translate expression into postfix format,
2. second stack to evaluate postfix.

(alternative pseudocode in text page 316)

Create a stack called symbol_stack
For each token in a left-to-right scan of the expression
{
	if (current token is a left parenthesis)
		symbol_stack.push(token);
	else if (current token is an operand)
		append token to postfix expression
	else if (current token is an operator)
	{
		while (symbol_stack not empty AND 
 		symbol_stack.peek() is not a left parenthesis AND
 		token has lower or same precedence as symbol_stack.peek())
		{
			append symbol_stack.pop() to the postfix expression
		}
		symbol_stack.push(token);
	}
	else // current token is a right parenthesis
	{
		while (symbol_stack.peek() is not a left parenthesis)
		{
			append symbol_stack.pop() to the postfix expression
		}
		symbol_stack.pop();  // pop the left parenthesis
	}
}
while (symbol_stack not empty)
{
		append symbol_stack.pop() to the postfix expression
}

Resulting postfix expression can then be evaluated using the previous algorithm.

Example:

Observation: postfix evaluation can be imbedded into this algorithm

• for operand token, push the token onto the operand_stack, in addition to appending it to postfix string.
• for operator token or right parenthsis, each popped token is operator which can be then applied to top two operand_stack items, in addition to appending it to postfix string.

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )