0 STACKs AnD QUEUES La. Inthe previous chapters, we discussed a ques allow one to insert and delete raged a arrays and linked lists. These linear data peal. However, there are some applications that istany onion: be beeen “eetion of an element to occur only at one end, rare ada srichae ye ae ee Be edie tht fill uch requirements are socks andquees Ths peagiontoe = soorant,simple and commonly used data structure inc cate ee Ce Inthis chapter, we shall discuss about the sta sion, operations and applications. 41 STACK Astack is a linear data structure in which inserti mly at one end. This end is often called the top of the dement takes place only at one end, the ‘elements can only be remove tatin which they were added to the stack Due to this reversing charact tlered to as Last-in First-out (LIFO) & k data structure is as and queue data structure, their represen- ind deletion ofan element can occur stack. Since insertion or deletion of an nthe opposite order from eristc, stack is frequently ata structure sckof books on a desk, You can get Aneveryday analogy of a stac a ea ry skconly at the top of the stack. Addi abook only from the top and you can easily put anew boo - es ee ae a ass renova bok fom thbonembe SEEPS 0, yuma re ee tks from the top ofthe stack ™ he tn ferent stacks in your daily ie Tike astacks ‘alableto be removed. Similarly, YOu etapa ingen at tt staysina cafeteria, a stack of cms eae i. Ifyou wanttoremove am Which you can only add or remove an object atthe i the objects that lie above it. hichis not at the top, you must rst 7— f the stac is makes t encounter dil topisastac move all 201 “St ond Queue e "i 1\ 3. hee , Stack of Coins Stack of Plates Can of Tennis balls Stack of Books Fig. 4.1 From the above discussion, it is clear that stack is the way you group things together ty placing one thing on the top of another and then removing things one ata time from the top oft stack. Itis amazing that such simple data structure is a critical component of nearly . that is written, ¥ : Logically, a stack can be visualized in different ways which may grow in the upwardor downward direction or horizontally in the left or right direction. The following figure F wi bs how stack can be visualized in different ways along with their top that change according! ” gen 4 Xx musics I. Top—| X xXIt t © . lhe cme xe edi } 1 ; (A) (8) or ; Fig. 4.2 - Different logical representations of stack with their Top (Here X represents some element Although any of the above logical form of a stack can be used but we generally use th convention of having the top in the up direction (Fig. 4.2) which we will use throughout the book 4.1.1 BASIC STACK OPERATIONS ‘ The basic operations that can be performed on a stack are push, pop and stacktop ¢ peek. [Link] PUSH ‘The push operation inserts an element at the top of the stack. After the push operation. the element that has just been pushed onto the stack becomes the top .Each push operation increases the number of elements on a stack by one. Fig 4.3 illustrates the push operation on a stack. 202 Data Structures using C++ ahe Xk. or e = ‘ Tor— |i B Pushed or . th Notte stack TOP—>| 5 A Before Push ~_| ish Operation fter Push Op a After ii ation Fig. 4.3 - Representation of a push operation n the Fig eer In th Fig43,the stack initially contains two elements A and B, After performing the ation, the new element C is inserted at the top leaving the other elements below it. ugh space for the nnot be Before performing the push operation, we must ensure that there is en clement in the stack. Ifthere isnot enough space in the stack then the new element Jin the stack and stack is in overflow state, 41.1.2 POP The pop operation on lement from the top of the st ng the top elem the push operation. In this operation astack is just the reverse of mitto the user. If stack contains more ack, the next older element in th tack by one. tack and ret nent from the yumber of € move the el element then after removin eration reduces tl comes the top. Each pop oP ments i ter Pop Operation @) ( ! ition { eornine 7” PEA Jements A, Band ©. ATE j aaath , ai ice lee BBD In the above Fig. 4 pet } Performing the pop operation top (Fig 4.4B). NOTE : No element other tha sp or pop operation: form the POP now pet P p the 10P ast On removing the ! Stacks and QueuesOperation on the empty stack then stack is in underflow state [Link] STACKTOP OR PEE In some situations, you may want to inspect the element at the top of a tack w tho . actually removing it. This is accomplished using the stacktop or peek operation. The ckiopin a Peck) operation returns the element atthe top ofthe stack without altering the stacy. Pi 1 Performing this oper ation, there is no change in the number of elements in the stack Ce Reading top element [ without removing 7] top| c= Top—+| ne aol B 8 at thi tothe A A Before Stacktop Operation After Stacktop Operation 4.1. (A) (B) Fig. 45 - On performing stacktop operation | repr a From the Fig. 4.5, itis clear that after performing the stacktop operation, the top bx elements read without removing it on If the stacktop operation is performed on an empty stack then the stack is in under a state. 41. [Link] STACK OPERATIONS - BY EXAMPLE We shall now explain how a series of operations (push, pop and peek) are performe whi stack. For this, we start with an empty stack and then push elements with values 20 and 15 (mi the stack (Fig. 4.64, B). At this point, the stack contains two elements with number 15 at the pes We then perform the pop operation and the element with value 15 (i.e. one at the top) is ree from the stack. Now the stack contains only one element (See Fig, 4,6D). < Push - 20 Push - 15 Pop - 15 Push sta wt C-| th 4 . n : 1 ™ PU 2 2 2 15 2 ] 1 1|_20 1L_2 | be TOP =0 TOP TOP =2 ToP=1 - (A) ) (c) iy Sta Data Structures using C++Push =40 “ Pop . 49 ax a oy 5 3 {| a 7 1 ae ‘For =2 1 2] 0 TOP =3 1 a e (F) TOP=2 a P (6) Fig. 46 tH) gain after pu ele Again after pushing the elements with aly .6£,F) and this elements removed when Shipp topmost element is 40 (F op ope ig ement with a value 20 at the bottom chee is performed again, Now stack contains element with vi his point, we perform peek ith value 30 at the top (Fig. 4.6G), is po Perform peek operation, which retum the top elemer Pree he user without removing it jp element of the stack i.e. number 30 4.2 REPRESENTATION OF A STACK A stack can be represented in memory using several data structures but usually itis resented using one-dimensional array ora singly linked lis. The choice of representing stack as Sat ‘uray or a linked list depends upon whether the size of the stacks fixed or not. Ifthe size of the suck is fixed then array representation of stack is more efficient and convenient as compared to ed list representation of stack. We shal discuss both these representations in the folowing jow sections 41.2.1 ARRAY REPRESENTATION OF STACK -ican be done using one-dimensional array on The most primitive representation of astack oe Se pie — ' she ay aege hes a ane smmnodate) must De predetermined before 9 fasiieaimiber vf elements that a stack can 2° ed Performing any operations. cas an array, We maintain ano -imensioal anny Sea . Jnorder to represent stack a5 an TT gs inseted element (.e the Opal ene rp ack of th inde FT ye MAXSIZE that cons 2 Va P Yaiable TOP which keeps t12ck OH ihe variable 2 aoe e two, we sack $ can accommodate. niall, Ce eno elements tha ase See element, thenthe val of number 0 je has a valu ins sing] Which identifies the maximum ain j thestack is empty, TOP varia? TOP is 1 and so on. PUSH: emented by | he sack, he variable TOP is inetee c as cl yew values ent on at actally happens is that ned vale isa othe stk Vary clement becomes the topof HES j index of — jranew elem Eacl we pus Each time We Ps ont ent and ‘efor the element isinserted 0" "the next available array ¢l° “Sets ond QueuesThe structure of array $ with MAXSIZE =5 is shown in Fig. 4.7. The of elements that can be stored in array S are 5. The first ele MAXIMUM Mum second element is p) ment will be placed at inder laced at index 2 andthe las clement is placed at index S (i.e, Maxey a t ae dfasemnci4 ah 10 fone r6pe4 (A) 8) (c Fig. 47 Initially when the stack is empty, the value of TOP variable is 0as shown is ig. 4.71 On performing the push operation, the element with value this array element becomes the toy Clements in the stack. Fig. 4.7C shows the presence of S elements in the st the stack array $ is now fully occupied so now discuss the al 10is inserted at the index 1 and inde P of the stack (see Fig. 4.7B). Similarly, we can insert tack since TOP: > no further insertions is possible onto the stack. We gorithm for performing push operation on a stack Algorithm 4.1 : PUSH (S, TOP, MAXS! Tepresenting stack with MAXSIZE elements, The v ¢lementat the top of the stack. This algorithm insert 1) - Given S be a one-dimensional amy ariable TOP holds the array index of the 's ITEM at the top of the stack. 1. [.check for stack overtiow} I TOP = MAXSIZE then Write “overtiow" return [End of If structure} 2. TOP ¢ TOP +1 [Increment TOP] 3. STOP] <— ITEM {Insert ITEM at the top of stack] 4, Return Inthis algorithm, we first check whether there is rooy not. For this in step 1, we compare the value of TOP. stack is full which represe min the stack for the new ITEM ¢ with that of MAXSIZE and no insertion can take pl If they are equal the s overflow state ated, lace and appropriate er message is sing Co ‘Daa Structures Cor index 5 iS decrement 30" as the index 5 rer stack, not U If empty sts V arrayNUmbey * 1, the IZ) (A), x of ore As hall ny re there is room for the new it Min the ontains the index of the aay Sak tenia step, TOP is incr ITEM at the TOP of the stacy. “Te the new rp rem ented by I so “Mwillbe inserted. Then in step yn performing pop oper: ation on the stack Ck, th gemember that v : P 7 lement fi ariab P ec Tom the top ofthe stack is re- ; i mi : OP contains an index of the array element ve isat ‘s peo schetation What actully happensis thatthe aay element with 1 and TOP is decremented by 1 ‘Once an elements popped k, the element is no longer availabe onthe stack although the value remains in the yntained in TOP is removed nsider the stack as shown in Fig 4.8A with five element and TOP=Si.e at the top of the stack. When you perform element with POP operation on the stack, TOP is ) of the new TOP element. This makes 8B ). Notice that array element 45 with 1 and now it contains the index (5 ew value at the top of the stack (see F n the stack only alters the mains untouched in the array because popping a value from the stack underlying array 7° or ¢ TOP—* 5 45 4 2 aa ie TOP =5 ; (A) Fig. 4 oty and TOP = 0. This represe be emp «will stac t erflow sta). ee ements. njace (unde — If we pop all the elem ions can take i vent from t empty stack and no further dele nO tack anda an algorithm maintaining st Rs ea one nose valueisat the PT I any. sg, TOP) Givers Semen sea local variable : (S, he array Oe Here, We Atgorithim’ 4.2: POPs, of the a ay S: ins an i fromart Yanable TOP contains element Algorithm removes the 10P °ryed thedeleted clement which is" fe 1 sncortiow state 2 [heck tor MTOP = 0 then = Write *Underfiow’return [End of If structure} 2. ITEM < S[TOP] [Copy TOP element to ITEM] 3. TOP < TOP -1 [Decrement TOP] 4. Return (ITEM) Inthis algorithm, we first check whether there exists any element to be removed from th stack or not. For this in step 1, we check whether TOP = 0 or not. If TOP = 0, then the stack empty which represents an underflow state and we return without deletion. If stack is not empty then in step 2, we first assign the TOP element to the local variable ITEM and then in step 3, we decrement the value of TOP by 1. Finally the deleted ITEM is returned. Note that if before performing pop operation, the stack contains only one element then after pop operation it becomes empty and TOP = 0 af PEEK: The peek or stacktop operation returns the element at the top of the stack without altering c the stack. Algorithm 4.3 : PEEK (S, TOP) - Given S be a one - dimensional array maintaining stack and variable TOP contain an index of the array element whose value is at the top of the stack. This 7 algorithm returns the top element from the stack Ys 1. [Check for underflow state of stack] { If TOP = 0 then Write “ Underflow” return {End of If structure] } 2. ITEM < S[TOP] 7 3. Return (ITEM) This algorithm is similar to algorithm 4.2 except that we simply inspect the TOP element of | the stack without removing it Program 4.1 : Program to implement basic operations of stack as an array using objects and classes in C++. In C++, the array index starts from 0 instead of 1 jude process.h> WAX 5 //Maximum elements allowed 8 stack Data Structures using Co=r 1 from the € Stack ig ot empty ep 3, we ent then ent of sand 008 jat top) poccack( 1{ top = «2 wea push (ine); 1) / Semana jot pop () 4 making int peek ()) int isempty(); woid display (); Tatack() {cout << empty stack "Destroying stacks ) eid stack: :push(int item) if(top == MAX-1) cout<<"overflow : stack is full"; else is { at top ++; A s{top] =item; } ) int stack: :pop() i int item; item=s [top] top \ return (item) int stack: :peek() { int item; itemss [top] 7 | Feturn (item) 7 ? oie stack: :aieplay () cack 27 coutecs\n Contents of © for(int 1=0;4<=toP? cutcee [i] <>schoice ; switch (choice) { \t [Link]\t K\t 4:Dieplay\t §.meit case 1 coute< cin>>val; [Link] (val) ; break; case 2: “Enter element to push = *; if (01. isempty() cout<<"underflow ; else { int item=[Link](); cout<<" Element popped =" } break; case 3: if = 1) stack Empty"; //atack not empty < ye the topmost element (15 vtion Fig. 49C).The Sin this case soni : ©). The pop() member functions mas sek and retumttot Pens) member urn can etn chek derflow condi ‘op =-1), which means that stac nl : i remove any element from the stack gesaiement . item = peek), again( read the contents of topmost element of the stack without ch fecaling function. This member function also check the un ain senber function. flow con estatement , 1. display (); {gy the contents of the stack when the value choice is 4, Finally, when user en doice,he exits the program. 4 3 2 |) 0 5 i point of view nf a of stack from CHF top tas dex Inthe previous S05 ery si u representation of 20K em a array's size. If t aycan a Eee more elements thatthe” cab vethis problemis 105° gown sentation of stack ilable , sation of BY presenti’ nest Inthe linked 210 hat consists of the act” Socks and Quewes ai data itePoints to the next element of the stack. The pointer called TOP will be directed to it. The | is set to NULL figure Fig. 4.10 depicts a stack cont. one - dimensional stack array first n last node is the bottom An empty stack in this represent, ining four elements with 40 at and its corresponding TOP (or HEAD) node is considered to be the toy ‘ation will have TOP = NULL. The linked list representation. P of the stack n of the stack and jit ink following the top when represented ay [laa t eames | 30 Ty] 4) 40 |«-top t B)2* so 2 [1] 21g 20 c a 10 10 |X (A) Fig 4.10 A - Representation of a stack using 1-D array (B) ining bottommost element. Fig. 4.10B - Linked representation of a stack In the linked stack, first node on the list is the current elemen the stack and the last node is the node cont: TOP pointer instead of conventional HE .e. the element at the top of Observe that we are using ‘AD pointer that points to the first node of the linked list. ‘The push and pop operations are performed at the front of the linked stack. On perform- ing push operatiot Femoves anode from the front of the linked stack .The following figure Fig operation on the li TOP in, a New node is inserted at the front of the linked inked stack. stack. The pop operation 4.11 illustrates the push 40 | -—>| 30 | -+ 0] -+_-o x (A) Before Push Operation TOP 4 32 | +}+—>| 40 | -+—-[ 30] -1 Jy] - +i x] (A) After pushing 32 onto the linked stack Fig. 4.11 From the above figure, we observe that new node with a value 32 is inserted at the Data Structures using C+sgopotie linked stack and Top kang Toe figure 4.12, ltustrates the Pont wing TOP PETation on md le Stack, as Tepre “sented usis ing linked list TOP (A) Befor mer Pop Operation 40> | DG — sl a | (B) After Popping element from the linked stack Fig. 4.12 ‘" From the figure 4.12, we observe thatthe first ne pointed to by TOP is removed and vg BROW points tothe next node Inthe linked stack, the sizeof the stacks notimportant because this representation allows i. jmamic structure instead of static structure as with rays. Whené isles sdsan a smade available from the availability ist and when any nodeisnole anid h ‘ndreturned to the availability list. The pac pa ray represeatation of . ided availability list contains enough nodes Oi te ae tropes cheek for verlow incase o7PISTOP ST. yom acme here MAXSIZE contains the maximum ed in linked stack as the eof the stac Such overflow condition need not rea a MAXSIZE) is not maintained in this ® ee pop operations on 8st e algorithms !¢ We shall now discuss the al8° 1p -Givenainked stack with ted by a linked list. eaiit ror, avanlaTt a pointer pots tothe fist jst. The: tack Algorithm 4.4: PUSH ll eof te bak TEM ‘onto the stack: Printer TOP pointing 10 the gorithm pushes "ode of the availability Hist. °° e | 'AVAIL € LINK (AVAIL) [Update AVAIL pointer} INFO (NEW) ¢~ ITEM [Copy ITEM into INFO part of new node) LINK (NEW) <= TOP [Sot link part of new node to top] TOP «~NEW [TOP points to new node} Return Neneae In this algorithm, we first get a free node from the availability list and store ITEM into thi J then push the node at the front of the list Before pushing an ITEM, we first check whether there is a node available in the availabil ity list or not. For this, in step 1, we check whether the availability list is empty or not. Ifitis empty, then the appropriate message is displayed and return. In step 2 and 3, the new node from the front of the availability list is cre: ed and AVAIL pointer is set to point to the next node of the availability jist. In step 4, we copy the ITEM into INFO part of the new node. In step 5, the new node point to the original top node of the stack and in step 6, the TOP pointer is set to point to this new node TOP [eh Ram| e+ ign L fart] ]}-—+[ von |} [ean] Fig. 4.13 Pushing an ITEM with INFO = ‘Ram’ in the linked stack Now we shall discuss an alogrithm that performs POP operation on linked stack. ‘Algorithm 4.5 : POP_LINKSTACK(TOP, AVAIL) - Given a linked stack with pointer TOP pointing to the first node of the linked list. The AVAIL pointer points to the first node of the availability ist. This algorithm removes the top element of the linked stack and assign it to the Jocal variable ITEM. Here ‘SAVE? is a local pointer variable which points to the deleted node. 1. [Empty list?) It TOP = NULL then Write “Undertlow” return: [End of i structure} 2. ITEM «INFO (TOP) [copies top element of stack into ITEM] i 3. SAVE © TOP 4, TOP < LINK (TOP) [Reset TOP to point to the next node in linked stack] 5. LINK (SAVE) <— AVAIL Data Structures using C++ = 214inthis algorithm, before perf yornot. If stack is e setting opty or isempty, then Tope ny PoP oman w P € a" rom the algorithm without fist check /f S Popping 0 We displ ether t épiscopied into variable ITEM eine In sep the Noe appropiate mess 3 jedstack and then in step 4, we reset inert SAVE Pon atthe lement pointed Tedstack. In step 5 and 6, the ai TOP pointer soi rhe Potten fevfthe free storage ist and pointer AVANT on PY SAVE pointers : TOP SAVE S updated according! * x ; ~> Amit | <1 Ven | +} Cap] x | Fig. 414 Popping an ITEM from the ack Program 4.. Program to implement stack using linked isin C+ finclude finclude finclude fdefine NULL 0 struct node { int info; node *link; clas { Priva node Public link_stack() { top: void void void h link_stack top: petructoF y/ 20 ace NOLL: push (int)? pop()? ee aispley()' , geste" link stack)’ main ()newnode. The statement, newnode->info = item; Stores the value of item in the info Part of new node pointed to by newnode . The Statements s Rewnode->link = top; top = newnode; causes the new node to point to the first node and then top pointer points tothe new first noe top Old link Fig. 4.15 - Pushing an ITEM with INFO = 10 in the linked stack. This newly created node becomes the first node of the linked stack and top points to it. Ifthe choice =2, then the pop operation is performed using member function call [Link](); In the definition of member function pop (), we first check whether the linked lst (repre- senting stack) is empty or not. Ifit is empty (ic. top = NULL), we display underflow message and Tetum, otherwise we proceed with the procedure of removing top element (first node of linked list) from the stack. To remove top element of the stack, pointer variable top is made to point to Nextto top element using statement, top = top->link; To release the memory of deleted node, we first need to store its address (using pointer Saye ) and then release its memory using delete operator. If choice =3 then statement, [Link](); on invocation displays the info part of all the nodes from the beginning. Finally, on exiting the Program, the object sl is destroyed and destructor (~linkstack( ) ) is invoked that releases the memory allocated to the nodes of the linked list. 4.1.3 APPLICATIONS OF STACK A stack is a widely used data structure in modern computers. It is used in all those applications in which data must be stored and retrieved in last - in first -out order. There are ‘numerous applications of stack that include + Reversing Data * Recursion * Evaluation of arithmetic expressions + Backtracking * Delimiter matching (parsing) * Sorting data using quicksort * Processing functional calls * Adding very large numbers Data Siructures using C+— de, oit pre- and Iked at to inter z the s the hose are 218 pal now be discussing some of). 1 REVERSING DATA Toreverse a Biven set of data y are excha . © nee e gerement are exchanged, second and sec, "6d (0 reordey the ‘Suppose we hav we ws "IN Such a way thatthe first and. opt Weshall now disc ag decimal tO binary. exchanged ‘and so on for all other NON reversing it wou uld be EMOC std REVERSE A STRING Astack can be used to reverse thet ! e Se the characters ofa string, This canbe ache character of the string onto tring. This can be achieved by simply sgshing © the stack , which later can be we. . later can be popped from the stack one one. Bec et of its Last-in First-out Property, the stack reverses the characters of the string See Fig. 4.15). Pop Operations (a a ToP—>7 E 7 1 6 M 5 ° 4 c 3 ‘ et | 2 E ee ee I Fig. 416 kin o using Sta erses the string Thefollowing program reverses Ninclude ? oy main! char atack(20)7 //8t®°°o¢ top ° int tope-1; bane le main() (char 1)? void rever SlrserO1 char 5 eae eae t=? = 219 [Link] (str, 25)? : se(atr)? ’ NS od Queues thattering reverse a # Noid Feverse(char str(1) //detining function to void push (char); shar pop(); int Leempty(); for (int 4 = 0) 4 < atyien(str)) i¢+) { char ch = str(i); push (ch) ; while (1isempty()) coute Ramesh kumar return (0); ramuk hsemaR 413.12 CONVERTING DECIMAL TO BINARY Although decimal numbers ‘echnical applications require number used to convert a number from decim are used in most business applications, some scientific and 7s ineither binary, octal or hexadecimal form. A stack can be nal to binary/octal/ hexadecimal form, 2 14 2 (ay ee Pushing 4 J led = 1). | orcer 3 1 é et Die. | — o -@ Last element ye a a Sacre ing oy ate be pushed a Fig. 4.17 StackBe foaseott decimal ny eter er eqavacat ot gece 100-Tya 8 push ee eT Biven decimal my Simply ie rem; ledly divide the decimal sit inder . of eac Consider an example of a deg ee kan vision oto the Whole: Stack and result so obtained J jasteremainder whichis a Pushed on geno 14, F eremail ‘ON the gt Or i a nder Which sagan pont “8 Onapn dg oY re Bris notTedvCed 100. The dag tom he aan dividing ye iC lagrammaticrepreses ck This process 2, we Bet 3 as quotient sentation fg ons mies until the given > this operation is shown in Fig, 4.16 When we pop off the stack ¢ stacl k completely, bi juivalent binary numt wary number 1110, ne , We et the 4132 EVALUATION OF ARITEMETIC ett eq Astack is very effective tac data struct orig MERE. ture for evaluating arithmetic etic expressions inthe pro- Anarithmetic expression consists of o cmstants and the basic set of operations Tice 4 (at i fon) aia eee ay and Nexpon , (addition), -(subtraction), *(multiplica " a q ah aa entiation). In addition to operands and ona ne re cae fons may also include parentheses like ‘left parentheses (() and right . aticas (0) Fe and right parentheses ( ) ). For ample: PRESSION A+B*tC i ad A * (BC)/D @) seyalid arithmetic expressions ’ |, morertoevalate express } forarithmetic expressions. The precee ‘aponentiation operator (*) has the highé Joperator which is then followed by addition (+) and picid me De sression, when te operazors of Sa Pp | lowest priority . In any parentheses free expression, when per + to ight except incase of POF Vc oie a ? tase en withthe useo i ‘default precedence rules can get mitten ¥ aware of the standard precedence ru Fence rles for the five basic arithmetic operators ae lowed by multiplication (*) and division -) operators that have the ns, one needs to be est priority fol parentheses toverw PRECEDENCE Highest cand * (exponentiation) * (multiplication), [(division) action) +(addition), -(subl ate the €xP" sor i Now, when we evaluate ultilic ion operat cause # BC is computed first be“ : operator (+) 3-c)!D Inexpression (2 ‘end Quewesby enclosing the subtra highest and hence the esultis they ‘ction operation within parentheses, the priority of the operation becomes Sub expression B -Cis computed first which is then multiplied by Aaand the n divided by D, A* @® ~¢ D NY ° oe 2 AN a This method of writing arithmetic expression imposes difficulties when evaluated by apace Thisis because we need to scan the expression from left to right repeatedly and hene isinefficient A better way is to a) First con vert the given expression into special notation b) Evaluate the expression specified in this new notation In both these steps, stack data structure and then is used to evaluate expressions in computers [Link] NOTATIONS FOR ARITHMETIC EXPRESSION ‘There are three notations to represent an arithmetic expression : infix, prefix and postfix. a) _INFIXNOTATION: The infix notation is a conventios Which each operator is placed between the operands. For example: A+B ,C-D. E*F G/H,1* Jet. All these expressions are in infix notation because operator comes between the operands. Infix expressions can be parenthesized or unparenthesized de Pending upon the problem requirement. The above expressions are unparenthesized the following infix expressions, A*B+OQ , D/(F-G)*4 are parenthesized infix expressions. b) PREFIX NOTATION : The prefix notation places the operators before the operands. For example : The expressions + AB ,- CD, *EF ,/GH, * IJ ete. axe in prefix notation. This notation was introduced by the polish m Lukasiewicz and hence often referred to as polish notation ©) _ POSTFIX NOTATION: The postfix notation places the operators after the operands. For example : The expressions AB+, CD-,EF*, GH/,IJ* etc, ‘are in postfix notation. Thi: as Reverse polish Notatio nal way of writing an expression i and athematician , Jar s notation is just reverse to the polish notation and also known m (i.e. RPN), Data Soractres ssing Cs yjowin fol step * steP 2 we get Postfix . ands,Is. an wn ‘Toconvert the infix ¢, Bowing se °XPression step 1- Fully parenthesize step 2 Convert the sub ex ction *dopted for ine Veit parents bby taking into consid Ca pawO® Arte oper fe ca st rns EXPRESSION is comand MERC asa single” POS tation by putin gp 3. Fully remove allthe ge MSL open Rapa Tounderstand these steps, — ession sifix expression. * Consider the following inf A+B cep i exprvedcn ant eco After performing step 1, the g expression becor (A +((B/O)*p)) — Instep 2, we first convert the inne lerMOst expres (A+(BC/)*p) sion into postfix notation as Then we convert the expression in the next outer bracket into postfix re a notation. Now w (A +((BC/D*))) Then we convert the expression in the outermost parentheses into postfix notation, Now reget (A(@BC/D *)) +) Finally in step 3, all the parentheses are removed and we get the resultant postfix expr im, ABC/D*+ Similarly, we can convert inf ‘ise i s placed bel Xatix conversion is that the operator's P at, fix expression to prefix exp fore the operands rather th ersions are Some examples of these conv Infix Notation Prefix Notation a AB oe 1+ ABC (a+B)/C Pacoima AtBAC is | (at) +(0-°) (arpec)*(E-DF)From the above three notations, we observe the following points The operands in a postfix or prefix notation occurs in the same order a in the comes ing infix notation, only the position of operators is changed The expression in postfix / prefix notation does not require use of parentheses because » actual order of the oper determi ions to be performed on evaluating the expression is ¢ ed by the position of the operators and operands in the expression, Out of three notations that we have discussed , postfix notation has certain advan over other notations from the computational point of view. The main advantage is that it evaluated efficiently in computers. While evaluating a postfix expression, we need not requin scan the expression from left to right several times, but exactly once. Therefore, evaluation of arithmetic expression in infix notation is a two step process. First we have to convert the expr sion into postfix notation and then evaluate that postfix expression. In each step, the stack structure is used to accomplish these tasks. We shall now discuss the algorithm for converting infix expression into a postfix exp and evaluation of a postfix expression using stack data structure 4. 2 CONVE! ING INFIX EXPRESSION INTO POSTFIX EXPRESSION Before discussing the algorithm for converti postfix notation, we make certain assumptions, The ‘an expression in infix notation to the onein ven infix expression can only consist oft basic arithmetic operators +{addition), (subtraction), *(multiplication), /(division nentiation), each of which has its own precedence while evaluation. The algorithm that converts the infix expression A into its equivalent postfix expres only needs to shift the operators to the right and possibly reorder them if the precedence of operators is different, The order of the operands remains unchanged after conversion. Wit considerations in mind, while reading infix expression, the operands of the infix expression willbe simply placed into the output postfix expression in order and the operators will be tempora stored in a stack until they are inserted at the proper position into the output postfix express Since infix expression may contain parentheses that changes the order of evaluation so to hand Such situation we also need to store left parentheses along with other operators. The algorithm starts by pushing a left parentheses onto the stack and addi ig arigh Parentheses at the end of the input infix expression A, we then begin to scan the infix expression A from left to right. If the next ‘symbol in th put is an operand, it is placed directly in the ou'p' &xpression without any further processing. If the next symbol in the input expression A is Operator, we Compare the precedence of that operator with one at the top of the stack. It pel: higher priority than the One at the top of the stack then we push the input operator onversely, if the input operator has lower ore top, then we repeatedly pop operators with higher or eq from the stack and add it in the expression B. After thi j Mfduring scanning, a left pare . Parentheses is encountered whil ie pie qual precedence than the operator a! ual precedence than the input ope We push the input op jor onto the stack ses occur then we simply push it onto the stack. Ifa si ea on ning the repeatedly keep on popping operators fro" bi expreseSpong. USE the mpletely antages tan be quire to On of an expres, ck data ression N ‘one in tof the (expo- sion B of the | these vill be rarily ssion. andle right ion A jutput isan f that into at the ator tack: right nthe 224 zandadd it t0 the outpy, xp SSion, nti, The algorithm is compler svete. The complet meth a ts ‘ ; Crithm that kis emp Moun tor td POSTER Rena joperators and parenthese, 7? igen converts the input infix ex? element om sion fing Append”) ” to san | from let i ys ft to right ang Tepeat st while (S Is not empty *P8 4107 foreach a ce {Han operand is encountereg oe it "(is encountered, PUSH It onto stack Hen operator ® Is encountered then a) Repeat whi is ) Pe ile (TOS is 8N Operator with ‘Same precedence as @ or higher precedence than @) r 1) Pop TOS and append ito Pc b) Push @ ontos [End of If structure} oi") alg ‘ "XeXpression dSb a in nd Si ai represented by TOS ta "Post ouput expression 1 @PPend it to p, dof step 6 (a) loop is encountered then a) Repeat while (TOS is not" (" ) i) Pop TOS and append it to P [end of step 7 (a) loop] b) Remove ”(” .Donot append it to P [End of f structure} [End of step 3 loop) 4 Return. Letus now consider an infix expr ‘ 7 mcs D*(E-F) 7 *E"(” onto the stack and the "Pession are scanned from left tack Infix Expression ) m+B/ct+D + fi) AwB/C* + fi) A+B 4 Queuesme zameame mat +4 = se tebesteqy betyoun bob obsusiou ou spe erscx suq sbbeug excp obersr01 60 spe onthny TUp6 what obetsrox. pe jor. ox edna] bueceqeuce gpsu ouc st rp6 (0b OL rps cae (pe gy20 bobbeq yous rpc zrscx zon cau zec pre ws agcb xr xa beug 10 mpe exbiszeiou muny yous batcunpcece re cucomuscted Tu 219CK" VC Jou bmcurpcece TLUBpr baeumpcece re cucomursieq a1] spe obetsto12 sus bobbeq tou qps 2racK. suq sb- Aavu Joy bssunpcece re cuconucueg 1¢ re brepeq ouro rpc 29K. se wu 2¢cb ne spe boerpx exbuceerou suq qoce vor canac sud cpu 1 (pe arscx 8) —_pApSu su obeusuq re cucomcucg se rw ace ¥ mr «AN x IP XA IF eemMUbpA sbbeuqeq 0 [Lows spe spore pm rere cjem put wk vie + V+B\C+D.(E-E) vm VBC\tDEE-Cv.+ + V+B\C+D.(E-E) via) VBC\"DEL-C + V+B\C+D.(E-E MC) i VBC\+DEE~ + V+B\C+D.(E-EMve) VBC\+DEt- + V+B\C+D.(E-B)ve) VBC\+DEE + V+B\C+D. (ERE ve ‘VBC\+DE + v+B\C+D.(B-E)ve) ; VBC\+DE + v+B\C+DME-E)ve) vBC\+D + v+B\C+DI(E-E)v@) VBC\+D. 5 u v+B\C+M.(E-E)v@) vBC\*D 5 va v+B\CHD.(E-E)v@) ‘vBC\ Vier oe (e-b iso) vec ve oh b)v@)ee scm ern *NSTETUE ST 3 fO]]POOLP Gre Clusws JIcKey Boop 0 peectaice’ s dene oj bsncure sine for s qocror’ diene of epibe msqu® st boue" jruc op coz TE TKS 8 dnene 01 acpicjce st's aGus] borur’ s dnene of scconur poyqerz maim st 9 psuK comurce dene te qpe set betzou fo pnd s acKer gms] Aon cau cuconureL quysisut dnenee 1 hom qarjA (pe dene 12 que per berzou so Lescp mye WLour Oo} (yc dnene suq pnd s ficKer [p> |s2t bewzou tu ys betzoue main ous next Lous fpo ricKSr ComUICL IU 9 cIUCWHS" [NC Let beLzou so Jom Ape tem OF Onene re 9 counsou bycuowcus 1 wsuA 169] J116 21erstI0Ue" Que csu opectac 3 dene of zt cjeweur so cure s dene 12 (pe pL2t UG 10 JosAc" robes 1 sapicp cjeweure euret rye dione qu (pe ougeL 1u mpicp MPGA JoIAG" [U OTpEL souge* KS NUPKe erscK spicy Lo]Om2 PTEO brobers?’ pe dnens joy]Om2 LILO (E!2s-1U-p2t-ont) anncime iczcuupjce re dnens (pst me CoWG scLoze TU GAGLA qs TKS our (01 pesq) of tpe dacne” [pe usUE OF tps GUqe (HOUT Lest) sLG 20 Cpooecu Pat KBle qua eaqjeq spe Les. (01 1911) oL pe dene suq rps orpet cng spore qojenoue ms beyoued re Cae He cjoteure aus qoyot6q (LOU rpc orpct cud’ BA couAcuTOU TPE euq mypcus ecLrOUe me bee ¥ Onions fe 9 ]1ucsr. qars eruncinic 1 anpicp uci ejcuscure sue weeLseq st OVE SUR SU +3) ONENEaamey aay Grener dnene* me uceq to Fesb mac 04 porp tps pour suq tes of «pe dine We arEUNUCHU qISLEUCS re EMT MURS exacK mpetc 6 U66q (0 Kecb fiaey q LOUTD 4 Vitbonép tpe obetroue betyouneq ou drcne sus eran 1 italia $9626 (0 ps bans of tp parc dene obststioue ae Gnene obssstroue’ me my uorqreenze ay vou pact Obctanowe ecbatep. suq may seems aerate ClsweUr St Ip LM. Of pe drinc maqpont sqiCLIUE tps drone Wom qreneaouos Keoutbese (terme cpe eycuscur 91 {Pe Your of fps dene mutpont su tbe dncncy romeo mperper (ye dnene re ny] o1 uot): PeEwbPA (Cpecke mq wcboure mperpor dncnc ecube a sue su cusbrd dnene) [Link]. (qc beryouneg ou 162 9] (pe GyewGUre O (pe dene)” TexAM (CpeeKe sq Leb Sidnene ste eudnenc suq pednene: 2owse orp. obciamoue wejnge cxesre ¥ UNUIpSt of obststrou? cau pe TSI BV berjoueg ou 3 dacne: Ly pserc obeisnoue gar cau pe IC ONENE ObEKVLIOVA MAE 31 - Pokseay rehuezcurayou 6 dene (ers ¥, ucbuczcute zou yeu) (reywoe; eleweur) Qs:Apswoey ejeweus) EKOM. BEVIS y tt » TX DX LX tnsotn Deir agze isbisecurstiou urs sI20 pe necq Lebiszcure pe our suq ipo 1 PobIcs|A g dacne rz nensq|A ucbucecutcg 2 epomu rw FAB" 4°32 1° Ne 1eyrWOR 6 prusozt Gjeweur Lebiczsure (pe test” HOMEAGL IU 2oUIE biocezecq §pe zunariow suyz6e spots (pe UMUIpEL OF HCO) este [Lows que spone qrecnezton" 1c 12 cjest. par dnene quis ensnceme re edncere wpe ocem. dmc 1 sper bscxsre sue cudneneq nun vonet cau tong ctnorg. 20 51] sqqioUs| buckcre sie cudneneq SICKGE ST F UIC IU # WELOLK 20.5] ee all 20 mst wu dren w combnyer ustmouKe” ¥ LoMGL Lontce ou} pujousssriou bacsre a cozecq’ a dnene cuentce (st Kee biceecq Lousy 1 01 posiq” wistuestuue OKG,2 quts *ApGU (pC Mack biseece Kee [LOW (pe ¥ diene re youEq (0 e016 KOA ent0K,2 qa PCH ee wa pjozotactm 9 cowbmiet vernorx mpeu cabscit wa uous pe cHCUTE Fe Lou HU ctednca WOU CEU 208 NEN Oe eae b urd youn 9 ansqu® dene : — ray sue maequ® (0 pe buoceeeed |. : genie ceomuece enunyesueome]> tp enema yu mete psn (po eerewy U r oun pets yu scape 2d21c) tq pa (pe jue buuiet (0 pe samyspIe rectz ust pe snentlyan pancons mt Co+ = tt ce vewone \ Ded Ber ecu oq End \ bet sug qesinene fe node 2 10\ NE Oe iene FeO PUC : a Geren sm cyoucur os dene veabecttel® an wor around ae wg qodene Tee AOL We a «« VOLE + AUTRE mp6 exsex beep suq bob obeusroue’ (pe rouse si 4 ur obeuamou ou pe cubrd dnene spew spe dens 1? ms angeulon ec wom BEXOLN KPC qed a 3 Ue bp Tyne wor BELO 6 qednene Ow LewWOATUE spe [ser cpoUIEUE TPE dnene pocourse omsbr Th eo a re your ye UMP OL FOUN TO qpednene qoctorece i) inene re" YF GETEIE U4 eur st rp BOUT Ld vexr ojget cjeweur B pecouse? (P ysTued OM G|SWEULe Y" BCL «gust beyousnué rpc qednens ol [plows qpe BAe 33" we opzeLA MF beisniou ps cI5ts a qyc dice wu}esT}A COM we 433 A EOL wes EBOML weWs | ! 4 | pjc jo | TyTete[o| oycjeweure mips donc phoue ext ojqst cjcuseur pecouee 1H ¢ courmmue INOLG (PSU OUS 6 pracy qednenc obstsrrou teqnese gps Unp ye 6]6u6Ur LOWS fp6 [LOU cureur thous 1p wour OL pe dre your oy spe dren JGUIGUE {PEU TSE LSLOA quips den “pe pednene obet "13 DEONENE 3 sqnou re neeq fo LstHONG TU CxTeTE El Tu S OAGLAJOLA 2516 caruwor pe mecuicq sug tye dene 12 pe ucm eyouscur 1 spe dnenc’ TL mpets Te vor GuoNEp zbuce Ty TE dnene cpeu spe ued osu vat pojous bexjousnué rpc cudncne obstsniow' me unnes euems qpat qpete re evon&p 2bs0 [peep eudnene obsisnou yeistas unupet oj ejeueure ny rye dic cp]: « cu betjousnu® ype cudnene obsisriou' (ps usm cyouscu se S|GUICUT | Te Weelseq If APC LET. GUA OL IP Lows ype 4°35" "6 opectxe ty dene mIASTTA coursed fpuce cyeueure VB’ CY ue 435 : 4 Ivlelc] I . rs obeu obccstiou bexjouncg ou 9 diene sill nou muctesece (pe UNIS O| cjomNCUrZ 1 1c IswcurZ 1 (pe dene pd ous i — Cannan ena meena ee ecw Seu ecLIEq pec b 69 pecomice rpc tem: Facp eudne -< [pe Budnene obcusmou 12 ecq (0 1; aC UE vTT EXONEDE +h GIGLUGUT [0 THE Lem OF ppc deneey ey Gener = 54 HOU" PAG em] qlecnze por (pee LcbucecUIITIOUE IU Ipc O]JOMIUE eccpour Councureut st coubmeg (0 jiuged pet wcbucecursnou O4dncne ompcunies mec puye UATIIPSL O} G]EWIGUTe SLE KUOMU TY IqATUCS (CU TAMA LebUcecUFITIOU of drone 2 UE een WOKE 6UCICUE Iq snerpel on jane su buot kuomjoqBe spont tye UMUIpEL OY CIoUICULe W je drcne ce awA [UKE [re pC cporce oy rebicecurUs dnene we aU TULSA OL 8 JrUKEq Jer gel net Ke axscy" dene cau sj20 po Lcbicecurcq 1 WcWIOLA marUE OU - qu TY BEbBE2EALVLIOV OL ONENE TIP Lesbos obstsnou re betyousseq ou cuibrd erucy spew po apscy 12 wy nuqeLyom ey eJoweUr C12 te9q ELOUI tye WEmce .I8° 4°32 "IL 1e cjomt (pst SCL boxjoustue rpc tembecg obeusnou" ppc ue we eKOML wevs OWL wevs | oe | { eh >, v c il i: | l omer cjeweure 1 dnene syreuu® pe dnene: ye oupA scccze obcistiou re betjousseq 20 (pote Fe uo cpaUB U AE UMUpKL Of {Ups testbecy obcisti0u rz neq (0 Lets (pe 6]susGUr {LOWS (ps L6s o4 (pe dnene aqpont YI BEVBLEEK Tune wourbesy obsisriou 12 bexyotseq ou su cwsbrd dene qpeu dene re mw muqetyjon cyewour y 12 1699 saagpont Leto nTUe IC ous pe pms pS 34 1 FecIOs. HH USL boxyounUE rpe wourboog ok = you boxouantu® Lowber. obeaou weplli> mee obeusjou" rpous 12 wo cpsubc vy frou uemure ppc ojoureur OUT cena) wsusontu® 1° Le w zowse 240 4313 LBOALDEEK spioue’ ON 1 y spe uruspor oy cqouxcure 1 spe dnc 6 your ope dm ccousbyrepeq maine ‘aur co webect (yo 6fewscut Hf meaqponits po pLourboog obsust10u" LP gh th cul spe dene: y yet beryouuu juousbee, obcts ay dnene ait pe (LOU OFpone uncanny C++ te Ss: SLLGN’ po AMLIUPISE LKOVLL I KEVE Kesh HICK OF ULNA. cr = qiweueIous) mus) icbicecumUE dene (par cw corn WY X2INE SIeweurs mpcie VI8ONNH +10 = EZONENE ( O' KKOUL KEV MV X2ISE’ LLEVD = C16" 6 po» MG 2p5I] vom qrcnee (pe s]FouU Jor berjoussIUE cudnenc obetstI0U ov s dene ‘ye IHesusA 6 re yom snd ocenbicq zo [msPEL Uo INectAIOLT mc bozaIp|s 19 (p> de La ec Alpen edtouanu 4 urous cudinens chessyoue LBOML= 1° BEVE = @ ye] sy | as | ws | 35 4 3 3 t 2 qompercudnone obetsroue" rp dene 2 JOO pa |" par pe EKO Lowstue (pc ewe: go ou beryoutue Escp cudnene obststiou iucuesese (pe ANING OL KEV MTUSPIC sus) Mgex” [pe AgINE OL BOL towsIwe (pe zs" (E18 CB) pA] suqirwom pecomee | (SEK =0+ 1 = 1) suq spe cyouseur sap ase 18 Ye meus Ose zpomu HBF $304" OU beyouNUE rps cudnenc obetsnou" Ie KEV AUspI6 F1UC Twrnsy}e pow gps done re cui (ps ssn OLLKOWL “suUSPIC! I Sq KEV a eraew - Grete commayue outs years, Wak c3ea- Guns 2 cwbe, EBOML= 1° KEV = 4 3 | [3 , eae peers a ae EBOML= 1" BEV = 0 Tees (pe zecoug 6jcuscur rq] ps byyeeq st 1qex 5 3q ummpet oj ejeucure spur cau pe [Link] Tu UT 6) Y2 2° LPO Lat cyowseur mm] Pe BSCS {[pe euncenuc of 9) 6 ICP AV X2INE = 2 1@ epOmu TU EIB 30" LP suq (p6 Ue G]GUICUT 12 IwecLAEg 9K (PHT SULA boetqIOU 1 lugex cour 20 ou {V6 KEV #e wcuewsursg ph | poyote rye cjewmour 2 msecigeq 1 epe dene papst scemsqjA pbboue re qpat pocp rye inc qq 9 UCM GyeweUr HULO rpc dene’ TPE KEWIS AUSPIE EVONED KEVE ssuspice pane 9 agjne edn (0 | 13106 0 ("C* EKOUL= I’ BEV = 0) 1. dnene coursiue a eukye cyousout (peu por? LKOML woque: juIng||® mpou donc ¥e ew LGOVAL ANNpIC pre # Asn | SUG KEWK AUP) (pat counnue 9 g|NG BIH IqCURUGe (pe wine UIT [Link] 6]6UxAUK aH sm MATA CY cowour of (pe dene wsebec acy: Ju IqqHIOU 10 {HEE mG BTeO ERG OTP AsTISPIE NV ug (#0 ASUPIGe KBOUL 194 BEVIS *pICH Kecbe ruscy OL mtAsTA 1qex OL {HE LOUK TT, bicecut Acne ie SU ILLIA’ se UGE (0 LUMTURTD su OUG-qHUEUEOUs] 0 Ju ouget.t0 u su) obeusti0u" susie 1 axonic quia extern. hon uceq 10 ebecr|A (pe #186 OL MUS 1 1 peyote beyou” mush'V" Lpc eiuibjoat sid (0 Lebtceeut a diiene Ww urGWOLA Ye (0 Mes ONG - qHUENeIOUST TIT] VEKVA BEDBECEVLVLIOY Ob ONENE‘AHEM ou Gener = ht Lewsiwe qpe amuse (6° KEV =2)' Lil? 12 pe cvec mpots dene pecowser ey The bexyous ¢ wos qednene obcistiowe (pou 5, PEA TUG LK OY, ny PSU EKOUL tq] pe 1 2110 & 16 (O° Lue KEY HAE egg - Guens ely HAE 3.8 - OM qeyoUUE OE gyomeag EBOML = 1" KEV = 2 EBOML = S' KEVE = 2 de | ss | as | ts | 3s ss [as [a ] 4 3 3 t 2 4 3 3 A 2 dnene oujd syrct2 tpo [Lour of rye dene suq vor 1f2 Lest wqsx 5(1 +1 =5) oLmednene: yo BEV Lewsve (pe zsune se qojorwE su cjcweu, Low fpe tps dnene tz qojoreq suq EKOUL 12 WCLCWIGUIE PA |° LVS EKOUL A9U9pI¢ LOM coursiue pe KEV =2 AAPSU don berjouws pc qednene obcistiou ou ye dncne’ rpe ejouseut st pc out Cowaiger su gush ( 92 eporu wy FAB 43) V ANP 2 SISWICUI2’ 20 EKOL= I Iewssmue 1 qpe sus LGWOAGY [LOU Ips dene’ (pe c|sweUL 12 Uo JoURGL sAsT]SpIs IU «pe dene syrponep (pe As) IUqex COUISIUEG TU EKOUL 2 LswoACG SUG EBOUL #2 Tuctoweureg pA 1° QUCE su c]eMIcUL 12 tuednene: 20 ou cscp qedncnc obsisrion’ myst scens]A pybboue ra (pst qy6 sus eyouseur KKCWIGUUPEI (PST IPE ASLISPIC KOVAL CoursIUe sw 1Uqex Of (ps SLLNA GpeMIEUE PIED Fa 8 PE BOUT OL Qubcyoume spe qednens obcistron" ype ejeweur re qojereq OUT PE WoUr OL (pS dsne DEONEDE * mo qwecls LLE 9116 BEV OL tps drenc (POT KEYES Hom course pe uqex OL SIA 6 mpeLe Bem LEW il Pe eerie peD 1 2 Tuapoue re ebace Yor pe uc rus pe dnc (pou Ae 5’ KEV Yeqctemeured PAI x aye cLLOL we2eaEe Ye Boucrsteq cacil(e OAGLJOM 2¢ queu drone re pny] sapiop tebtsecure On poe tac tor pox rp nu 2ieb |" 6 combs tH pay OLBEWE “6H (PSK OL WV X2ISE Tuped ste edna] qu qpre sjBoups' me utat pork mCP pote zbace IU 1p6 MLS 6 LOL CUS LLEIN 0 91¢ sq UO weELTOU CoE fae byscs suq su sbbLobu vic, caw g oOfbEvE]<-HEW [weey LEW) Ss BEV BEVE + 4 [luciowen! Bev) [eva on enncine ] WHEE = WVX2ISE (HOU 4*_ Lepeck or dene oneuion 1 ouyqpun yee LEN 5 «meat if pane amc 1 oom sees. aE neath forperes. oppo diene” : vec acy one wee a HT suspic? LBOAL™4 KEV! fa emf 0sonond pew ep OF'P Sty ut umoys sv poruasauday 109 0 AtATE UP JO, “WHILUD]D ISI a4 AQ PAA ‘gnanb sepnauia & Uy odueum am sjuow nave yons b 0} Suypuodsa.i09 b smynouy saudas w3oT -(q)6e% Sty —-ananb y -(v)6er Md NOMS ilo f 2st 20g) Aeare oy ansadsau | q pay ANAND AV 1NDAII-ANAN AO NOLLVINASTAATY AVAAY GIANT 7 ML -dgey Sty parayep 1 = uvay Z = INOwS u UO - TRE “By = UVBY 'Z = INOS J hs ca ee ~aser Sty z= 4vau'L 1M OL - DBE “St 2 = BVSU‘0= INOS ae lz [ oe. 2 7G supmuos nO - a8e'r Bi 0= wat '0= 1Nows aL [ ananb Gduy - ya + ALI AU >pu VW ‘20 stv noua >a ttt mb ay ay pur wow9[9 yo xapur aA UI +49 Smem sxcmmse. ome (I+4V Ta =INOMA 27 1INy anang) pauasuy stuauaya 240m ons - HIP" Biy © = BEY "b= INDUS [else] e oo Peusasuy wow? 240 - 91p'p ‘hy b= BRM 'P © INOMY | ae] | 19 oO Sey eo ee eee uu 2m ret * LNOWA OWL “xaput Aen yexp ye pauiasut aq fim usu P MOU otf PUR | 0170894 ITM BVSTY qn ananb Je|nour9 sip 0 19 Aes (uomexado ananbua >t) awiaja MoU Ppe MOU oN J Pataqap stuowaya asm omy -t1pp Sry Povyap somaya a0 = ZIP B14 $= Uvau'P = INOws $= Uv3Y 2 = LNOUS vz | ze wlelw]s Ce EN ae aaa oo OL aa (N=UVAY Pur T=INONT arn) ssuawiay a64f supomues among - q1y'y ‘iy porasuy stuowenya suow Oxy - 919° ‘Shy S = uvau "l= INDUS = Uva ‘t= LNOM ve |e | i [ss | ee | tw [st | ez s v € Zz 3 Ss v s z L suaWpa avo summiu0s mand - g14°p “Sty Sida anand soynouy VIP “Bt b= Uvau't = Now O= NYU ‘t= LNORS [ [ 82 a s v € z L s v € Zz L S=AZISXVW 00 Ava ue raprsuos sn 19] ‘91 1 9p10 Uy “ananb ayp Jo aunyeu sejnos19 ay 2 IGELEA INOW U1 Pt bn ado onanbap pue ananbus ayy ureydxo 8 94 TEM LNOWA 2M wom ¢ xapur poy) wopiad a” uaya Kyser Pur | 0139899 J[1m mou om jf: 9jdunexo aUID[9 Mau e ZuNOSUT IeuEA YAY amp uaKp a[durexa snoraaud ay 1 pus ayy poyoeas sey swas J! uaAa Ksea ston: ananb sonaays fo uoyoquasaadas po30] - opp “B14 [L-ulo) {lo cz HOwine (avay ie WALIvesU) Wa [uvaH]0o | & [eumonas 9 jo pug ) -+uv3u > yuvay b> uvae eu) AZISXWW = HW3H 40 [Aidwe si eneno] 0 = HWaY J Ipsec od ci» veal cba Sas eee [esnjonuys 4} 0 pu3 } usmes : ‘MOl9NO,, OM vou (| + HWE = LNOWS PUP O =] HY3H ) 40 ( 3ZISXWIW = HVSH Pue L = LNOHS) J * [moyseno enenb 1040049] *b “ananb zejnouio ayp JO as 2Y) 1 WALT O= AVM Pur | = [NOY pure Aidwa st onanb sejnast9 woRLOOAUL J 24 0} ONC etp auunsse 244 “KyoAnsedsaz ananb atp jo sjusUr2|9 sear Pur IO ay JO XepuE ‘eure otp joyoun doay yVaY Pur LNOYA SAiqeUeA JUL “Avue aM Jo 9215 9Up St AZISK WW 2x 1PAZISXVI UreuOD Ue eM onanb seams Sunuasaudos Kee [EUOISUAUNp -9uO. B9d0D WAI - WLLL “AZISXVIN AVA ‘INOW 0D) ONAOD : ZF UNLLOSTY SUF LUT P SSNOSIP MOI YS OM 14 suo mand - WIP Shy ‘© = ANOUd | se [ad] » ae A LNOUA pur Aidura 2 YUVAY = LNOW 0s an:yeas aip stuasaiday aura] ysounys ayp pure wo amp stuasadar ywswalS up ‘AqTes9U9y ‘6p'p ‘Bly UI UMOYs sv payuasaudas ATpeuLIOU st Inbop v ‘A{TeOIOq “oppru ng ananb amp Jo sway JO JOLY axp ye "2"! pud 194}19 Je UOND[ap pur YORASUT SMOTTE YEU, anbap y ‘ananb v Jo uoneERA arp Jo uo st (ananb papua-ajqnop) anbag y anda e'7'+ “IST] POUT] BP JO Sopou atp [Te 0} poyeooyye K1ourout ap sasvafau veup payoaur st (() ananb~ yur] ~) so}onsap pur pexonsap st 7b afgo ayy “wesToud x9 Uo ‘ATTeULY “SuTUUTTaQ 1p Woy sapou ayp [Te Jo wed oyur at sXejdstp ‘uoNIOAU UO ()eszeaez3 "Tb quowrarers uatp ¢ = 99109 JT ‘royesado ayayap Sursn A1ouraur sit aseajau Uotp pur ans Ja1uH0d Ut) Ssaxppe sit a10}S 0} paoU ISTY aM ‘apou paro|ap Jo AIOUIOUL aU aswaIOI OL, tyuyi<-eaes = quozz ‘quawoyeys otp Suisn uawua[9 wos} 1x9U 0} JUIOd oy apeUL st juouy 2]qetTeA J\UIOd ‘anonb op Woy uEWE]> eAouiay OJ, ‘onanb ayp Woy (ananb poxU] Jo apou juautd[2 JOY SuLAOUIOs Jo ainpedoad yp IPI paedoid am astauraypo “WMyaE pure ITessaut woqepun Aeydsip 94s (IAN = 1woyy 2°t) Aiduua sty] OU 0 Axduuo st (ananb Sunuasaudat) 1s1] paqul aq soyrey 3Jooyo sty om “()ananbyuy bap uonoury soqurout jo uonTUTFap amp Uy )enenbyutT bep- 1b ‘q]e2 wonsuny requrowt Suisn pautioyiad st uorwexado ananbep watp ‘Z = a9K0y JT Sb'p Bly Woy rwa[9 st oy, 2pou wou stip 0} syutod soquT0d way wotp pue ananb axp Jo pus aup ye apou MoU at SLOSUT SII} fepoumeu = 2e0z fepoumeu = yut{<-zeex ‘wowaIes a1 apoumsau £q 0} pautod apou mau otp Jo ured our oup nur WHE Jo anpeA amp sasors {we3}t = osuT<-epoumeu ‘quowiarers oy, Poulan sowuiod ur ssaxppe Sunseys sy saioys pure ATjeorureuXp apou mau atp o1 AzoUFoUU SaredOITE fepou neu = epouncu “quouroye}s ax “( ananby ‘bus uonouny Jaquiow! Jo UONTULJap ay) UT # (wea 7. enbyutT bus tb *St13usn pauioysad st uonesado onanbuo oun‘ mindut soye uoyp | = 201049 amp JTyoeys e se anbeg somand) po syo0%s op pur Anare seynouto ase SuorTE) hom opdnyut ame avo, (xlx |< eee f OUNSa uowosodo Yr T1P SE lous uvay —-LNO} NOUS uo - aIS% snanb v se sioe anbap ap £ J] 49"1S SI9e anbop OK J'onn 1guad anbap auf, Sujmuofiad uO - GIS'# Ba 4 ie elon 13 paado yforpuasi fued ug = 15% “Std ANOUS uvad t Isp juuopied ug = AIS “Std NOUS 4 bo ajoleal|vjal | smyp wasut am, q quou 2d “VISE St ANOY4 4 giv | moue USN asuy yf “4 HP PRPP W PPPP TYARAL98Uy Yr TasuL a: (sway syuasaudas x a OADMOH “A 1S'b 2st aM J §lpanoadsai anbap amp Jo 144 anadsay anbop au J MP DAasur OL, WYyBRAaIop pur suontiado 3 10} ULsn se. Au su uy st d [= Te Pe] z x | alv| b6"p Bly Ur uMoys se poruasaudas éyqeo18oy st anon’ Aoud y “OdLa'2't onanb a4) 01 pappe aiom Koup Yor wt Jop0 ® aourpuo99e ur passaooud aim Komp uoyp oLsd sues ay 2ARY SOWI}DON | —_(G Auond Jomo] Jo wuaw9} ue o1 101d passodaid si AOU JoaTY YIM WaWIIDUY —_(e ‘sajna Surmorjoy ayp Yim doueprosoe Ur UoUID[a ap Jo AUOUd > siseq amp Uo patuuoyrod a Juowafo ue ing ananb seouT] Jo Oy ret an vie v st onanb Ayoud y S11} poxourar axe Auoud saysiy auloj9 WYN asuss xp ur ALioLd £q paropyo axe syuauray -Arsoud pojpeo (onqea) Kay oq Sey IAULIaTO Yowa YoryAs UF onaNb [duns Jo uoNeLEA v st onanb AWOUd y cd gg Aq pom ud aq []iM 1uoumoop aed id.2q 01 saed Jo Joqumu ayp 0} ZuIproo9" sqof yuud axp aznuOLd 0} Jang 99 PINom 0 ‘pantuigns 9g 01 gofysey a Y U9AA OLIN BuO] 10} 1TeAS 01 BAeY Pjnom gofased-| ures axp UI passaooud axe sqol asoup Jf ‘stseq AAS ISI1J aWH09 1SI4 Uo sated Oy pur ed gg ‘sated ( b 19d v apisuod : a]durexe 10.4 ido TY Ul J9py0 axp Ut passadaid 2q 01 paps UL pappe ara Kup yor Ur repo ad a10m Os passnosip aaey aa yeu onanb ayy ANdNO ALRION FZ FOAaMOH] ‘onan urejuo9 ur passa’ anbap pornussaxmdimg - aes'p i anbop pasounsou du - yes hg yvay 4LNOYS uvay 4ANOYS | Jvereie109 1UBrye}ejep | | 4 Eee a 4 Bribe el [<<] [x:[s ananb Auoud amp wpte parersosse santioud aup Jo stseq aup UO paTea1s eq O41 ® Suntqryxe uonnzed yoea pur pareredas you ing suonnsed adn nud xp Jo uonewoue|duur JoAd-BMU 9p UY wvae pur INOW puodsaioo xap\ ed yor 10,4°S anzed au "S poptatp st ‘onanb Auoud sip jo uoneausura|du [9A2f-MNU 0g "W20U09 JOfeUL B sea STHOUIOIO tf] HOS 01 PaAIOA 1y pure seas ap ve Alisea pouLiojiod axa wOaIap pure anb AWOL a4p Jo uoneWuaUID|duNt snolAasd aUp UT NOLLVINAWA Td ANANOLLIAW TFT? pus quouy ay WoIy Kyeanoodsax p SOM v9 pauLopiod 9q [[1 UOND|ap ULL au]2 mau v Suysasuy 42 onanb Sods, ala id“ 6S'b “Bg 4 ANOS x $ viv Mme leletvefets, L ©, | fo" ey Paes RiGHEY lt ReaeRAR L > 01 pauuiopiad 9 P Avot SUE AOU Unf Kos) Huson ce eae Pua aeaN A UO} KOU e SuTOsUT UC 1 pays oq