Fundamentals of Stack Applications in Computer Science
CSCI 204: Data Structures &
Algorithms
Stack Applications
1
2
Stack Applications
Stack Applications
Many applications encountered in
computer science requires the use of a
stack.
Balanced delimiters
Postfix expressions
3
Balanced Delimiters
Many applications use delimiters to group
strings of text or simple data into
subparts.
mathematical expressions
programming languages
HTML markup
4
Source Code Example
Consider the following C source code:
int sum_list( int the_list[], int size )
{int sum = 0;
int i = 0;
while( i < size ) {sum += the_list[ i ];
i += 1;
}
return sum;
}
5
Source Code Example
The delimiters must be paired and balanced.
We can design and implement an algorithm to:
read a C source file, and
determine if the delimiters are properly
paired.
Valid C Source?
from
list_stack
import
Stack
def
is_validSource( srcfile ):
s = Stack()
for
line
in
srcfile :
for
token
in
line :
if
token
in
"{[(" :s.push( token )
elif
token
in
"}])" :
if
s.is_empty() :
return
False
else
:
left = s.pop()
if
(token == "}"
and
left != "{") or
\
(token == "]"
and
left != "[")
or
\
(token == ")"
and
left != "(") :return
False
return
s.is_empty()
stack_apps.py
Mathematical Expressions
We work with mathematical expressions on a
regular basis.
Easy to determine the order of evaluation.
Easy to calculate.
But the task is more difficult in computer
programs.
A program cannot visualize the expression to
determine the order of evaluation.
Must examine one token at a time.
Types of Expressions
Three different notations can be used:
infix:
A + B * C
Easy for humans, but challenge for program,
should we evaluate
A+B
first or
B*C
first?
prefix:
+ A * B C
postfix:
A B C * +
Very natural for program to handle
Infix to Postfix
Infix expressions can be easily converted by
hand to postfix notation.
1. Fully parenthesize the expression.
2. For each set of (), move operator to the
end of the closing parenthesis.
A * B + C / D
((A * B) + (C / D))
((A B *) (C D /) +)
Infix to Postfix (cont)
The expression at the end of step 2:
3. Remove all of the parentheses.
Which results in the postfix version.
((A B *) (C D /) +)
A B * C D / +
The implementation of infix2postfix.py is left as a part of the lab exercise.
Evaluating Postfix Expressions
We can evaluate a valid postfix expression using a
stack structure.
For each token:
1.
If the current token is an operand, push its value
onto the stack.
2.
If the current token is an operator:
1.
pop the top two operands off the stack.
2.
perform the operation (top value is RHS operand).
3.
push the result of the operation back on the stack.
The final result will be the last value on the stack.
Postfix Evaluation Examples
To illustrate the use of the algorithm, assume
the existence of an empty stack, and
the following variable assignments
Evaluate the valid expression:
A = 8 C = 3
B = 2 D = 4
A B C + * D /
Postfix Example #1
Postfix Example #2
What happens if the expression is
invalid?
A B * C D +
15
Postfix Example #3
What happens if there are too many
operators for the given number of
operands?
A B * + C /
Understanding the various applications of stacks in computer science is crucial for developing efficient algorithms. From balanced delimiters to postfix expressions, stacks play a key role in organizing and processing data efficiently. The provided examples demonstrate how stacks are utilized in source code analysis, mathematical expression evaluation, and conversion of infix to postfix notations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CSCI 204: Data Structures & Algorithms Stack Applications 1
Stack Applications Many applications encountered in computer science requires the use of a stack. Balanced delimiters Postfix expressions 2
Balanced Delimiters Many applications use delimiters to group strings of text or simple data into subparts. mathematical expressions programming languages HTML markup 3
Source Code Example Consider the following C source code: int sum_list( int the_list[], int size ) { int sum = 0; int i = 0; while( i < size ) { sum += the_list[ i ]; i += 1; } return sum; } 4
Source Code Example The delimiters must be paired and balanced. We can design and implement an algorithm to: read a C source file, and determine if the delimiters are properly paired. 5
Valid C Source? from list_stack import Stack def is_validSource( srcfile ): s = Stack() for line in srcfile : for token in line : if token in "{[(" : s.push( token ) elif token in "}])" : if s.is_empty() : return False else : left = s.pop() if (token == "}" and left != "{") or \ (token == "]" and left != "[") or \ (token == ")" and left != "(") : return False return s.is_empty() stack_apps.py
Mathematical Expressions We work with mathematical expressions on a regular basis. Easy to determine the order of evaluation. Easy to calculate. But the task is more difficult in computer programs. A program cannot visualize the expression to determine the order of evaluation. Must examine one token at a time.
Types of Expressions Three different notations can be used: infix: A + B * C Easy for humans, but challenge for program, should we evaluate A+B first or B*C first? prefix: + A * B C postfix: A B C * + Very natural for program to handle
Infix to Postfix Infix expressions can be easily converted by hand to postfix notation. A * B + C / D 1. Fully parenthesize the expression. ((A * B) + (C / D)) 2. For each set of (), move operator to the end of the closing parenthesis. ((A B *) (C D /) +)
Infix to Postfix (cont) The expression at the end of step 2: ((A B *) (C D /) +) 3. Remove all of the parentheses. A B * C D / + Which results in the postfix version. The implementation of infix2postfix.py is left as a part of the lab exercise.
Evaluating Postfix Expressions We can evaluate a valid postfix expression using a stack structure. For each token: 1. If the current token is an operand, push its value onto the stack. 2. If the current token is an operator: pop the top two operands off the stack. perform the operation (top value is RHS operand). push the result of the operation back on the stack. The final result will be the last value on the stack. 1. 2. 3.
Postfix Evaluation Examples To illustrate the use of the algorithm, assume the existence of an empty stack, and the following variable assignments A = 8 C = 3 B = 2 D = 4 Evaluate the valid expression: A B C + * D /
Postfix Example #1 Token ABC+*D/ ABC+*D/ ABC+*D/ ABC+*D/ Alg Step 1 1 1 2(a) 2(b) 2(c) 2(a) 2(b) 2(c) 1 2(a) 2(b) 2(c) Stack Description push value of A push value of B push value of C pop top two values: y = 3, x = 2 compute z = x + y or z = 2 + 3 push result (5) of the addition pop top two values: y = 5, x = 8 compute z = x * y or z = 8 * 5 push result (40) of the multiplication push value of D pop top two values: y = 4, x = 40 compute z = x / y or z = 40 / 4 push result (10) of the division 8 8 2 8 2 3 8 8 8 5 ABC+*D/ 40 40 4 ABC+*D/ ABC+*D/ 10
Postfix Example #2 What happens if the expression is invalid? A B * C D + Token AB*CD+ AB*CD+ AB*CD+ Alg Step 1 1 2(a) 2(b) 2(c) 1 1 2(a) 2(b) 2(c) xxxxxx Stack Description push value of A push value of B pop top two values: y = 2, x = 8 compute z = x * y or z = 8 * 2 push result (16) of the multiplication push value of C push value of D pop top two values: y = 4, x = 3 compute z = x + y or z = 3 + 4 push result (7) of the addition Too many values left on the stack. 8 8 2 16 16 3 16 3 4 16 16 16 7 xxxxxx AB*CD+ AB*CD+ AB*CD+ Error
