Lect 5

CSE211 Lecture Notes – 2004/2005-II

CSE 211: Data Structures Lecture Notes V by Ender Ozcan, Sebnem Baydere STACKS In this lecture we will discuss one of the most common data structures found in the computer algorithms; stacks Stacks are special cases of the more general data structures than an ordered list. A stack is an ordered list in which all insertions and deletions are made at one end, called the top. In other words it is a data structure in which all access is restricted to the most recently inserted elements. Stack is dynamically changing data type. How does it change? As we know that the ADTs are defined together with the operations defined on them. The last item added to the stack is placed on the top and is easily accessible. The items that have been in a stack for a while are more difficult to access. The stack structure is more appropriate if we expect to access only to the item at the top; all other items are inaccessible. It is analogues to the common stack of bills, stack of plates, stack of newspapers.

1. Stack Operations In a stack the three natural operations are Insert, Delete and Find. These are renamed as Push (insertAtFront), Pop (removeFromFront) and Top (peek). We can combine Pop and Top operations and return the popped item in Top. We also need an operation to create the stack.

Pop A B C

Top

Push(D)

A Top

D D B C

B C

Top

We expect that each stack operation take constant amount of time, independent of the number of the items in the stack. Analogy, in stack of newspapers finding today's paper takes fixed amount of time no matter how deep the stack is.

1

CSE211 Lecture Notes – 2004/2005-II

What makes the stack useful is that there are many applications for which we need to access the most recently inserted item to the list.

2. Example Uses of Stacks • • • •

Compiler Design, matching symbols The stack is also used in the implementation of the function calls. When a call is made to a function all the variables local to a function and the return address have to be saved by the system. The problem is similar to the balanced symbols. Stacks are used in converting parenthesized and unparenthesized expressions from infix to postfix notation based on a set of precedence rules. Another important application of stacks is the evaluation of expressions in computer languages.

2.1. Matching Symbols Compilers check the errors in your programs, frequently a lack of one symbol (missing * or / from a comment or a missing ( ) will cause the compiler to return unsuccessfully. A useful tool in this situation is a program that checks if everything is balanced. i.e., every ( has a corresponding ) or something else and the order is legal. Solution: Count the number of opening symbols, and corresponding closing symbols. For each symbol the quantities must be the same. Following structures will pass the legality check using this approach: [ ( ) ]a legal [ ( ] ) r illegal Simply counting the symbols is not sufficient, because [ ( ) ] legal but [ ( ] ) is illegal. Note that we are talking about processing a sequence of tokens and not worry about character constant '{' which does not need a matching. A stack is useful here because we know that each closing symbol matches the most recent opening symbol. If we place the opening symbols in a stack we can easily check that closing symbols are balanced or not. Algorithm: 1. 2. 3. 4.

Make an empty stack. Read symbols until the end of the file. If the token is an opening symbol, push it onto the stack. If the token is a closing symbol and the stack is empty report error. Otherwise, pop the stack. 5. If the symbol popped is not the corresponding opening symbol report an error 6. At the end of the file, if the stack is not empty report an error Otherwise, the symbols are balanced.

2.2. Use of Stacks in Function calls What happens when a function is called? Three actions are taken in steps: 1. A copy of the arguments is made locally within the function. Any changes to them are made on the local copy. 2. Storage is allocated for the local variables. 3. Control is transferred to the function. Before passing the control to the fuction return address in the calling program must also be saved. This is an implicit argument passed to the function. When the function is finished it retrieves the return address in its own data space and passes the control to it. When a function returns three actions are performed. 1. Return address is stored in a safe location. 2

CSE211 Lecture Notes – 2004/2005-II

2. Function`s data area is freed. 3. Finally, control is returned to the calling function and any returned value is also stored in known registers. Suppose that we have three functions and a main function. Main --------call A1 r1: -------end

Function A1 Function A2 Function A3 ---------------------call A3 ----------r3:------------call A2 -------------r2:-----------end ------end end Main calls A1, on completion its execution main will start at r1. This address is passed to A1. It saves it in some location for later processing. A1 invokes A2 A2 invokes A3 In each case calling function passes the return address to the called procedure. If we examine the memory while A3 is computing there will be an implicit stack which contains (r0, r1, r2, r3) , where r0 is the address in O/S where main returns control. Q. Why shall we use a stack? A. The returns are made in the reverse order of calls.

r3 r2 r1

r0 Implementing Recursive Functions using Stacks The use of stacks in implementing function calls becomes clerarer in this special case. If we assume that the return address for each function is kept in hardware we have a problem implementing reentrant code (recursive). Therefore, a separate stack of return addresses must be used and each time a recursive function calls itself, a new data area for that call must be allocated containing all the parameters and local variables.

3. Basic Stack Operations Two changes that can be made on a stack are given special names. When an item is added to a stack, it is pushed onto the stack, and when an item is removed it is popped from the stack. One way of implementing stacks is using arrays. Assuming that a stack is implemented using an array, we can define the following operations and use them whenever needed in an algorithm. Given a stack, item i, maximum size of the stack as n and top being the variable that holds the current number of elements in the stack, performing PUSH(stack,i,n top) operation adds the item i to the top of the stack . Similary, POP(stack,n,top) removes the top element and returns it in i. It is also possible to return the top element as a function value. For example: pop operation can be impelmented in a away that i=pop(stack,n,top)

/* returns the top item in variable i.

3

CSE211 Lecture Notes – 2004/2005-II

The following procedures give the algorithms for these operations (considering that the stack is implemented with an array of size n). Procedure PUSH(item, stack, n, top) //Insert item into the stack of maximum size n; top is the number of elements currently in stack// if top>= n then report STACK_FULL else top = top +1; stack(top) = item end PUSH Procedure POP(item, stack, top) //removes the top element of stack and stores it in item unless stack is empty // if top<0

then report STACK_EMPTY else item = stack(top) top = top -1

end POP

Additional to these methods implementing peek (returns the value at the top of the Stack without removing it), getStackSize, isEmpty and isFull (if a static structure is used) methods are very useful. 3.1. Implementation of Stacks in C Before defining the operations we need to create an empty stack. An array can be a home for the stack. During the execution satck can grow or shrink within this array. One end of the array is the bottom and the insertions and deletions are made from the other end. We also need another field that at each point we need to keep track of the current position of the top of the stack. Therefore, a stack can be declared as a structure type containing two items: an array to hold the elements of the stack and an integer to indicate the position of the current stack. #define STACKSIZE 100 struct stackcontent { int top; myType items[STACKSIZE]; }; typedef struct stackcontent Stack; Stack s;

The above definition tells us that the maximum size of a Stack type is given by the STACKSIZE which is 100 in the given example. The identifier top indicates the top most item in the stack. For example: if the value of s.top is 4 this means that there are five elements in the stack. s.items[0], s.items[1], ...s.items[4]. When the stack is popped the value of the top is reduced to 3 which means 4 items remain in the stack. The empty stack contains no elements and can be indicated by s.top= -1 .To initialize the stack we can set the value of the top to -1. We may write a function which returns if the given stack is empty or not.

4

CSE211 Lecture Notes – 2004/2005-II #define true 1 #define false 0 int isEmpty(Stack *ps) { if (ps->top == -1) return(true); else return(false); };

Implementing the pop operation: Poped value can be stored into a variable passed to pop operation as an argument and pop operation can return success or failure of the operation. #define SUCCESS 1 #define STACK_EMPTY -1 #define STACK_FULL -2 int pop(Stack *ps, myType &popedVal) { if (isEmpty(ps) ) { printf("%s", "stack EMPTY"); return STACK_EMPTY; } popedVal = ps->items[ps->top--]); return SUCCESS; }

Write the other stack operations in C as an exercise. 3.2. Implementation of Stacks in C++ Following interface can be used implementing a stack: template< class myType > class Stack { private: int size; int top; myType *stackArr; public: Stack( int ); ~Stack(); bool isEmpty(); bool isFull(); int pop( myType & ); int push( myType & ); int peek( myType & ); int stackSize(); } template< class myType > bool Stack <myType> :: isEmpty() { return (top == -1); };

#define SUCCESS #define STACK_EMPTY #define STACK_FULL

1 -1 -2 5

CSE211 Lecture Notes – 2004/2005-II template< class myType > int Stack <myType> :: pop( myType &popVal ) { if ( isEmpty() ) { printf("%s", "stack EMPTY"); return STACK_EMPTY; } popVal = ps->items[ps->top--]); return SUCCESS; }

4. Evaluation of Expressions and Polish Notation ( ( (A/B)**C)+(D*E)-(A*C) ) How compiler executes this lengthy expression? Every language uniquely define the order of operators. (Precedence rule) An expression consists of operands operators and delimiters. Parenthesized co nventional form is called infix form. (operand operator operand) They are converted to another form called postfix form (Reverse Polish Notation -each operator appears after the operands). We will see the relationship between an infix and postfix notation, we will also see how stacks can be used to evaluate an RPN expression. Also to convert an infix to postfix by hand. RPN is used in interpreters and compilers as an intermediate representational form for statements. There is also prefix form (Forward Polish Notation) in which the operator precedes its operands. Ex A*B/C infix AB*C/ postfix Converting from infix to postfix notation: Translation by hand: 1. Parenthesize the expression 2. Move all operators so that they replace their corresponding right paranthesis, starting from the inner most parenthesis 3. Delete all parenthesis ( ( (A / (B*C) ) + (D*E) ) - (A*C ) ) ABC*/DE*+AC*Its implementation requires two passes -

read and paranthesize

6

CSE211 Lecture Notes – 2004/2005-II

-

Examples: Infix A A-B (A-B)+C A-(B+C) (A+B)*(C-D)

move the operators

RPN A ABAB-C+ ABC+AB+CD-*

If we relax the condition that expression be fully parenthesized. We need to use operator precedence from left to right. (associative rule) Associative Rule 1) + and - associate left to right 2) * and / associate left to right 3) If there is a built in exponentiation operator (**) associate from right to left (we will ignore this ) Priorities and Precedence Rule 1) + and - have the same priority 2) * and / have the same priority 3) (* and /) precede (+ and -) Unparenthesized A+B+C A-B+C A+B-C+D A*B*C E/F*G E*F/G*H A+B*C+D A-(B+C)*D

Assumed Parenthesized Form (A+B)+C (A-B)+C ((A+B)-C)+D (A*B)*C (E/F)*G ((E*F)/G)*H A+(B*C)+D A-((B+C)*D)

RPN AB+C+ AB-C+ AB+C-D+ AB*C* EF/G* EF*G/H* ABC*+D+ ABC+D*-

4.1. Infix -to RPN Translation using STACKS 1) Initialize an empty stack of operators 2) While no error, until the end of infix expression do the following: a) Get the next token (const., Variable, operator, “(“, “)”) from the infix expression b) If token is i) A left paranthesis Push it onto stack ii) A right paranthesis Pop and display (add it to the rpn string) elements until a left paran. is encountered. (if no left paran., error!) iii) An operator If the stack is empty or token has higher priority 7

CSE211 Lecture Notes – 2004/2005-II

than the top stack ele ment, push token onto the stack. Otherwise, opo and display (add it to the rpn string) the top stack element, then repeat the comparison of token with new top stack element. Note: Assume “(“ in the stack has lower priority than others iv) An operand display it (add it to the rpn string) 3) When the end of infix expression is reached, pop and display (add it to the rpn string) stack items until the stack is empty. Note that do not display or add “(“ or “)” to the rpn string. With operator priorities only Example : Workout A+B*C/D-E See COURSE NOTES.. Involving parenthesis in the expressions Push left parenthesis onto the operator stack (create a false bottom). Apply the algorithm. When a right parenthesis is reached the stack is emptied until the false bottom) Example : Workout A+(B*(C-D)/E) See COURSE NOTES 4.2. Evaluation of RPN Assuming only binary operators, the algorithm for evaluating RPN expressions is: Get a token until EOF If token is a number (operand), push it into a stack Else // it is an operator Pop two numbers from the stack, otherwise exit with ERROR Apply the operator Push the result back onto the stack Pop the result If the stack is empty return the result, otherwise exit with ERROR

35+ 24 - * 6 * 1- empty

2- 3

9- 6 -16

10- -96

3- 5 3

4- 8

5- 2 8

8

6-4 2 8

7- -2 8

8-

-16

CSE211 Lecture Notes – 2004/2005-II

Each snapshot is taken just before the leftmost input character is examined. In general, 1. If argument is an operand, stack it. 2. If argument is an n-ary operator, then the n arguments are already on the stack. Pop the n arguments from the stack and replace by the value of the operator applied to the arguments.

9