Applications of Stack

Applications of Stack
Stacks
 Last In First Out (LIFO List)
◦ FILO?
 Insertions and Deletions from the same
end called the Top
 Push(), Pop(), Top(), IsEmpty() IsFull()
 Implementation
◦ Arrays
◦ Linked Lists (SLL/DLL)
Applications of Stack
 Reversing a String
 Parentheses Matching
 Arithmetic Expressions
◦ Infix to Postfix conversion
◦ Infix to Prefix conversion
◦ Evaluation of Postfix arithmetic expressions
Matching Parentheses
 Balanced parentheses and brackets
◦ every open parenthesis/bracket is matched
with a corresponding close parenthesis
◦ Parenthesis/bracket are properly nested
 Example
 (x(y)(z)) - balanced
 a( {(b)}c) - balanced
 w)(x) - not balanced
 p({(q)r)} - not balanced
Matching Parentheses
 Scan expression from left to right, one character at a
time
 If left/opening parenthesis, push corresponding closing

parenthesis onto the stack
 If right/closing parenthesis then

◦ If stack empty then
 error, exit
◦ Else
 If it matches with the topmost element on the stack then
 pop stack and continue
 else
 report error and exit
Matching Parenthesis
 Draw the status of the stack for following
cases:
◦a(b{de[f]g{h}I}jk)lm
◦(ab{c}d([e[f]g])(j))
Matching Parenthesis
◦ Reading the string, from Left to Right, the
status of stack is:
a(b{de[f]g{h}I}jk)lm
] }
} } } } }
) ) ) ) ) ) )
Arithmetic Expressions
 A + B : Infix
 +AB : Prefix
 AB+ : Postfix
 Stack Applications
◦ Conversions
◦ Evaluation
Evaluation of Arithmetic Expressions
 Precedence rules
◦ Exponentiation
◦ Multiplication/Division
◦ Addition / Subtraction
 Use parentheses to overide precedence rules
 When operators of same precedence are

scanned (without brackets)
◦ the order is assumed to be left to right, the order in
which they are read
Example: Infix to Postfix
 Example 1  Example 2
A+B*C (A + B) * C
=> (A + (B*C)) => (A + B) *C)
=> (A + (BC*)) => (AB+) * C)
=> A (BC*) + => (AB+) C*
=> ABC * + => AB + C *
Example
 A+B–C
◦ AB+C- (Postfix)
◦ - + ABC (Prefix)
 (A+B) * (C-D)
◦ AB+ CD - * (Postfix)
◦ *+AB – CD (Prefix)
Conversion: infix to postfix
 A+B*C–D/E
Pre (*) > Pre (+)

Pre (-) < Pre (*)
Pre (-) == Pre (+)
Pre (/) > Pre (-)
*/
Output:
+-
AB C* +DE /-
The Algorithm
◦ Read an item from input infix expression
◦ If item is an operand append it to postfix string
◦ If item is “(“ push it on the stack
◦ If the item is an operator
 If the operator has higher precedence than the one already on
top of the stack then push it onto the operator stack
 If the operator has lower precedence than the one already on
top of the stack then
 pop the operator on top of the operator stack and append it
to postfix string, and
 push lower precedence operator onto the stack
◦ If item is “)” pop all operators from top of the stack one-by-
one, until a “(“ is encountered on stack and removed
 If Stack Empty and corresponding “(” not obtained then “error”
 A * B – (C+D) + E
◦ Push (*) *
◦ Pre (-) < Pre (*) => Pop (*) & Push (-) -
◦ Push “(“ - (
◦ Push (+) since STop = “(“ - ( +
◦ Since “)” => Pop (+) , Pop “(” -

◦ Pre (+) == Pre (-) => Pop (-), Push (+) +
◦ Since end pop till stack empty
AB * CD+ - E+
Evaluating a postfix expression
 Each operator in a postfix string refers to
the previous two operands in the string
 One of the operand may itself be the
result of applying a previous operator
Evaluating a postfix expression using a
Stack
 Read the input string from Left to Right
 Each time an operand is read
 Push it on the stack
 When an operator is read
◦ Pop the two operands from the top of the stack
◦ Perform the indicated operation on the two
operands
◦ Push the result back onto the stack, so that it is
available as an operand for the next operator
Evaluating a postfix expression using a Stack
– Example
 63+2*
◦ Push (6)
◦ Push (3)
+
◦ Pop (3)
◦ Pop (6)
◦ Calculate ( 6+3 = 9)
◦ Push (9)
◦ Push (2)
*
◦ Pop (2)
◦ Pop (9)
◦ Calculate (9 * 2 = 18)
◦ Push (18)
Implementing Postfix Through
Stack
19
Implementing Postfix Through
Stack
20
Conversion: Infix to Prefix
 Reverse the input string
 Scan the input string from left to right
one character at a time (token)
 Call modified infix to postfix algorithm
 Reverse the output string to get the
prefix expression
If token is
 Left “(“
Push on the stack
 Operand (number/letter)
Write directly to output string
 Right “)”
Pop stack till corresponding “(” is found
If Stack Empty then “error”
Else while stack not empty
pop stack and write to output string
 Operator
If stack empty or sTop = “(“ then
push token/ operator onto stack
If precedence (token) >= precedence (sTop)

then
push token/ operator onto stack
If precedence (token) < precedence (sTop) then

while stack not empty
Pop stack and write to output
Push token onto stack
 A – (B/C) * D - Infix
 A – (/BC) * D
 A – [(/BC) * D]
 A - */BCD
 -A*/BCD - Prefix
 Infix: A – (B/C) * D
 Reverse: D * (C/B) – A
 Convert to postfix:
◦ D
◦ Push (*) *
◦ Push “(“ * (
◦ DC
◦ Push (/) since sTop == “(“ * ( /
◦ DCB
◦ Pop (/), Pop “(“ *
 => DCB/
◦ Pre (-) < Pre (*) => Pop (*)
 => DCB/*,
 Push (-) -
◦ DCB/*A
◦ Pop (-) => DCB/*A-
 Reverse: -A * / B C D
Evaluating Prefix
 Read the input string from Right to Left
 Each time an operand is read
◦ Push it on the stack
 When an operator is read
◦ Pop the two operands from the top of the stack
◦ Perform the indicated operation on the two
operands
◦ Push the result back onto the stack, so that it is
available as an operand for the next operator

Applications of Stack

Uploaded by

Copyright:

Available Formats

Applications of Stack

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Applications of Stack

Uploaded by

Copyright:

Available Formats

Applications of Stack

 If left/opening parenthesis, push corresponding closing

 If right/closing parenthesis then

 Use parentheses to overide precedence rules

 When operators of same precedence are

Pre (*) > Pre (+)

◦ Push (+) since STop = “(“ - ( +

◦ Since “)” => Pop (+) , Pop “(” -

◦ Since end pop till stack empty

If precedence (token) >= precedence (sTop)

If precedence (token) < precedence (sTop) then

You might also like