Data Structures
A P P L I C AT I O N S O F S TA C K S
Data Structures
Parsing Parenthesis
2
We have seen use of stack in validation of
expression using only ‘(‘ and ‘)’ scope delimiter
Let us change the problem slightly
Three different kinds of scope delimiters exist
e.g { x + (y – [a +b]) }
The scope ender must be of same type as scope
opener
It is necessary to keep track of not only the count
of scope but also the types
A stack may be used to keep track of the types of
scopes encountered
Data Structure
Stacks in validating an expression
3
Whenever a scope opener is encountered, it is
pushed into the stack
Whenever a scope ender is encountered, the
stack is examined
If the stack is empty, the scope ender does not
have a matching opener and string is invalid
If stack is not empty, we pop an item and check
if it corresponds to scope ender
If match occurs we continue, otherwise the
expression is invalid
At the end of the string the stack must be empty
Data Structure
Pusedo-code
Valid = true
S = empty stack
while (not end of string) {
read symb
if (symb == '(' || symb == '[' || symb == '{')
push(S, symb)
else if (symb == ')' || symb == ']' || symb == '}') {
if (empty(S)) {
Valid = false
} else {
I = pop(S)
if ((symb == ')' && I != '(') ||
(symb == ']' && I != '[') ||
(symb == '}' && I != '{'))
Valid = false
}
}
}
if (Valid && empty(S))
print "Valid String"
else
print "Not a valid string"
4
{ x + (y – [a +b]) }
5
( ( (
{ { { { {
1 2 3 4 5 6 7
Data Structure
Assignment
Write a C++ program using an array-based stack (push and
pop) to check whether the following expression is balanced or
not:
{ [ a + (b * c) ] + (d /
e) }
Prefix and Postfix notations
8
Data Structures
Infix, Postfix and Prefix Expressions
9
INFIX: From our schools times we have been
familiar with the expressions in which operands
surround the operator, e.g. x+y, 6*3 etc this way of
writing the Expressions is called infix notation.
POSTFIX: They are different from the infix in the
sense that in the postfix notation, operator comes
after the operands, e.g. xy+, xyz+* etc.
PREFIX: In the prefix notation, as the name
suggests, operator comes before the operands, e.g.
+xy, *+xyz etc.
Data Structures
Operator Priorities
10
How do you figure out the operands of an
operator?
a+b*c
a*b+c/d
This is done by assigning operator priorities.
priority(^) > priority(*) = priority(/) > priority(+) =
priority(-)
When an operand lies between two operators,
the operand associates with the operator that
has higher priority.
Data Structures
Tie Breaker
11
When an operand lies between two
operators that have the same priority,
the operand associates with the
operator on the left.
a+b-c
a*b/c/d
Data Structures
Delimiters
12
Sub-expression within delimiters is treated
as a single operand, independent from the
remainder of the expression.
(a + b) * (c – d) / (e – f)
Data Structures
WHY
13
Why to use these weird looking PREFIX and POSTFIX
notations when we have simple INFIX notation?
To our surprise INFIX notations are not as simple as
they seem specially while evaluating them. To
evaluate an infix expression, we need to consider
Operators’ Priority and Associative property
For example expression 3+5*4 evaluate to 32 i.e. (3+5)*4
or to 23 i.e. 3+(5*4).
To solve this problem Precedence or Priority of the
operators were defined. Operator precedence governs
evaluation order. An operator with higher precedence
is applied before an operator with lower precedence.
Data Structures
Infix Expression Is Hard To Parse
14
Need operator priorities, tie breaker,
and delimiters.
This makes expression evaluation more
difficult than is necessary.
Postfix and prefix expression forms do
not rely on operator priorities, a tie
breaker, or delimiters.
So it is easier to evaluate expressions
that are in these forms.
Data Structures
Prefix and Postfix notations
15
Due to above mentioned problem of considering
operators' Priority and Associative property while
evaluating an expression using infix notation, we
use prefix and postfix notations
Both prefix and postfix notations have an advantage
over infix that while evaluating an expression in
prefix or postfix form we need not to consider the
Priority and Associative property (order of brackets)
E.g. x/y*z becomes */xyz in prefix and xy/z* in postfix.
Both prefix and postfix notations make Expression
Evaluation a lot easier
Data Structures
Example: postfix expressions
16
Postfix notation is another way of writing
arithmetic expressions.
In postfix notation, the operator is written after
the two operands.
infix: 2+5 postfix: 2 5 +
Expressions are evaluated from left to right.
Precedence rules and parentheses are never
needed!!
Data Structures
Suppose that we would like to rewrite A+B*C in
postfix
17
Applying the rules of precedence, we obtained
A+B*C
A+(B*C) Parentheses for emphasis
A+(BC*) Convert the multiplication, Let D=BC*
A+D Convert the addition
AD+
ABC*+ Postfix Form
Data Structures
Suppose that we would like to rewrite A+B*C in
postfix
18
Step 1:
Apply parentheses A+(B*C) Parentheses for emphasis
Step 2:
Convert the multiplication A+(BC*), replace BC* with
into postfix form D
New expression becomes
A+D
Step 3:
Convert the addition into AD+
post fix form
Step 4:
Final expression ABC*+ (post fix form)
Data Structures
Postfix Examples
19
Infix Postfix Evaluation
2-3*4+5 234*-5+ -5
(2 - 3) * (4 + 5) 23-45+* -9
2- (3 * 4 +5) 234*5+- -15
Why ? No brackets necessary !
Data Structures
Examples of infix to prefix and post fix
21
Infix PostFix Prefix
A+B AB+ +AB
(A+B) * (C + D) AB+CD+* *+AB+CD
A-B/(C*D^E) ABCDE^*/- -A/B*C^DE
Data Structures
When do we need to use them…
22
So, what is actually done is expression is
scanned from user in infix form; it is
converted into prefix or postfix form and
then evaluated without considering the
parenthesis and priority of the operators.
Data Structures
Algorithm for Infix to Postfix
1) Examine the next element in the input.
2) If it is operand, output it.
3) If it is opening parenthesis, push it on stack.
4) If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of stack is opening parenthesis, push operator
on stack
iii) If it has higher priority than the top of stack, push
operator on stack.
iv) Else pop the operator from the stack and output it,
repeat step 4
5) If it is a closing parenthesis, pop operators from stack and
output them until an opening parenthesis is encountered.
pop and discard the opening parenthesis.
6) If there is more input go to step 1
7) If there is no more input, pop the remaining operators to
output. 23
Evaluating a postfix expression
24
Use a stack to evaluate an expression in postfix
notation
The postfix expression to be evaluated is scanned from
left to right
Each operator in a postfix string refers to the previous
two operands in the string
Each time we read an operand we push it into a stack.
When we reach an operator, its operands will then be
top two elements on the stack
We can then pop these two elements, perform the
indicated operation on them, and push the result on
the stack.
So that it will be available for use as an operand of the
next operator.
Data Structures
Evaluating a postfix expression
25
Initialise an empty stack
While token remain in the input stream
Read next token
If token is an operand, push it into the stack
Else, if token is an operator, pop top two tokens off the
stack, apply the operator, and push the answer back
into the stack
Pop the answer off the stack
Data Structures
Example: postfix expressions
(cont.)
26
Data Structures
Postfix expressions:
Algorithm using stacks (cont.)
27
Data Structures
Question : Evaluate the following expression in postfix :
6 2 3+ -3 8 2/+ *2^3+
Final answer is
49
51
52
7
None of these
28
Evaluate: 6 2 3+ - 3 8 2/+*2^3+
29
Symbol opnd1 opnd2 value opndstk
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
Data Structures
Evaluate- 6 2 3 + - 3 8 2/+*2^3+
30
Symbol opnd1 opnd2 value opndstk
8 6 5 1
1,3,8
2 6 5 1
1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7
1,7
* 1 7 7 7
2 1 7 7
7,2
^ 7 2 49 49
3 7 2
Data Structures
49