Department of
Computer Science and Engineering
DATA STRUCTURES
Unit 1-Linear structures
Year/Sem : II/III
Subject Code: 1151CS102
Topic : Applications of stack
Faculty Name : Mrs.Vijitha.S
Date : 26.08.2020
School of Computing
Vel Tech Rangarajan Dr. Sagunthala R&D Institute of
Science and Technology
Application of stack
Application of stack:
Stacks can be used for expression evaluation.
Stacks can be used to check parenthesis matching
in an expression.
Stacks can be used for Conversion from one form of
expression to another.
Stacks can be used for Memory Management.
Stack data structures are used in backtracking
problems.
07/09/2021 Department of Computer Science and Engineering 2
Application of stack
Expression Evaluation:
Stack data structure is used for evaluating the given
expression. For example, consider the following
expression
5 * ( 6 + 2 ) - 12 / 4
Since parenthesis has highest precedence among
the arithmetic operators, ( 6 +2 ) = 8 will be evaluated
first.
Now, the expression becomes
5 * 8 - 12 / 4
07/09/2021 Department of Computer Science and Engineering 3
Application of stack
Expression Evaluation:
* and / have equal precedence and their associativity
is from left-to-right. So, start evaluating the expression
from left-to-right.
5 * 8 = 40 and 12 / 4 = 3
Now, the expression becomes 40 - 3
And the value returned after the subtraction operation
is 37
07/09/2021 Department of Computer Science and Engineering 4
Infix expressions
Infix expressions:
Example: X+Y
Where X,Y-Operands and +--Operators
Operators are written in between their operands.
07/09/2021 Department of Computer Science and Engineering 5
Prefix expressions
Prefix expressions:
Example: +XY
Where X,Y-Operands and +--Operators
Operators are written before their operands.
and Project
Management
(SEPM)
07/09/2021 Department of Computer Science and Engineering 6
Postfix expressions
Postfix expressions:
Example: XY+
Where X,Y-Operands and +--Operators
Operators are written after their operands.
07/09/2021 Department of Computer Science and Engineering 7
Evaluation of Infix,prefix,postfix
Conversion of prefix to infix
Conversion of prefix to postfix
Conversion of postfix to prefix
Conversion of infix to prefix
Conversion of infix to postfix
26.06.2020 Department of Computer Science and Engineering 8
Prefix to infix
Algorithm for Prefix to Infix:
Read the Prefix expression in reverse order (from right to
left).
If the symbol is an operand, then push it onto the Stack.
If the symbol is an operator, then pop two operands from the
Stack.
Create a string by concatenating the two operands and the
operator between them.
string = operand1 + operator + operand2
And push the resultant string back to Stack
Repeat the above andsteps
Project until end of Prefix expression.
Management
(SEPM)
26.06.2020 Department of Computer Science and Engineering 9
Prefix to infix EXPRESSION STACK
C-BA+* D
Given string:
-BA+* C ---OP1
*+AB-CD D ---OP2
BA+* C-D
Steps: A+* B
C-D
Reverse the string.
DC-BA+* +* A
Scan ‘D’ B
Scan ‘C’ C-D
Scan ’-’
* A+B
Scan ‘B’ and Project
Scan ‘A’ Management
(SEPM)
C-D
Scan ‘+’ END (A+B)*(C-D)
Scan ’*’
26.06.2020 Department of Computer Science and Engineering 10
Prefix to postfix
Algorithm for Prefix to Postfix:
Read the Prefix expression in reverse order (from right to left)
If the symbol is an operand, then push it onto the Stack.
If the symbol is an operator, then pop two operands from the
Stack.
Create a string by concatenating the two operands and the
operator after them.
string = operand1 + operand2 + operator
And push the resultant string back to Stack
Repeat the above steps until end of Prefix expression.
and Project
Management
(SEPM)
26.06.2020 Department of Computer Science and Engineering 11
Prefix to postfix EXPRESSION STACK
C-BM+* N
Given string:
-BM+* C ---OP1
*+MB-CN N ---OP2
BM+* CN-
Steps: M+* B
Reverse the string. CN-
NC-BM+* +* M
Scan ‘N’ B
Scan ‘C’
CN-
Scan ’-’
Scan ‘B’ * MB+
and Project
Scan ‘M’ Management
(SEPM) CN-
Scan ‘+’ END MB+CN-*
Scan ’*’
26.06.2020 Department of Computer Science and Engineering 12
Postfix to prefix
Algorithm for Postfix to prefix:
Read the Postfix expression from left to right
If the symbol is an operand, then push it onto the Stack
If the symbol is an operator, then pop two operands from
the Stack.
Create a string by concatenating the two operands and the
operator before them.
string = operator + operand1 + operand2.
And push the resultant string back to Stack.
Repeat the above andsteps
Project until end of Prefix expression.
Management
(SEPM)
26.06.2020 Department of Computer Science and Engineering 13
EXPRESSION STACK
Postfix to prefix
H+CF-* E
Given string:
+CF-* H ----OP2
EH+CF-* E ----OP 1
CF-* +EH
Steps: F-* C
+EH
Scan from left to
right -* F
Scan ‘E’ C
Scan ‘H’
+EH
Scan ’+’
Scan ‘C’ * -CF
and Project
Scan ‘F’ Management
(SEPM)
+EH
Scan ‘-’
END *+EH-CF
Scan ’*’
26.06.2020 Department of Computer Science and Engineering 14
Evaluation of Infix,prefix,postfix
LOW LOW
HIGH LOW * / ----highest
priority
+ - -----lowest
priority
HIGH HIGH
LOW HIGH
and Project
Management
(SEPM)
26.06.2020 Department of Computer Science and Engineering 15
Infix to prefix
Algorithm for Infix to prefix:
First, reverse the given infix expression.
Scan the characters one by one.
If the character is an operand, copy it on to the output.
If the character is a left parenthesis, then push it to the stack.
If the character is an right parenthesis, pop the elements in
the stack until we find the corresponding left parenthesis.
If the character scanned is an operator
If the operator has precedence greater than or equal to
the top of the stack, push the operator to the stack.
If the operatorandhas
Projectprecedence lesser than the top of the
stack, pop the operator and push into the output.
Management
(SEPM)
Reverse the final expression.
26.06.2020 Department of Computer Science and Engineering 16
Input Stack Output
Infix to prefix
( (
consider the infix expression D ( D
(A+B)*(C+D) + (+ D
C (+ DC
Reverse the string
) (+) DC
(D+C)*(B+A)
) DC+
* * DC+
( *( DC+
Prefix expression is *+AB+CD B *( DC+B
+ *(+ DC+B
A *(+ DC+BA
) *(+) DC+BA
) * DC+BA+
END DC+BA+*
26.06.2020 Department of Computer Science and Engineering 17
Infix to postfix
Algorithm for Infix to postfix:
Scan the characters one by one.
If the character is an operand, copy it on to the output.
If the character is a left parenthesis, then push it to the stack.
If the character is an right parenthesis, pop the elements in
the stack until we find the corresponding left parenthesis.
If the character scanned is an operator
If the operator has precedence greater than or equal to
the top of the stack, push the operator to the stack.
If the operator has precedence lesser than the top of the
stack, pop theandoperator
Project and output it to the prefix notation
output and then check the above condition again with the
Management
(SEPM)
new top of the stack.
26.06.2020 Department of Computer Science and Engineering 18
Infix to postfix Input Stack Output
A A
consider the infix expression + + A
A+(B*C-(D/E^F)*G)*H ( +( A
B +( AB
Steps:
* +(* AB
C +(* ABC
Scan ‘A’
Scan ‘+’ - +(- ABC*
Scan ‘(’ ( +(-( ABC*
Scan ‘B’ D +(-( ABC*D
Scan ‘*’ / +(-(/ ABC*D
Scan ‘C’ E +(-(/ ABC*DE
Scan ‘-’ and Project
^ +(-(/^ ABC*DE
Management
Scan ‘(’ (SEPM) F +(-(/^ ABC*DEF
Scan ‘D’
) +(-(/^) ABC*DEF
Scan ‘/’
26.06.2020 Department of Computer Science and Engineering 19
Infix to postfix
Input Stack Output
consider the infix expression
A+(B*C-(D/E^F)*G)*H ) +(- ABC*DEF^/
* +(-* ABC*DEF^/
Scan ‘E’ G +(-* ABC*DEF^/G
Scan ‘^’ ) +(-*) ABC*DEF^/G
Scan ‘F’ ) + ABC*DEF^/G*-
Scan ‘)’ * +* ABC*DEF^/G*-
Scan ‘*’ H +* ABC*DEF^/G*-H
Scan ‘G’ END ABC*DEF^/G*-H*+
Scan ‘)’
Scan ‘*’
Scan ‘H’ and Project
Management
(SEPM)
Postfix expression is
ABC*DEF^/G*-H*+
26.06.2020 Department of Computer Science and Engineering 20
EVALUATING POSTFIX EXPRESSION
Department of Computer Science and Engineering
BALANCING PARENTHESIS
• Declare a character stack S.
• Now traverse the expression string exp.
If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘)
then push it to stack.
If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then
pop from stack and if the popped character is the matching starting
bracket then fine else parenthesis are not balanced.
• After complete traversal, if there is some starting bracket left in
stack then “not balanced”
Balancing Parenthesis
Department of Computer Science and Engineering 22
BALANCING PARENTHESIS
VALID INPUTS INVALID INPUTS
{} {(}
({[]}) ([(()])
{[]()} {}[])
[{({}[]({ [{)}(]}]
})}]
Department of Computer Science and Engineering 23
Thank You
Department of Computer Science and Engineering
