Stack Overview
Stack ADT Basic operations of stack
Pushing, popping etc. Arrays
FAROOQ
Implementations of stacks using
What is a stack?
It is an ordered group of homogeneous items of elements. Elements are added to and removed from the top of the stack (the most recently added items are at the top of the stack). The last element to be added is the first to be removed (LIFO: Last In, First Out).
FAROOQ
The Stack ADT
A stack is a list with the restriction
that insertions and deletions can only be performed at the top of the list
FAROOQ
The other end is called bottom
Fundamental/Primitive operations:
Push: Equivalent to an insert Pop: Deletes the most recently inserted element Empty: Examines whether the stack is empty
Stack ADT
Stacks are less flexible
but are more efficient and easy to implement
Stacks are known as LIFO (Last In, First Out) lists.
FAROOQ
The last element inserted will be the first to be retrieved
FAROOQ
Stack ADT
abstract typedef<<eltype> STACK (eltype);
abstract empty(s) STACK(eltype) s; Postcondition empty== len(s)==0; abstract eltype pop(s) STACK(eltype) s; precondition: empty(s) == FALSE postcondition pop == first(s`); s== sub(s`,1, len(s`) -1;
FAROOQ
Stack ADT
abstract push(s, elt); STACK(eltype) s; Eltype elt; postcondition s == <elt> +s`;
FAROOQ
Example
Consider a mathematical expression that includes several sets of nested parenthesis. 7 ((x * (( x + y) / (j - 3)) + Y) / (4 2.5)) In expression we want to check [Link] are an equal number of right and left parenthesis. 2. Every right parenthesis is preceded by a matching left parenthesis. Expressions like ((A+B) or A+B( violates condition 1 and expressions like )A + B(-C violate condition 2. Nested Depth: is the number of scopes that have been opened and not yet closed. Parenthesis count: no of left parenthesis no of right parenthesis.
FAROOQ
Example (Contd)
Expression id valid if following conditions are met. 1. Parenthesis count at end should be zero. 2. Parenthesis count at each point in expression should be non negative. 7 ( ( x * ( ( x + y ) / ( j - 3 ) ) + Y ) / ( 4 2.5 ) ) 00122234444334444322 211222 210 ( ( A + B ) and (A + B] is illegal
1 22221
FAROOQ
Algorithm for Example
valid = true s = empty stack; while (we have not read the entire string) { read the next symbol (symb) in the string; if (symb == ( || symb == , || symb == * ) push(s, symb); if (symb == ) || symb == - || symb == + ) if (empty(s)) valid = false; else{ i = pop(s); if (i is not the matching opener of symb) valid = false } }// end of while if (!empty(s)) valid = false; if (valid) cout << String is valid; else cout << String is not valid;
FAROOQ
Parenthesis Stack
Consider expression [x + {y (a + b)}] ( { [ [ [ [ x+{ { { [ [ x+{y-(a+b)
[
[ x+{y-(
[ [ x+{y-(a+b)} [ x+{y-(a+b)}]
FAROOQ
Implementation of Stacks
Any list implementation could be used to implement a stack
Arrays (static: the size of stack is given initially) Linked lists (dynamic: never become full)
FAROOQ
We will explore implementations based on array and linked list Lets see how to use an array to implement a stack first
Array Implementation
A stack in C++ may be declared as a structure containing two objects
An array to hold elements of the stacks Integer to indicate position of stack top #define SIZE 100 class Stack { int top; int items[SIZE]; }; Stack type variable will be declared in main() as Stack s;
FAROOQ
Stack Operations
void push(int x) - add item to the top of the stack
void push(int x) { if ( top==SIZE-1) { cout <<Stack overflow; exit(1) } else items[++top)]=x; } Call of function will be like [Link](2);
FAROOQ
Stack Operations
int pop( ) - remove an item from the top of the stack
int pop() { if (empty()) { cout <<Stack underflow; exit(1); } return(items[top--]); }
FAROOQ
- To check whether the stack is empty or not
int empty() { if (top ==-1) return TRUE; else return FALSE; }
Stack Operations
int stacktop() - To get the top element of the stack
int stacktop() { if (empty()) { cout <<Stack underflow; exit(1); } return(items[top]); }
FAROOQ
Polish Notations
Expression can be written in prefix, postfix or infix notations + A B prefix operator precedes operands
A B + postfix operator precedes operands A + B infix Unlike Infix notation no parenthesis are required to enforce precedence. Expressions are evaluated from left to right.
FAROOQ
Converting to Prefix, Postfix Notation
Precedence rules are used to convert expression
1) Exponentiation, 2. Multiplication/ Division 3. Addition/Subtraction
Converting to Prefix Notation (A+B)*C = [+AB]*C = *+ABC A+(B*C) = A+[*BC) = +A*BC (A+B)/(C-D)= [+AB]/[-CD] = /+AB-CD Converting to Postfix Notation Ex. A+B= AB+ (A+B)*C= [AB+]*C= AB+C* A+(B*C) = A+[BC*]=ABC*+
FAROOQ
Exercises
A$B*C-D+E/F/(G+H) ((A+B)*C-(D-E))$(F+G) A-B/(C*D$E) (A+B$D)/(E-F)+G A*(B+D)/E-f*(G+H/K)
FAROOQ
Example: postfix expressions (cont.)
FAROOQ
Postfix expressions: using stacks (cont.)
FAROOQ
Postfix expressions: Algorithm using stacks (cont.)
opndstk = the empty stack; while (not end of input){ symb = next input character; if (symb is an operand) push(opndstk,symb); else{ opnd2 = pop(opndstk); opnd1 = pop(opndstk); value = result of applying symb to opnd1 and opnd2; push(opndstk, value)
FAROOQ
EXERCISE
623+-382/+*2$3+ symb op1
6 2 3 + 3 8 2 / + * 2 $ 3 +
op2
value
opndstk
6 62 623 65 1 13 138 1382 134 17 7 72 49 49 3 52
FAROOQ
2 6 6 6 6 8 3 1 1 7 7 49
3 5 5 5 5 2 4 7 7 2 2 3
5 1 1 1 1 4 7 7 7 49 49 52
Algorithm to Convert Infix Exp to Postfix Expression
1. opstk = the empty stack; 2. while (not end of input){ 3. symb = next input character; 4. if (symb is an operand) add symb to the postfix string 5. else{ 6. while (!empty (opstk) && prcd(stacktop(opstk), symb)){ 7. 8. topsymb = pop(opstk); add topsymb to the postfix string; } /* end while*/ 9. push(opstk, symb); } /* end else*/ } /* end while*/ 10. while (!empty(opstk)){ 11. Topsymb = op(opstk); 12. add topsymb to the postfix string; } /* end while*/
FAROOQ
EXERCISE
A+B*C symb
A + B * C
Postfix string
A A AB AB ABC ABC*+ + + +* +*
opstk
FAROOQ
EXERCISE
A*B+C symb
A * B + C
Postfix string
A A AB AB* AB*C AB*C+ * * + +
opstk
FAROOQ
Algorithm to Convert Infix Exp to Postfix Expression
9. if (empty (opstk) || symb != ))
FAROOQ
push(opstk, symb); else topsymb = pop(opstk);
Precedence rules for parenthesis:
prcd((,op) = Prcd(op,() = prcd(op,)) = prcd(),op) = FALSE FALSE TRUE undefined
Evaluation of Expressions
Consider the following infix expression A+(B*C-(D/E$F)*G)*H Convert into Postfix using Stack
sumb
A + ( B * C ( D / E $ F ) * G ) * H
postfix string
A A A A A A A A A A A A A A A A A A A
opstk
+ + + + + + + + + + + + + + + + + + ( ( (* (* ((- ( (-( (-(/ (-(/ (- ( /$ (-(/$ ((-* (-* * *
B B B B B B B B B B B B B B B B
C C C C C C C C C C C C C C
* * * * * * * * * * * * *
D D D D D D D D D D D
E E E E E E E E E
F F F F F F F
$ $ $ $ $ $
/ / / / / /
G G G G G
* * * *
-H -H*+
FAROOQ
Converting Infix Expressions to Equivalent Postfix Expressions
Figure 6.9
A trace of the algorithm that converts the infix expression a - (b + c * d)/e to postfix form
FAROOQ