Lecture 7

Data Structures and Algorithms

Stacks
Stacks

 Definition
 A stack is a container of objects that are
inserted and removed according to the last-
in-first-out principle.
 A stack allows access to only one data item:
the last item inserted. If you remove this
item, then you can access the next-to-last
item inserted, and so on. This is a useful
capability in many programming situations.

Stacks 2
Operations on Stack
 Placing a data item on the top of the
stack is called pushing it.
 Removing it from the top of the
stack is called popping it. These are
the primary stack operations.
 A stack is said to be a Last-In-
First-Out (LIFO) storage
mechanism, because the last item
inserted is the first one to be
removed.
 Examples
 “back” in a web browser
 “undo” in Text editors

Stacks 3
Pop
Procedure 7.1 : PUSH(STACK, TOP, LEN, ITEM)
This procedure pushes an ITEM onto a stack.

1 If TOP = LEN, then:

Print: Stack is Full, and Return. [Stack already filled ?]
2 Set TOP := TOP+1. [Increases TOP by 1.]
3 Set STACK[TOP] := ITEM. [Insert ITEM in new TOP position.]
4 Return.

Stacks 4
POP
Procedure 7.2 : POP(STACK, TOP, ITEM)
This procedure deletes the top element of STACK
and assignees it to the variable ITEM.

1 [ If Stack has no item to removed?]

If TOP = 0, than:
Print: Stack is Empty, and Return.
2 Set ITEM:= STACK[TOP]. [Assigns TOP element to ITEM.]
3 Set TOP := TOP-1. [Decreases TOP by 1.]
4 Return.

Stacks 5
Peek
 Push and pop are the two primary stack operations. However, it's
sometimes useful to be able to read the value from the top of the
stack without removing it.
 Notice that you can only peek at the top item. By design, all the
other items are invisible to the stack user.

Procedure 7.3 : PEEK(STACK, TOP, ITEM)

This procedure returns the top element of STACK wit out
removing and assignees it to the variable ITEM.

1 [ If Stack is Empty?]
If TOP = 0, than:
Print: Stack is Empty, and Return.
2 Set ITEM:= STACK[TOP]. [Assigns TOP element to ITEM.]
3 Return.

Stacks 6
Reversing a Word
 For our first example of using a stack, we'll
examine a very simple task: reversing a word.
When you run the program, it asks you to type
in a word. When you press Enter, it displays
the word with the letters in reverse order.
 A stack is used to reverse the letters. First the
characters are extracted one by one from the
input string and pushed onto the stack. Then
they're popped off the stack and displayed.
Because of its last-in-first-out characteristic,
the stack reverses the order of the characters.

Stacks 7
Algorithm for Reversing a Word
Procedure 7.3: REVERSWORD(INPUT, N, STACK, OUTPUT)
The Algorithm reverse a string INPUT of Length N
using a stack STACK and save the reverse
word in string OUTPUT.

Step 1 : Repeat for J=1 to N :

(a) push char INPUT[J] to STACK.
Step 2: Set K:=1;
Step 3 : Repeat Step 4 and 5 while STACK is not empty:
Step 4 : pop from STACK and store at OUPUT[K].
Step 5: K := K+1.
Step 5 : Return.

Stacks 8
Java Code for Reversing a Word (1)
class Reverse
{
private String input;

public Reverse(String input)

{
this.input = new String(input);
}

public String doReverse()

{
Stack stk = new Stack(input.length());
for(int i = 0; i<input.length(); i++)
{
stk.push(input.charAt(i));
}

Stacks 9
Java Code for Reversing a Word (2)
String output= new String("");
int k=0;
while(!stk.isEmpty())
{
output+= stk.pop();
k++;
}
return output;
}
}
//===============================
class TestReverse
{
public static void main(String args[])
{
String input = new String("abcdefg");
Reverse revString = new Reverse(input);
String output= new String(revString.doReverse());
System.out.println(output);
}
}

Stacks 10
Parsing Arithmetic Expressions
 Another very important application of
stack is parsing (that is, analyzing)
arithmetic expressions like
2+3
or
2*(3+4)
or
((2+4)*7)+3*(9–5)

Stacks 11
Parsing Arithmetic Expressions
 As it turns out, it's fairly difficult, at least for a computer algorithm,
to evaluate an arithmetic expression directly. It's easier for the
algorithm to use a two-step process:
1. Transform the arithmetic expression into a different format, called
postfix notation.
2. Evaluate the postfix expression.

 Step 1 is a bit involved, but step 2 is easy. In any case, this two-
step approach results in a simpler algorithm than trying to parse
the arithmetic expression directly.
 Of course, for a human it's easier to parse the ordinary arithmetic
expression. We'll return to the difference between the human and
computer approaches in a moment. Before we delve into the
details of steps 1 and 2, we'll introduce postfix notation.

Stacks 12
Infix Notation
 Everyday arithmetic expressions are written with an
operator ( +, –, *, or / ) placed between two operands
(numbers, or symbols that stand for numbers). This is
called infix notation, because the operator is written
inside the operands.
 For Example
A+B C-D E*F G/H
 In Infix Notation we must distinguish between
(A+B)*C and A+(B*C)
 The order of the operators and operands in arithmetic
expression doesn't uniquely determine the order in which
the operations are to be performed but by using
parenthesis and operator-precedence level we
determine the order evaluation.

Stacks 13
Polish Notation (Prefix Notation)
 Polish notation (Infix notation) named after the polish
mathematician Jan Jukasiewicz, refers to the notation
in which the operator symbol is placed before its two
operands.
 For Example
+AB -CD *EF /GH
 The Fundamental Property of Polish notation is that
the order in which the operations are to be performed
is completely determined bye the positions of the
operators and operands in expression. Accordingly we
never need parenthesis when writing expression in
Polish notation

Stacks 14
Reverse Polish Notation (Postfix Notation)

 In postfix notation (which is also called

Reverse Polish Notation, or RPN, the
operator follows the two operands.
 For Example
AB+ CD- EF* GH/

Stacks 15
Infix and postfix expressions
Infix Postfix
A+B–C AB+C–
A*B/C AB*C/
A+B*C ABC*+
A*B+C AB*C+
A*(B+C) ABC+*
A*B+C*D AB*CD*+
(A+B)*(C–D) AB+CD–*
((A+B)*C)–D AB+C*D–

Stacks 16
How Humans Evaluate Infix
 How do you translate infix to postfix?
 Let's examine a slightly easier question first:
“how does a human evaluate a normal infix
expression”?
 Although, this is difficult for a computer, we
humans do it fairly easily because of countless
hours in Dr.Nawaz's math class. It's not hard
for us to find the answer to 3+4+5, or 3*(4+5).
 By analyzing how we do this, we can achieve
some insight into the translation of such
expressions into postfix.

Stacks 17
How Humans Evaluate Infix
 Roughly speaking, when you "solve" an arithmetic
expression, you follow rules something like this:
1. You read from left to right. (At least we'll assume
this is true. Sometimes people skip ahead, but for
purposes of this discussion, you should assume
you must read methodically, starting at the left.)
2. When you've read enough to evaluate two
operands and an operator, you do the calculation
and substitute the answer for these two operands
and operator. (You may also need to solve other
pending operations on the left, as we'll see later.)
3. This process is continued—going from left to right
and evaluating when possible— until the end of the
expression.

Stacks 18
How Computer Evaluate Infix ?

 The Computer usually evaluates an arithmetic

expression written in infix notation in two steps
 First, it converts the expression to postfix notation,
and
 then it evaluates the postfix expression.
 In each step the stack is the main tool that is
used to accomplish the given task.
 First we illustrate the second step that how
stacks are used to evaluate postfix
expressions and then we see how stacks are
used to transform infix expressions into postfix
expressions.

Stacks 19
Evaluating a postfix expression

 We can use the following two rules shown in evaluate

postfix expressions.
Item Read from Postfix Expression Action

Operand Push it onto the stack.

Operator Pop the top two operands
from the stack, and apply
the operator to them.
Push the result into the stack.

 When you're finished, pop the stack to obtain the answer. That's all
there is to it.
 This process is the computer equivalent of the human approach.

Stacks 20
Evaluation of Postfix Expression
 Algorithms 7.4 This algorithm finds the VALUE of an
arithmetic expression P Written in Postfix notation using a
stack STACK to hold the operands.

1. Add a right parenthesis “)” at the end of P. [this acts as a sentinel.]

2. Scan P from left to right and repeat step 3 and 4 for each element of P
until the sentinel “)” is encountered.
3. If an operand is encountered push it on the STACK
4. If an operator  is encountered, then :
(a) Remove the two top elements of STACK, where A
is the top element and B is the next-to top element.
(b) Set ANS := B  A
(C) Push ANS back to STACK
5. Set VALUE equal to the top element on STACK.
6. Exit

Stacks 21
How Humans Translate Infix to Postfix

 To translate infix to postfix notation, you follow a

similar set of rules to those for evaluating infix.
However, there are a few small changes. You don't do
any arithmetic.
 The idea is not to evaluate the infix expression, but to
rearrange the operators and operands into a different
format: postfix notation. The resulting postfix
expression will be evaluated later.
 As before, you read the infix from left to right, looking
at each character in turn. As you go along, you copy
these operands and operators to the postfix output
string. The trick is knowing when to copy what.

Stacks 22
How Humans Translate Infix to Postfix (2)

 If the character in the infix string is an operand, you

copy it immediately to the postfix string. That is, if you
see an A in the infix, you write an A to the postfix.
There's never any delay: you copy the operands as
you get to them, no matter how long you must wait to
copy their associated operators.
 Knowing when to copy an operator is more
complicated, but it's the same as the rule for
evaluating infix expressions. Whenever you could
have used the operator to evaluate part of the infix
expression (if you were evaluating instead of
translating to postfix), you instead copy it to the postfix
string.

Stacks 23
Translating A+B–C into postfix

Character Read Postfix

Infix Expression
from Infix Expression Comments
parsed so Far
Expression Written So Far
A A A
+ A+ A
B A+B AB
– A+B– AB+ When you see the –,
you can copy the +
to the postfix string.
C A+B–C AB+C
End A+B–C AB+C– When you reach the
end of the expression,
you can copy the –.

Stacks 24
Translating A+B*C to postfix
Character Read Infix Expression Postfix Expression Comments
from Parsed So Far Written So Far
Infix Expression
A A A
+ A+ A
B A+B AB
* A+B* AB Can't copy the +,
because * is higher
precedence than +.
C A+B*C ABC When you see the C, you
can copy the *.
A+B*C ABC*
End A+B*C ABC*+ When you see the end of
the expression, you can
copy the +.

Stacks 25
Translating A*(B+C) into postfix

Character Read from Infix Expression Postfix Expression Comments

Infix Expression Parsed So Far Written So Far
A A A
* A* A
( A*( A
B A*(B AB Can't copy * because of
parenthesis.
+ A*(B+ AB
C A*(B+C ABC Can't copy the + yet.
) A*(B+C) ABC+ When you see the ) you
Can copy the +.
A*(B+C) ABC+* When you've copied the
+, you can copy the*.
End A*(B+C) ABC+* Nothing left to copy

Stacks 26
Saving Operators on a Stack
 You'll notice in both examples demonstrated in last
slides that the order of the operators is reversed
going from infix to postfix. Because the first
operator can't be copied to the output until the
second one has been copied, the operators were
output to the postfix string in the opposite order
they were read from the infix string. A longer
example may make this clearer.
 Next example shows the translation to postfix of
the infix expression A+B*(C–D). We include a
column for stack contents, which we'll explain in a
moment.

Stacks 27
Translating A+B*(C–D) to postfix

Character Read from Infix Expression Postfix Expression Stack Contents

Infix Expression Parsed So Far Written So Far
A A A
+ A+ A +
B A+B AB +
* A+B* AB +*
( A+B*( AB +*(
C A+B*(C ABC +*(
– A+B*(C– ABC +*(–
D A+B*(C–D ABCD +*(–
) A+B*(C–D) ABCD– +*(
A+B*(C–D) ABCD– +*(
A+B*(C–D) ABCD– +*
A+B*(C–D) ABCD–* +
A+B*(C–D) ABCD–*+

Stacks 28
Translation Rules
 Let's make the rules for infix-to-postfix
translation more explicit. You read items from
the infix input string and take the actions
shown in previous slides.
 These actions are described in pseudo-code,
a blend of Java and English.
 In this table, the < and >= symbols refer to the
operator precedence relationship, not
numerical values. The opThis operator has
just been read from the infix input, while the
opTop operator has just been popped off the
stack.

Stacks 29
Translation rules
Item Read from Input(Infix) Action
Operand Write it to output (postfix)
Open parenthesis ( Push it on stack
Close parenthesis ) While stack not empty, repeat the following:
Pop an item,
If item is not (, write it to output
Quit loop if item is (
Operator (opThis) If stack empty,
Push opThis
Otherwise,
While stack not empty, repeat:
Pop an item,
If item is (, push it, or
If item is an operator (opTop), and
If opTop < opThis, push opTop, or
If opTop >= opThis, output opTop
Quit loop if opTop < opThis or item is (
Push opThis

No more items While stack not empty,

Pop item, output it.

Stacks 30
Translating Infix Expressions (1)
Algorithm 7.5: POLISH(Q,P)
Suppose Q is an arithmetic expression written in infix notation.
This algorithm finds the equivalent postfix expression P.

1. Push “(“ onto STACK, and add “)” to the end of Q.

2. Scan Q from left to right and repeat Step3 to 6 for each element of Q until
the STACK is empty.
3. If an operand is encountered, add it to P.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator  is encountered, then:
(a) Repeatedly pop from STACK and add to P each
operator ( on the top of the STACK) which has the
same precedence as or higher precedence than .
(b) Add  to STACK.
[End of if Structure]

Stacks 31
Translating Infix Expressions (2)
6. If a right parenthesis is encountered, than:
(a) Repeatedly pop from STACK and add to P each
operator ( on the top of STACK ) until a left parenthesis is
encountered.
(b) Remove the left parenthesis. [Do not the left parenthesis to P.]
[End of If structure.]
[End of Step 2 loop.]
7. Exit.

Stacks 32
The End