ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Stack: applications
by
Marcel Turcotte
Version February 12, 2020
Preamble
Preamble
Overview
Overview
Stack: applications
We look at several examples of the use of stacks, including evaluating arithmetic
expressions, saving command history, and running Java programs.
General objective :
This week you will be able to apply the stacks for algorithm design.
1 39
Preamble
Learning objectives
Learning objectives
Justify the role of a stack in solving a computer problem.
Design a computer program requiring the use of a stack.
Readings:
Pages 159-176 of E. Koffman and P. Wolfgang.
2 39
Preamble
Plan
Plan
1 Preamble
2 Applications
3 Prologue
3 39
Applications
Applications
Evaluating an arithmetic expression
Application : Evaluating an arithmetic
expression
Architecture of our application
Clear separation of concerns: lexical analysis and
syntactic analysis
Lexical analysis takes a string of characters as
input and cuts it into chunks called tokens.
Input: ·1 ·+ · ·2× 33 · · · −4·
Output: [1, +, 2,×, 33,−, 4]
Our syntax analysis takes a sequence of tokens as
input and returns the value of the expression.
Input: [1, +, 2,×, 33,−, 4]
Output: 63
Lexical analysis
Syntax analysis
Arithmetic expression
List of tokens
Value
5 39
StringTokenizer
Java has a lexical analyzer!
S t r i n g T o k e n i z e r s t ;
s t = new S t r i n g T o k e n i z e r ( ” 1 + 2 ∗ 33 − 4″ ) ;
whi le ( s t . hasMoreTokens ( ) ) {
System . out . p r i n t l n ( s t . nextToken ( ) ) ;
}
1
+
2
*
33
–
4
StreamTokenizer is more versatile!
6 39
Scan
Please take a few minutes to analyze this example. What do you think?
pub l i c s t a t i c i n t scan ( S t r i n g e x p r e s s i o n ) {
S t r i n g T o k e n i z e r s t ; S t r i n g op ; i n t l , r ;
s t = new S t r i n g T o k e n i z e r ( e x p r e s s i o n ) ;
l = I n t e g e r . p a r s e I n t ( s t . nextToken ( ) ) ;
whi le ( s t . hasMoreTokens ( ) ) {
op = s t . nextToken ( ) ;
r = I n t e g e r . p a r s e I n t ( s t . nextToken ( ) ) ;
l = e v a l ( l , op , r ) ;
}
re tu rn l ;
}
7 39
p r i v a t e s t a t i c i n t e v a l ( i n t l , S t r i n g op , i n t r ) {
i n t r e s u l t ;
switch ( op ) {
case “+” :
r e s u l t = l + r ;
break ;
case “−” :
r e s u l t = l − r ;
break ;
case “/” :
r e s u l t = l / r ;
break ;
case “∗” :
r e s u l t = l ∗ r ;
break ;
de f au l t :
System . e x i t ( −1);
}
re tu rn r e s u l t ;
}
Exercises
What does scan(“3 * 12 + 4”) return?
What does scan(“3 + 12 * 4”) return?
What do you think?
9 39
Discussion
The scan algorithm evaluates operations from left to right, regardless of the priority
of the operations. Scan doesn’t process the parentheses.
There are two solutions:
Use a new representation for the expressions
Use a more complex algorithm
⇒ Both of these solutions require the use, implicit or explicit, of a stack!
10 39
Representations. There are three ways to represent an expression: l � r , where � is an
operator.
infix: The infix notation corresponds to the usual notation, the operator is
sandwiched between its operands: l � r .
post-fixed: In post-fixed notation, the operands are placed in front of the operator,
l r �. This notation is also called Reverse Polish Notation or RPN, it is
the notation used by some scientific calculators (such as HP-35 from
Hewlett-Packard or Texas Instruments TI-89 using RPN Interface by Lars
Frederiksen∗) and the languages PostScript and PDF.
7− (3− 2)→ 7 3 2 − −
(7− 3)− 2→ 7 3 − 2 −
pre-fixed The third notation is to place the operator first followed by its operands,
� l r . The programming language Lisp uses a combination of parentheses
and prefix notation, (- 7 (* 3 2)).
∗www.calculator.org/rpn.html
http://http://www.calculator.org/rpn.html
From infix to postfix
Successively transform, one by one, each subexpression following the normal order
of evaluation of an infixed expression.
An infixed subexpression l � r becomes l r �,
where l and r are themselves subexpressions and � is an operator.
12 39
Evaluating a postfixed expression
(mentally)
Until the end of the expression is reached:
1. Read from left to right up to the first operator;
2. Apply the operator to the (2) operands preceding it.;
3. Replace the operator and its (2) operands by the result.
When the end of the expression is reached, we have the result.
14 39
Evaluating a postfix expression
(mentally)
A few exercises:
9 3 / 10 2 3 ∗ − +
9 2 4 ∗ 5 − /
15 39
9 3 / 10 2 3 ∗ − +
9 2 4 ∗ 5 − /
Remarks
The order of the operands is the same for the two notations, postfix and infix, however
the places where the operators are inserted differ.
2 + (3 ∗ 4)→ 2 3 4 ∗ +
(2 + 3) ∗ 4→ 2 3 + 4 ∗
To evaluate an infixed expression, the operator priority as well as the parentheses must
be taken into account.
In the case of postfix notation, these concepts are represented within the
notation.
18 39
9 3 / 10 2 3 ∗ − +
9 2 4 ∗ 5 − /
Exercises
Give the content of the stack for each iteration of the algorithm. :
9 3 / 10 2 3 ∗ − +
9 2 4 ∗ 5 − /
Modify the algorithm so that it constructs an expression infix from an expression
postfix given as input.
22 39
Applications
Discussion on the usefulness of abstract data types
Discussion
Now please answer the question asked earlier: “One of the proposed implementations
uses an array, why don’t we just use an array for algorithm design? What are the
advantages? ”
23 39
Applications
Memory management
Application : Memory management
during program execution
Memory representation and
program interpretation
…
basePtr
Variables
method calls
Program counter
Method n
activation record
Method 2
activation record
Method 1 (main)
activation record
Local variables
Parameters
Return address
Previous
basePtr
Return value
heap
(instances)
Stack for
static
program
(byte code)
Java Virtual
Machine
free
25 39
When a method is called
The Java Virtual Machine (JVM) must:
1. Create a new activation frame [working memory] (the return value, previous basePtr
value and the return address have a fixed size, the size of local variables and
parameters depends on the method);
2. Save the current value of basePtr, in the space “previous value of basePtr”, point
basePtr to the base of the current block;
3. Save the value of locationCounter in the space designated by “return address”, make
locationCounter point to the first instruction of the called method;
4. Copy the actual parameter values in the region designated by “parameter”;
5. Initialize the textbflocal variables;
6. Start execution at the instruction pointed to by locationCounter.
26 39
When the execution of a method ends
1. The method saves the return value at the location indicated by “return value”.;
2. Returns control to the calling method, i.e., resets the locationCounter and basePtr
values;
3. Removes the current activation block;
4. Resumes execution at the location designated by locationCounter.
27 39
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
1
1
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
v
m
n
b:
b(2)
2
1
1
2
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
v
m
n
b:
b(2)
v
n
c:
c(3)
3
2
1
1
2
3
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
v
m
n
b:
b(2)
c(3)4
2
1
1
2
3
4
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
b(2)
1
1
2
4
4
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
a(1)
1
4
4
pub l i c s t a t i c i n t c ( i n t v ) {
i n t n ;
n = v + 1 ;
re tu rn n ;
}
pub l i c s t a t i c i n t b ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = c (m) ;
re tu rn n ;
}
pub l i c s t a t i c i n t a ( i n t v ) {
i n t m, n ;
m = v + 1 ;
n = b (m) ;
re tu rn n ;
}
pub l i c s t a t i c vo id main ( S t r i n g [ ] p ) {
i n t m = 1 , n ;
n = a (m) ;
System . out . p r i n t l n ( n ) ;
}
args
m
n
main:
v
m
n
a:
a(1)
v
m
n
b:
b(2)
v
n
c:
c(3)
3
4
4
2
1
1
2
3
4
4
4
4
4
Prologue
Summary
A a stack is used when one wishes to process the elements in reverse order.
36 39
Next module
Stack : linked elements
37 39
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
38 39
Marcel Turcotte
Marcel.
School of Electrical Engineering and Computer Science (EECS)
University of Ottawa
39 / 39
Marcel.
Preamble
Overview
Learning objectives
Plan
Applications
Evaluating an arithmetic expression
Discussion on the usefulness of abstract data types
Memory management
Prologue