CPE211 Lecture 16-18: STACK and Applications PDF

Stack - an ordered collection of items into which new items may be inserted and from which items may be deleted at one end only (the top end). - LIFO (Last In First Out) structure Examples: Pile of trays Pile of plates Pile of books Pile of chairs Tennis balls in a tube cont...

Stack - an ordered collection of items into which new items may be inserted and from which items may be deleted at one end only (the top end). - LIFO (Last In First Out) structure Examples: Pile of trays Pile of plates Pile of books Pile of chairs Tennis balls in a tube container A tube of Pringles Sliced loaf bread inside a cellophane container Operations: 1. Push( - adds a new element into the Stack at the top end. 2. Pop() - removes the top element from the Stack. 3. Size() - returns the number of elements in the Stack. 4. IsEmpty() - returns True if Stack is empty, otherwise returns False. Application #1: Parenthesis Count at any point in an arithmetic expression with parentheses is the number of left parenthesis symbols encountered minus the number of right parenthesis symbols encountered. Requirements for valid arithmetic expressions with parentheses: a) Parenthesis Count at any point in the expression is >= 0. b) Parenthesis Count is zero at the end of the expression. Stack Implementation of Parenthesis Count problem: - as you scan the expression string left to right, every ‘(‘ encountered is pushed into the Stack and every ‘)’ encountered pops the top of the Stack. If Stack is empty at the end of expression string scan then the expression is VALID, else if the Stack is not empty or getting an exception (run-time error) due to an attempt to pop from an empty Stack, then the expression is INVALID. ALGORITHM for Stack Implementation of the Parenthesis Count Problem: s = Stack(); scan the input arithmetic expression string Left to Right (leftmost symbol to rightmost symbol): while (not end of input arithmetic expression string) symbol=getNextSymbol() if symbol is '(' s.push(symbol); else if symbol is ')' s.pop(); // if this results to a run-time error or exception then stack s is empty, // which means that P.C.< 0, there are more ‘)’ than ‘(‘ if (s.isEmpty()) output “valid” // which means that P.C=0, input arithmetic expression else // has balanced parentheses. output “invalid” // which means that P.C. > 0, there are more ‘(‘ than ‘)’ Exercises: Determine if the following expressions are valid or invalid by parenthesis count and stack implementation. 1. (b - a) * c) - (a + b) / d 2. ((a + b) / (a - c)) * d 3. ((c - b) * (d + a) / (a - c) Three (3) forms of arithmetic expressions: 1. Infix expression - 2. Prefix expression - 3. Postfix expression -