{"id":142,"date":"2018-07-18T10:57:13","date_gmt":"2018-07-18T10:57:13","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=142"},"modified":"2018-12-12T08:57:24","modified_gmt":"2018-12-12T08:57:24","slug":"applications-of-stacks-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/applications-of-stacks-i\/","title":{"rendered":"Applications of Stacks &#8211; I"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/k0PT3yI7pG4\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will talk about some of the applications of the Stack ADT.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of the introductory module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0 To discuss some important applications of Stacks\r\n\r\n\u2022\u00a0 To explain the handling of Algebraic expressions by stacks\r\n\r\n\u2022\u00a0 To outline the conversion of infix to postfix using stacks\r\n\r\n\u2022\u00a0 To explain the evaluation of postfix expression using stacks\r\n\r\n&nbsp;\r\n\r\n<strong>9.1 Stacks<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The stack is the simplest of all ADTs and understanding how a stack works is easy. The application of a stack, however, requires the creation of a design which allows the use of a stack and therein lies the challenge. We will look at reverse Polish, parsing, function calls, and other interesting applications.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Two types of applications of stacks are applications that require keeping track of the last state processed and the checking for balancing symbols. Recursion type of Applications that use stacks are implementation of recursive calls and applications where there is a need to keep track of the state we are in such as searching networks, traversing trees (keeping a track where we are).etc. One important group of examples that use stacks is the evaluation of algebraic expressions, checking balanced expressions and recognizing palindromes. Let us first look at the use of stacks to handle algebraic expressions.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2 Algebraic Expressions<\/strong>\r\n\r\n&nbsp;\r\n\r\nBefore we go into the details of how to use stacks, let us understand the three different types of expressions:\r\n<ul>\r\n \t<li style=\"text-align: justify\">Infix expressions \u2013 in this case an operator appears between its operands. This is the conventional way of writing algebraic expressions.<\/li>\r\n<\/ul>\r\nA simple example: a + b\r\n<ul>\r\n \t<li>Prefix expressions \u2013 in this case the operator appears before its operands.<\/li>\r\n<\/ul>\r\nExample: + a b\r\n<ul>\r\n \t<li>Postfix expressions \u2013 in this the operator appears after its operand<\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Example: a b +\r\n\r\n&nbsp;\r\n\r\nMore interesting examples of all types of expressions are given in\u00a0 Figure 9.1.\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-145 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54.png\" alt=\"\" width=\"512\" height=\"316\" \/>\r\n<p style=\"text-align: justify\">Both prefix and postfix expressions do not need precedence rules, association rules or parentheses and have simple grammar expressions and straightforward recognition and evaluation algorithms. This is the reason why they are generally used during computation.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2.1 Reverse Polish (Postfix) Notation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As already discussed an infix expression can be converted by placing the operands first, followed by the operator rather than in between as in the case of infix expression.<\/p>\r\n&nbsp;\r\n\r\nExample:\r\n\r\nInfix --- (3 + 4) \u00d7\u00a0 5 \u2013 6\r\n\r\nPostfix-- 3\u00a0 4\u00a0 + 5\u00a0 \u00d7 6\u00a0 \u2013\r\n\r\n&nbsp;\r\n\r\nParsing reads left-to-right and performs operation on two operands\r\n\r\nExample\r\n\r\n3\u00a0 4 +\u00a0 5\u00a0 \u00d7 6\u00a0 \u2013\r\n\r\n7\u00a0 \u00a0 5\u00a0 \u00d7 6\u00a0 \u2013\r\n\r\n35\u00a0 \u00a0 \u00a06\u00a0 \u2013\r\n\r\n29\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This method of representing the expression is called <em>reverse-Polish<\/em> notation after the mathematician Jan \u0141ukasiewicz (Figure 9.2) and the method forms the basis of the recursive stack used on all processors. Jan \u0141ukasiewicz also made significant contributions to logic and other fields of computer science.<\/p>\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-146 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55.png\" alt=\"\" width=\"249\" height=\"317\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nNow let us summarize the benefits of the <em>reverse-Polish<\/em> notation from the perspective of computing.\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>\u00a0no ambiguity and no brackets are required<\/li>\r\n \t<li>\u00a0this is the same process used by a computer to perform computations:<\/li>\r\n \t<li>\u00a0operands must be loaded into registers before operations can be performed on them.<\/li>\r\n \t<li>\u00a0reverse-Polish can be processed using stacks<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0 Reverse-Polish notation is used with some programming languages, examples include postscript, pdf, and HP calculators. This processing is similar to the thought process required for writing assembly language code, where you cannot perform an operation until you have all of the operands loaded into registers.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2.2 Algebraic Expression Operations using Stacks<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">When the ADT stack is used to solve a problem, the use of the ADT\u2019s operations should not depend on its implementation. In this section we discuss the following functions that use stacks namely that conversion of an infix expression to postfix form and evaluation of the postfix expression. Now let us look at each of these functions in detail.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2.2.1 Conversion of Infix to Postfix<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here are some facts to be considered when converting from infix expression to postfix expression. Operands always stay in the same order with respect to one another. An operator will move only \u201cto the right\u201d with respect to the operands. All parentheses are removed. In other words when we analyze the conversion process we discover that<\/p>\r\n&nbsp;\r\n\r\n\u2022\u00a0 <em>Operands<\/em> are in same order in infix and postfix\r\n\r\n\u2022\u00a0 <em>Operators<\/em> occur later in the case of postfix\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The basic strategy is to send operands straight to output, output higher precedence operators first before outputting lesser precedence operators. If operators have same precedence, send them to the output in left to right order. The stack is used to hold pending operators that are yet to be given as output.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">Before we discuss the steps in detail let us give the table (Table 9.1) for the incoming priority (ICP) and in stack priority (ISP) of the different operators<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-147 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56.png\" alt=\"\" width=\"628\" height=\"539\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-148 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57.png\" alt=\"\" width=\"652\" height=\"265\" \/>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-149 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58.png\" alt=\"\" width=\"625\" height=\"494\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-150 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59.png\" alt=\"\" width=\"623\" height=\"501\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-151 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60.png\" alt=\"\" width=\"628\" height=\"283\" \/>\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0The steps and simulation of conversion of infix to postfix are shown in Figure 9.3 and Figure 9.4 respectively.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>1.\u00a0<\/strong>Figure 9.4(a) shows the initial state with Stack empty and the infix expression <strong><em>A*(B+C) \u2013D\/E <\/em><\/strong>yet to be processed. Then we scan the Infix expression from left to right for tokens.<strong>\u00a0<\/strong><\/p>\r\n<p style=\"text-align: justify\"><strong>2.\u00a0<\/strong>Figure 9.4 (b) shows the first token which is <strong><em>A<\/em><\/strong> given as output (as per step 2 of the algorithm)<\/p>\r\n<p style=\"text-align: justify\"><strong>3.\u00a0<\/strong>Figure 9.4 (c) shows the pushing of the operator <strong><em>*<\/em><\/strong> into the stack according to step 4 (b).<\/p>\r\n<p style=\"text-align: justify\"><strong>4.\u00a0<\/strong>Then the open parenthesis <strong><em>(<\/em><\/strong> is pushed onto the stack as per step 3 of the algorithm.<\/p>\r\n<p style=\"text-align: justify\"><strong>5.\u00a0<\/strong>Similarly the next token the operand <strong><em>B<\/em><\/strong> is given as output and the operator <strong><em>+<\/em><\/strong> is pushed onto the stack as shown in Figure 9.4 (e ) and 9.4 (f).<\/p>\r\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>6.\u00a0<\/strong>Next token we see is a <strong><em>)<\/em><\/strong> which means all entries in the stack up to and including open parenthesis is removed from the stack as shown in Figure 9.4 (g).<\/p>\r\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>7.\u00a0<\/strong>However neither ( or ) form part of the output. As per step 4 (a) <strong><em>*<\/em><\/strong> is popped out and \u2013 is pushed onto the stack (Figure 9.4 (h)).<\/p>\r\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>8.\u00a0<\/strong>Now the operand D is output (Figure 9.4(i)) and then the operator \/ is pushed into the stack ( Figure 9.4 (j)).<\/p>\r\n<p style=\"text-align: justify\"><strong>9.\u00a0<\/strong>Figure 9.4 (k) shows E being\u00a0 the next output token and<\/p>\r\n<p style=\"text-align: justify\"><strong>10. <\/strong>Finally operators left in the stack are popped out in the last in first out order (Figure 9.4 (l)).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">As you can see an important part of the algorithm is the comparison of the precedence of the operators that are scanned and those that are in the stack. If the operators in the stack have higher precedence than the precedence of the incoming operator then they are outputted in reverse order to which they were pushed into the stack. Then the lower precedence operator is pushed into the stack. The other important part of the algorithm is the handling of parenthesis. When a right parenthesis is encountered, we pop all operators in the stack up to and including the matching left parenthesis. However neither the open or closing parenthesis is given as output. When this step is carried out when we say matching parenthesis we mean that the type of parenthesis should also match.<\/p>\r\n&nbsp;\r\n\r\n<strong>9.2.2.2<\/strong>\u00a0\u00a0<strong>Evaluating Postfix Expression<\/strong>\r\n\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 The next application of stack that we discuss is the evaluation of postfix expression.\r\n\r\nThe basic concept is as follows:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2022 Whenever an operand is encountered, push it onto the stack<\/p>\r\n<p style=\"text-align: justify\">\u2022 Whenever an operator is encountered, pop required number of arguments from operand stack and evaluate<\/p>\r\n\u2022 Push result back onto stack\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The algorithm considers two cases \u2013 namely when the operator is binary or when it is unary where the number of operands popped out of the stack depends on the type of operator. Figure 9.6 shows a running example of the use of stack for evaluating a postfix expression. In the figure we have numbered the operators in order to explain the process. Please note that the stack is a single stack. The first column shown in the Figure 9.6 is the stack. However the second column is used to show the progress of the evaluation and does not form part of the stack.<\/p>\r\n&nbsp;\r\n\r\nThe detail steps of the algorithm are given in Figure 9.5.\r\n\r\n<\/div>\r\n<table style=\"border-collapse: collapse;width: 100%\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100%\"><strong>\u00a0 \u00a0 Algorithm for Evaluation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">1. Empty the operand stack<\/p>\r\n<p style=\"text-align: justify\">2.<strong>while <\/strong>there are more tokens - Get the next token<\/p>\r\n<p style=\"text-align: justify\">3.I<strong>f <\/strong>the first character of the token is an operand Push it onto the stack<\/p>\r\n<p style=\"text-align: justify\">4.\u00a0<strong>else if <\/strong>the token is a binary operator<\/p>\r\n<p style=\"text-align: justify\">a. Pop the right operand off the stack<\/p>\r\n<p style=\"text-align: justify\">b. Pop the left operand off the stack<\/p>\r\n<p style=\"text-align: justify\">c. Evaluate the operation<\/p>\r\n<p style=\"text-align: justify\">d. Push the result onto the stack<\/p>\r\n<p style=\"text-align: justify\"><strong>5.\u00a0<\/strong><strong>else if <\/strong>the token is an unary operator<\/p>\r\n<p style=\"text-align: justify\">a. Pop the top operand off the stack<\/p>\r\n<p style=\"text-align: justify\">b. Evaluate the operation<\/p>\r\n<p style=\"text-align: justify\">c. Push the result onto the stack<\/p>\r\n<p style=\"text-align: justify\">6. Pop the stack and return the result<\/p>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Figure 9.5 Algorithm for Evaluation of Postfix Expression<\/strong><\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-152 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61.png\" alt=\"\" width=\"613\" height=\"223\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-153 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62.png\" alt=\"\" width=\"599\" height=\"455\" \/>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-154 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63.png\" alt=\"\" width=\"620\" height=\"424\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-155 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64.png\" alt=\"\" width=\"609\" height=\"420\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-156 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65.png\" alt=\"\" width=\"579\" height=\"414\" \/>\r\n<p style=\"text-align: center\"><strong>Figure 9.6 A Running Example for Evaluating Postfix Expression<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Figure 9.6(a) shows the initially empty stack and the input postfix expression with 8 operators (given below) which we wish to evaluate. The expression will be read one by one, left to right until the end of the expression is reached.<\/p>\r\n<p style=\"text-align: center\">3\u00a0 6 3\u00a0 +\u00a0 5\u00a0 5 6\u00a0 \u00d7\u00a0 +\u00a0 8\u00a0 \u00d7\u00a0 \u2013\u00a0 8\u00a0 6\u00a0 \u00d7\u00a0 + +<\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">\u00a0 \u00a01.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">As long as the tokens from left to right are operands (3,6,3) the elements are pushed onto the stack one by one ( Figure 9.6 (a) \u2013(c)) \u2013 step 3 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">2.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">The next token is a binary + operator (1) (operators are identified by numbers in Figure 9.6) and therefore we pop the top two elements from the stack 3 &amp; 6, perform the operation and push the result 9 back on to the stack (Figure 9.6 (d)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">3.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">The next three tokens are operands and they are pushed onto the stack (Figure 9.6 (e)\u2013(g)) \u2013 step 3 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">4.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now the next token is a binary x operator (2) and therefore we pop the top two elements from the stack 6 &amp; 5, perform the operation and push the result 30 back on to the stack (Figure 9.6 (h)) \u2013 step 4 of the algorithm<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">5.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we again see a binary + operator (3) and therefore we pop the top two elements from the stack 30 &amp; 5, perform the operation and push the result 35 back on to the stack (Figure 9.6 (i)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">6.<\/strong><span style=\"font-size: 1em\">The next token is the operand 8, which we push onto the stack (Figure 9.6 (j))<\/span><strong style=\"font-size: 1em\">\u00a0<\/strong><span style=\"text-align: initial;font-size: 1em\">\u00a0step 3 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">7.\u00a0<\/strong><span style=\"font-size: 1em\">Now we again see a binary x operator (4) and therefore we pop the top two elements from the stack 8 &amp; 35, perform the operation and push the result 280 back on to the stack (Figure 9.6 (k)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">8.\u00a0<\/strong><span style=\"font-size: 1em\">Again we see a binary - operator (5) and therefore we pop the top two elements from the stack 280 &amp; 9, perform the operation and push the result - 271 back on to the stack (Figure 9.6 (l)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">9.\u00a0<\/strong><span style=\"font-size: 1em\">The next two tokens are the operands 8 &amp; 6, which we push onto the stack (Figure 9.6 (m)) \u2013 step 3 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">10. <\/strong><span style=\"font-size: 1em\">The next token is a binary x operator (6) and therefore we pop the top two elements from the stack 8 &amp; 6 perform the operation and push the result 48 back on to the stack (Figure 9.6 (n)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">11. <\/strong><span style=\"font-size: 1em\">The next token is a binary + operator (7) and therefore we pop the top two elements from the stack 48 &amp; -271 perform the operation and push the result - 223 back onto the stack (Figure 9.6 (o)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">12. <\/strong><span style=\"font-size: 1em\">The next token is again a binary + operator (8) and therefore we pop the top two elements from the stack -223 &amp; 3 perform the operation and push the result -220 back onto the stack (Figure 9.6 (p)) \u2013 step 4 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">13. <\/strong><span style=\"font-size: 1em\">Finally we see that all tokens have been handled, and the stack is empty, therefore the result -220 is on top of the stack (Figure 9.6 (q)) \u2013 step 6 of the algorithm.<\/span><\/p>\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">In this example we have not considered an unary operator but in that case only one operand will be taken from the stack processed and pushed onto the stack. The algorithm finishes only when all tokens of the input have been handled and the stack is empty.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">As you have seen in both these applications stacks are used to keep track of the elements that are to be processed. While in the first application the stack is used to store operators to keep track of precedence, in the second application the stack\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">stores the operands to ensure the recent operands are used with the associated operator.<\/span><\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Discussed some important applications of Stacks<\/li>\r\n \t<li>Explained the handling of Algebraic expressions by stacks<\/li>\r\n \t<li>Outlined the conversion of infix to postfix using stacks<\/li>\r\n \t<li>Discussed the evaluation of postfix expression using stacks<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Applications of Stacks \u2013 I<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/k0PT3yI7pG4\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<img class=\" wp-image-157 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66.png\" alt=\"\" width=\"740\" height=\"458\" \/>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/k0PT3yI7pG4\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will talk about some of the applications of the Stack ADT.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of the introductory module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 To discuss some important applications of Stacks<\/p>\n<p>\u2022\u00a0 To explain the handling of Algebraic expressions by stacks<\/p>\n<p>\u2022\u00a0 To outline the conversion of infix to postfix using stacks<\/p>\n<p>\u2022\u00a0 To explain the evaluation of postfix expression using stacks<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.1 Stacks<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The stack is the simplest of all ADTs and understanding how a stack works is easy. The application of a stack, however, requires the creation of a design which allows the use of a stack and therein lies the challenge. We will look at reverse Polish, parsing, function calls, and other interesting applications.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Two types of applications of stacks are applications that require keeping track of the last state processed and the checking for balancing symbols. Recursion type of Applications that use stacks are implementation of recursive calls and applications where there is a need to keep track of the state we are in such as searching networks, traversing trees (keeping a track where we are).etc. One important group of examples that use stacks is the evaluation of algebraic expressions, checking balanced expressions and recognizing palindromes. Let us first look at the use of stacks to handle algebraic expressions.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2 Algebraic Expressions<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Before we go into the details of how to use stacks, let us understand the three different types of expressions:<\/p>\n<ul>\n<li style=\"text-align: justify\">Infix expressions \u2013 in this case an operator appears between its operands. This is the conventional way of writing algebraic expressions.<\/li>\n<\/ul>\n<p>A simple example: a + b<\/p>\n<ul>\n<li>Prefix expressions \u2013 in this case the operator appears before its operands.<\/li>\n<\/ul>\n<p>Example: + a b<\/p>\n<ul>\n<li>Postfix expressions \u2013 in this the operator appears after its operand<\/li>\n<\/ul>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Example: a b +<\/p>\n<p>&nbsp;<\/p>\n<p>More interesting examples of all types of expressions are given in\u00a0 Figure 9.1.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-145 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54.png\" alt=\"\" width=\"512\" height=\"316\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54.png 512w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54-300x185.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54-225x139.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-54-350x216.png 350w\" sizes=\"auto, (max-width: 512px) 100vw, 512px\" \/><\/p>\n<p style=\"text-align: justify\">Both prefix and postfix expressions do not need precedence rules, association rules or parentheses and have simple grammar expressions and straightforward recognition and evaluation algorithms. This is the reason why they are generally used during computation.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2.1 Reverse Polish (Postfix) Notation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As already discussed an infix expression can be converted by placing the operands first, followed by the operator rather than in between as in the case of infix expression.<\/p>\n<p>&nbsp;<\/p>\n<p>Example:<\/p>\n<p>Infix &#8212; (3 + 4) \u00d7\u00a0 5 \u2013 6<\/p>\n<p>Postfix&#8211; 3\u00a0 4\u00a0 + 5\u00a0 \u00d7 6\u00a0 \u2013<\/p>\n<p>&nbsp;<\/p>\n<p>Parsing reads left-to-right and performs operation on two operands<\/p>\n<p>Example<\/p>\n<p>3\u00a0 4 +\u00a0 5\u00a0 \u00d7 6\u00a0 \u2013<\/p>\n<p>7\u00a0 \u00a0 5\u00a0 \u00d7 6\u00a0 \u2013<\/p>\n<p>35\u00a0 \u00a0 \u00a06\u00a0 \u2013<\/p>\n<p>29<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This method of representing the expression is called <em>reverse-Polish<\/em> notation after the mathematician Jan \u0141ukasiewicz (Figure 9.2) and the method forms the basis of the recursive stack used on all processors. Jan \u0141ukasiewicz also made significant contributions to logic and other fields of computer science.<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-146 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55.png\" alt=\"\" width=\"249\" height=\"317\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55.png 249w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55-236x300.png 236w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55-65x83.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-55-225x286.png 225w\" sizes=\"auto, (max-width: 249px) 100vw, 249px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p>Now let us summarize the benefits of the <em>reverse-Polish<\/em> notation from the perspective of computing.<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\u00a0no ambiguity and no brackets are required<\/li>\n<li>\u00a0this is the same process used by a computer to perform computations:<\/li>\n<li>\u00a0operands must be loaded into registers before operations can be performed on them.<\/li>\n<li>\u00a0reverse-Polish can be processed using stacks<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0 Reverse-Polish notation is used with some programming languages, examples include postscript, pdf, and HP calculators. This processing is similar to the thought process required for writing assembly language code, where you cannot perform an operation until you have all of the operands loaded into registers.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2.2 Algebraic Expression Operations using Stacks<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">When the ADT stack is used to solve a problem, the use of the ADT\u2019s operations should not depend on its implementation. In this section we discuss the following functions that use stacks namely that conversion of an infix expression to postfix form and evaluation of the postfix expression. Now let us look at each of these functions in detail.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2.2.1 Conversion of Infix to Postfix<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here are some facts to be considered when converting from infix expression to postfix expression. Operands always stay in the same order with respect to one another. An operator will move only \u201cto the right\u201d with respect to the operands. All parentheses are removed. In other words when we analyze the conversion process we discover that<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 <em>Operands<\/em> are in same order in infix and postfix<\/p>\n<p>\u2022\u00a0 <em>Operators<\/em> occur later in the case of postfix<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The basic strategy is to send operands straight to output, output higher precedence operators first before outputting lesser precedence operators. If operators have same precedence, send them to the output in left to right order. The stack is used to hold pending operators that are yet to be given as output.<\/p>\n<\/div>\n<div>\n<p style=\"text-align: justify\">Before we discuss the steps in detail let us give the table (Table 9.1) for the incoming priority (ICP) and in stack priority (ISP) of the different operators<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-147 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56.png\" alt=\"\" width=\"628\" height=\"539\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56.png 628w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56-300x257.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56-65x56.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56-225x193.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-56-350x300.png 350w\" sizes=\"auto, (max-width: 628px) 100vw, 628px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-148 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57.png\" alt=\"\" width=\"652\" height=\"265\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57.png 652w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57-300x122.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57-225x91.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-57-350x142.png 350w\" sizes=\"auto, (max-width: 652px) 100vw, 652px\" \/><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-149 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58.png\" alt=\"\" width=\"625\" height=\"494\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58.png 625w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58-300x237.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58-65x51.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58-225x178.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-58-350x277.png 350w\" sizes=\"auto, (max-width: 625px) 100vw, 625px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-150 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59.png\" alt=\"\" width=\"623\" height=\"501\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59.png 623w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59-300x241.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59-65x52.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59-225x181.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-59-350x281.png 350w\" sizes=\"auto, (max-width: 623px) 100vw, 623px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-151 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60.png\" alt=\"\" width=\"628\" height=\"283\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60.png 628w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60-300x135.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60-225x101.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-60-350x158.png 350w\" sizes=\"auto, (max-width: 628px) 100vw, 628px\" \/><\/p>\n<\/div>\n<div>\n<p style=\"text-align: justify\">\u00a0 \u00a0The steps and simulation of conversion of infix to postfix are shown in Figure 9.3 and Figure 9.4 respectively.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>1.\u00a0<\/strong>Figure 9.4(a) shows the initial state with Stack empty and the infix expression <strong><em>A*(B+C) \u2013D\/E <\/em><\/strong>yet to be processed. Then we scan the Infix expression from left to right for tokens.<strong>\u00a0<\/strong><\/p>\n<p style=\"text-align: justify\"><strong>2.\u00a0<\/strong>Figure 9.4 (b) shows the first token which is <strong><em>A<\/em><\/strong> given as output (as per step 2 of the algorithm)<\/p>\n<p style=\"text-align: justify\"><strong>3.\u00a0<\/strong>Figure 9.4 (c) shows the pushing of the operator <strong><em>*<\/em><\/strong> into the stack according to step 4 (b).<\/p>\n<p style=\"text-align: justify\"><strong>4.\u00a0<\/strong>Then the open parenthesis <strong><em>(<\/em><\/strong> is pushed onto the stack as per step 3 of the algorithm.<\/p>\n<p style=\"text-align: justify\"><strong>5.\u00a0<\/strong>Similarly the next token the operand <strong><em>B<\/em><\/strong> is given as output and the operator <strong><em>+<\/em><\/strong> is pushed onto the stack as shown in Figure 9.4 (e ) and 9.4 (f).<\/p>\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>6.\u00a0<\/strong>Next token we see is a <strong><em>)<\/em><\/strong> which means all entries in the stack up to and including open parenthesis is removed from the stack as shown in Figure 9.4 (g).<\/p>\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>7.\u00a0<\/strong>However neither ( or ) form part of the output. As per step 4 (a) <strong><em>*<\/em><\/strong> is popped out and \u2013 is pushed onto the stack (Figure 9.4 (h)).<\/p>\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>8.\u00a0<\/strong>Now the operand D is output (Figure 9.4(i)) and then the operator \/ is pushed into the stack ( Figure 9.4 (j)).<\/p>\n<p style=\"text-align: justify\"><strong>9.\u00a0<\/strong>Figure 9.4 (k) shows E being\u00a0 the next output token and<\/p>\n<p style=\"text-align: justify\"><strong>10. <\/strong>Finally operators left in the stack are popped out in the last in first out order (Figure 9.4 (l)).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As you can see an important part of the algorithm is the comparison of the precedence of the operators that are scanned and those that are in the stack. If the operators in the stack have higher precedence than the precedence of the incoming operator then they are outputted in reverse order to which they were pushed into the stack. Then the lower precedence operator is pushed into the stack. The other important part of the algorithm is the handling of parenthesis. When a right parenthesis is encountered, we pop all operators in the stack up to and including the matching left parenthesis. However neither the open or closing parenthesis is given as output. When this step is carried out when we say matching parenthesis we mean that the type of parenthesis should also match.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>9.2.2.2<\/strong>\u00a0\u00a0<strong>Evaluating Postfix Expression<\/strong><\/p>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 The next application of stack that we discuss is the evaluation of postfix expression.<\/p>\n<p>The basic concept is as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2022 Whenever an operand is encountered, push it onto the stack<\/p>\n<p style=\"text-align: justify\">\u2022 Whenever an operator is encountered, pop required number of arguments from operand stack and evaluate<\/p>\n<p>\u2022 Push result back onto stack<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The algorithm considers two cases \u2013 namely when the operator is binary or when it is unary where the number of operands popped out of the stack depends on the type of operator. Figure 9.6 shows a running example of the use of stack for evaluating a postfix expression. In the figure we have numbered the operators in order to explain the process. Please note that the stack is a single stack. The first column shown in the Figure 9.6 is the stack. However the second column is used to show the progress of the evaluation and does not form part of the stack.<\/p>\n<p>&nbsp;<\/p>\n<p>The detail steps of the algorithm are given in Figure 9.5.<\/p>\n<\/div>\n<table style=\"border-collapse: collapse;width: 100%\">\n<tbody>\n<tr>\n<td style=\"width: 100%\"><strong>\u00a0 \u00a0 Algorithm for Evaluation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">1. Empty the operand stack<\/p>\n<p style=\"text-align: justify\">2.<strong>while <\/strong>there are more tokens &#8211; Get the next token<\/p>\n<p style=\"text-align: justify\">3.I<strong>f <\/strong>the first character of the token is an operand Push it onto the stack<\/p>\n<p style=\"text-align: justify\">4.\u00a0<strong>else if <\/strong>the token is a binary operator<\/p>\n<p style=\"text-align: justify\">a. Pop the right operand off the stack<\/p>\n<p style=\"text-align: justify\">b. Pop the left operand off the stack<\/p>\n<p style=\"text-align: justify\">c. Evaluate the operation<\/p>\n<p style=\"text-align: justify\">d. Push the result onto the stack<\/p>\n<p style=\"text-align: justify\"><strong>5.\u00a0<\/strong><strong>else if <\/strong>the token is an unary operator<\/p>\n<p style=\"text-align: justify\">a. Pop the top operand off the stack<\/p>\n<p style=\"text-align: justify\">b. Evaluate the operation<\/p>\n<p style=\"text-align: justify\">c. Push the result onto the stack<\/p>\n<p style=\"text-align: justify\">6. Pop the stack and return the result<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Figure 9.5 Algorithm for Evaluation of Postfix Expression<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-152 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61.png\" alt=\"\" width=\"613\" height=\"223\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61.png 613w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61-300x109.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61-225x82.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-61-350x127.png 350w\" sizes=\"auto, (max-width: 613px) 100vw, 613px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-153 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62.png\" alt=\"\" width=\"599\" height=\"455\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62.png 599w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62-300x228.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62-65x49.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62-225x171.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-62-350x266.png 350w\" sizes=\"auto, (max-width: 599px) 100vw, 599px\" \/><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-154 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63.png\" alt=\"\" width=\"620\" height=\"424\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63.png 620w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63-300x205.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63-225x154.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-63-350x239.png 350w\" sizes=\"auto, (max-width: 620px) 100vw, 620px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-155 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64.png\" alt=\"\" width=\"609\" height=\"420\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64.png 609w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64-300x207.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64-225x155.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-64-350x241.png 350w\" sizes=\"auto, (max-width: 609px) 100vw, 609px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-156 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65.png\" alt=\"\" width=\"579\" height=\"414\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65.png 579w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65-300x215.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65-65x46.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65-225x161.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-65-350x250.png 350w\" sizes=\"auto, (max-width: 579px) 100vw, 579px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Figure 9.6 A Running Example for Evaluating Postfix Expression<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Figure 9.6(a) shows the initially empty stack and the input postfix expression with 8 operators (given below) which we wish to evaluate. The expression will be read one by one, left to right until the end of the expression is reached.<\/p>\n<p style=\"text-align: center\">3\u00a0 6 3\u00a0 +\u00a0 5\u00a0 5 6\u00a0 \u00d7\u00a0 +\u00a0 8\u00a0 \u00d7\u00a0 \u2013\u00a0 8\u00a0 6\u00a0 \u00d7\u00a0 + +<\/p>\n<\/div>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">\u00a0 \u00a01.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">As long as the tokens from left to right are operands (3,6,3) the elements are pushed onto the stack one by one ( Figure 9.6 (a) \u2013(c)) \u2013 step 3 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">2.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">The next token is a binary + operator (1) (operators are identified by numbers in Figure 9.6) and therefore we pop the top two elements from the stack 3 &amp; 6, perform the operation and push the result 9 back on to the stack (Figure 9.6 (d)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">3.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">The next three tokens are operands and they are pushed onto the stack (Figure 9.6 (e)\u2013(g)) \u2013 step 3 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">4.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now the next token is a binary x operator (2) and therefore we pop the top two elements from the stack 6 &amp; 5, perform the operation and push the result 30 back on to the stack (Figure 9.6 (h)) \u2013 step 4 of the algorithm<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">5.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we again see a binary + operator (3) and therefore we pop the top two elements from the stack 30 &amp; 5, perform the operation and push the result 35 back on to the stack (Figure 9.6 (i)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">6.<\/strong><span style=\"font-size: 1em\">The next token is the operand 8, which we push onto the stack (Figure 9.6 (j))<\/span><strong style=\"font-size: 1em\">\u00a0<\/strong><span style=\"text-align: initial;font-size: 1em\">\u00a0step 3 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">7.\u00a0<\/strong><span style=\"font-size: 1em\">Now we again see a binary x operator (4) and therefore we pop the top two elements from the stack 8 &amp; 35, perform the operation and push the result 280 back on to the stack (Figure 9.6 (k)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">8.\u00a0<\/strong><span style=\"font-size: 1em\">Again we see a binary &#8211; operator (5) and therefore we pop the top two elements from the stack 280 &amp; 9, perform the operation and push the result &#8211; 271 back on to the stack (Figure 9.6 (l)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">9.\u00a0<\/strong><span style=\"font-size: 1em\">The next two tokens are the operands 8 &amp; 6, which we push onto the stack (Figure 9.6 (m)) \u2013 step 3 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">10. <\/strong><span style=\"font-size: 1em\">The next token is a binary x operator (6) and therefore we pop the top two elements from the stack 8 &amp; 6 perform the operation and push the result 48 back on to the stack (Figure 9.6 (n)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">11. <\/strong><span style=\"font-size: 1em\">The next token is a binary + operator (7) and therefore we pop the top two elements from the stack 48 &amp; -271 perform the operation and push the result &#8211; 223 back onto the stack (Figure 9.6 (o)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">12. <\/strong><span style=\"font-size: 1em\">The next token is again a binary + operator (8) and therefore we pop the top two elements from the stack -223 &amp; 3 perform the operation and push the result -220 back onto the stack (Figure 9.6 (p)) \u2013 step 4 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">13. <\/strong><span style=\"font-size: 1em\">Finally we see that all tokens have been handled, and the stack is empty, therefore the result -220 is on top of the stack (Figure 9.6 (q)) \u2013 step 6 of the algorithm.<\/span><\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">In this example we have not considered an unary operator but in that case only one operand will be taken from the stack processed and pushed onto the stack. The algorithm finishes only when all tokens of the input have been handled and the stack is empty.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">As you have seen in both these applications stacks are used to keep track of the elements that are to be processed. While in the first application the stack is used to store operators to keep track of precedence, in the second application the stack\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">stores the operands to ensure the recent operands are used with the associated operator.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Discussed some important applications of Stacks<\/li>\n<li>Explained the handling of Algebraic expressions by stacks<\/li>\n<li>Outlined the conversion of infix to postfix using stacks<\/li>\n<li>Discussed the evaluation of postfix expression using stacks<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Applications of Stacks \u2013 I<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/k0PT3yI7pG4\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-157 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66.png\" alt=\"\" width=\"740\" height=\"458\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66.png 662w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66-300x186.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66-225x139.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-66-350x217.png 350w\" sizes=\"auto, (max-width: 740px) 100vw, 740px\" \/><\/p>\n","protected":false},"author":3,"menu_order":9,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-142","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":8,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/142\/revisions"}],"predecessor-version":[{"id":916,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/142\/revisions\/916"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/142\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=142"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=142"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=142"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}