Applications of Stack (Data Structure).pdf

zz

1. Applications of Stack
ThefollowingApplicationsofstackare:
1.Stackisusedbycompilerstocheckforbalancingofparentheses,bracketsandbraces.
2.Stackisusedtoevaluateapostfixexpression.
3.Stackisusedtoconvertaninfixexpressionintopostfix/prefixform.
4.Inrecursion,allintermediateargumentsandreturnvaluesarestoredontheprocessor’sstack.
5.Duringafunctioncallthereturnaddressandargumentsarepushedontoastackandonreturnthey
arepoppedoff.

2. Expression evaluation and conversion
•The most frequent application of stacks is in the evaluation of arithmetic
expressions. An arithmetic expression is made of operands, operators.
•Operand is the quantity on which a mathematical operation is performed. Operand
may be a variable like x, y, z or a constant like 5, 4, 6 etc. Operator is a symbol
which signifies a mathematical or logical operation between the operands.
Examples of familiar operators include +, -, *, /, ^ etc.
•When high-level programming languages came into existence, one of the major
difficulties faced by computer scientists was to generate machine language
instructions that could properly evaluate any arithmetic expression. A complex
assignment statement such as

3. Might have several meanings, and even if the meanings were uniquely defied, it is
still difficult to generate a correct and reasonable instruction sequence. The fist
problem in understanding the meaning of an expression is to decide the order in
which the operations are to be carried out. This demands that every language must
uniquely define such an order.

4. Another example:
To calculate this expression for values 4, 3, 7 for A, B, C respectively we must
follow certain in order to have the right result :
•The answer is not correct; multiplication is to be done before the addition, because
multiplication has higher precedence over addition. This means that an expression
is calculated according to the operator’s precedence not the order as they look like.
•Thus expression A + B * C can be interpreted as A + (B * C). Using this
alternative method we can convey to the computer that multiplication has higher
precedence over addition.

5. •To fix the order of evaluation, assign each operator a priority, and evaluated from
left to right.

6. •Let us consider the expression
•By using priorities rules, the expression X is rewritten as
•We manually evaluate the innermost expression first, followed by the next
parenthesized inner expression, which produces the result.
•Another application of stack is calculation of postfix expression. There are
basically three types of notation for an expression (mathematical expression; An
expression is defined as the number of operands or data items combined with
several operators.)
1. Infix notation
2. Prefix notation
3. Postfix notation

7. •Infix
The infix notation is what we come across in our general mathematics, where the
operator is written in-between the operands. For example: The expression to add
two numbers A and B is written in infix notation as:
•Prefix
The prefix notation is a notation in which the operator(s) is written before the
operands. The same expression when written in prefix notation looks like:
•Postfix
In the postfix notation the operator(s) are written after the operands, so it
is called the postfix notation (post means after), it is also known as suffix
notation. The above expression if written in postfix expression looks like:

8. A + B * C Infix Form
A + (B * C) Parenthesized expression
A + (B C *) Convert the multiplication
A (B C *) + Convert the addition
A B C * + Postfix form
The rules to be remembered during infix to postfix or prefix conversion are:
1.Parenthesize the expression starting from left to right.
2.During parenthesizing the expression, the operands associated with operator having higher
precedence are first parenthesized. For example in the above expression B * C is parenthesized
first before A + B.
3.The sub-expression (part of expression), which has been converted into postfix, is to be treated as
single operand.
4.Once the expression is converted to postfix form, remove the parenthesis.

9. Exercise
A * B + C / D
(A * B) + (C / D)Parenthesized expression
(A B*) + (C / D) Convert the multiplication
(A B*) + (C D/) Convert the division
(A B*) (C D/) + Convert the addition
A B*C D/ + Postfix form

10. Converting infix to prefix expression
Example:
A * B + C / D Infix Form
(A * B) + (C/D) Parenthesized expression
(*A B) + (C/D) Convert Multiplication
(*A B) + (/CD ) Convert Division
+(*A B) (/CD ) Convert addition
+*A B /CD Prefix form
Note: the precedence rules for converting an expression from infix to prefix is
identical to postfix. The only change from postfix conversion is that the operator is
placed before the operands rather than after them.

11. Conversion from infix to postfix (another method):
Procedure to convert from infix expression to postfix expression is as follows:
1. Scan the infix expression from left to right.
2. a) If the scanned symbol is left parenthesis, push it onto the stack.
b) If the scanned symbol is an operand, then place directly in the postfix expression
(output).
c) If the symbol scanned is a right parenthesis, then go on popping all the items from the
stack and place them in the postfix expression till we get the matching left parenthesis.
d) If the scanned symbol is an operator, then go on removing all the operators from the
stack and place them in the postfix expression, if and only if the precedence of the
operator which is on the top of the stack is greater than (or greater than or equal) to the
precedence of the scanned operator and push the scanned operator onto the stack
otherwise, push the scanned operator onto the stack.
The three important features of postfix expression are:
1. The operands maintain the same order as in the equivalent infix expression.
2. The parentheses are not needed to designate the expression unambiguously.
3. While evaluating the postfix expression the priority of the operators is no longer relevant.

12. Example:Convert the following infix expression to the equivalent postfix notation.
(30+23)*(43-21)/(84+7)

13. Need for prefix and postfix expression
The evaluation of an infix expression using a computer needs proper code
generation by the compiler without any ambiguity and is difficult because of various
aspects such as the operator’s priority . This problem can be overcome by writing or
converting the infix expression to an alternate notation such as the prefix or the
postfix.
((A -(B + C)) * (C+ D / B )) ^ B + C Infix expression
A B C + -C D B / + * B ^ C + Postfix expression
Lets:
A = 6
B = 2
C = 3
D = 8
6 2 3 + -3 8 2 / + * 2 ^ 3 + Postfix

14. Evaluate the following expression in postfix
6 2 3 + -3 8 2 / + * 2 ^ 3 +