MODULE-1[CHAPTER-4]
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT
THE STACK ABSTRACT DATA TYPE STACK
This is an ordered-list in which insertions(called push) and deletions(called
pop) are made at one end called the top
Since last element inserted into a stack is first element removed, a stack is
also known as a LIFO list(Last In First Out).
When an element is inserted in a stack, the concept is called push, and when
an element is removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow and trying to push an
element in a full stack is called overflow.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
As shown in above figure, the elements are added in the
stack in the order A, B, C, D, E, then E is the first element
that is deleted from the stack and the last element is
deleted from stack is A.
Figure illustrates this sequence of operations. Since the
last element inserted into a stack is the first element
removed, a stack is also known as a Last-In-First-Out
(LIFO) list.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
SYSTEM STACK
A stack used by a program at run-time to process function-calls is called
system-stack.
When functions are invoked, programs
→ create a stack-frame (or activation-record) &
→ place the stack-frame on top of system-stack
Initially, stack-frame for invoked-function contains only
→ pointer to previous stack-frame &
→ return-address
The previous stack-frame pointer points to the stack-frame of the invoking-
function while return-address contains the location of the statement to be
executed after the function terminates.
If one function invokes another function, local variables and parameters of
the invoking function are added to its stack-frame.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
A new stack-frame is then
→ created for the invoked-function &
→ placed on top of the system-stack
When this function terminates, its stack-frame is removed (and processing of
the invoking function, which is again on top of the stack, continues).
Frame-pointer(fp) is a pointer to the current stack-frame.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
ARRAY REPRESENTATION OF STACKS
Stacks may be represented in the computer in various ways such as one-way
linked list (Singly linked list) or linear array.
Stacks are maintained by the two variables such as TOP and MAX_STACK_SIZE.
TOP which contains the location of the top element in the stack. If TOP= -1,
then it indicates stack is empty.
MAX_STACK_SIZE which gives maximum number of elements that can
be stored in stack.
Stack can represented using linear array as shown below
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Stack ADT
The following operations make a stack an ADT. For simplicity, assume the data
is an integer type.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Main stack operations – Push (int data): Inserts data onto stack.
– int Pop(): Removes and returns the last inserted element from the stack.
Auxiliary stack operations – int Top(): Returns the last inserted element
without removing it.
– int Size(): Returns the number of elements stored in the stack.
– int IsEmptyStack(): Indicates whether any elements are stored in the stack
or not.
– int IsFullStack(): Indicates whether the stack is full or not.
The easiest way to implement this ADT is by using a one-dimensional array,
say, stack [MAX-STACK-SIZE], where MAX STACK SIZE is the maximum number
of entries.
The first, or bottom, element of the stack is stored in stack[0], the second in
stack[1] and the ith in stack [i-1].
Associated with the array is a variable, top, which points to the top element
in the stack.
Initially, top is set to -1 to denote an empty stack.
we have specified that element is a structure that consists of only a key field.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
1. CREATE STACK:
The element which is used to insert or delete is specified as a
structure that consists of
only a key field.
1. Boolean IsEmpty(Stack)::= top < 0;
2. Boolean IsFull(Stack)::= top >= MAX_STACK_SIZE-1;
The IsEmpty and IsFull operations are simple, and is implemented
directly in the
program push and pop functions. Each of these functions assumes that
the variables stack and top are global.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Add an item to a stack
Function push() checks to see if the stack is full.
If it is, it calls stackFull, which prints an error message and terminates execution.
When the stack is not full, we increment top and assign item to stack[top].
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Delete an item in a stack
For deletion, the stack-empty function should print an error message and
return an item of type element with a key field that contains an error code.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
STACK USING DYNAMIC ARRAYS
Shortcoming of static stack implementation: is the need
to know at compile-time, a good bound(MAX_STACK_SIZE)
on how large the stack will become.
This shortcoming can be overcome by
→ using a dynamically allocated array for the elements &
→ then increasing the size of the array as needed
Initially, capacity=1 where capacity=maximum no. of
stack-elements that may be stored in array.
The CreateS() function can be implemented as follows
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Stack CreateS(max-stack-size') ::=
#define MAX—STACK—SIZE 100 /*maximum stack size */
typedef struct
{
int key;
/* other fields */
} element;
element stack[MAX—STACK—SIZE];
int top - -1;
Boolean IsEmpty(Stack) ::= top <0;
Boolean IsFulI(Stack) ::= top >= MAX-STACK-SIZE-1;
• Once the stack is full, realloc() function is used to increase the size of array.
• In array-doubling, we double array-capacity whenever it becomes necessary to
increase the capacity of an array.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
ANALYSIS
In worst case, the realloc function needs to
→ allocate 2*capacity*sizeof(*stack) bytes of memory and
→ copy capacity*sizeof(*stack) bytes of memory from the old array into the
new one.
The total time spent over all array doublings = O(2k ) where capacity=2k
Since the total number of pushes is more than 2k-1 , the total time spend in
array doubling is O(n) where n=total number of pushes.
STACK APPLICATIONS: POLISH NOTATION
Expressions: It is sequence of operators and operands that reduces to a single
value after evaluation is called an expression.
X=a/b–c+d*e–a*c
In above expression contains operators (+, –, /, *) operands (a, b, c, d, e).
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Expression can be represented in in different format such as
Prefix Expression or Polish notation
Infix Expression
Postfix Expression or Reverse Polish notation
Infix Expression: In this expression, the binary operator is placed in-between the
operand.
The expression can be parenthesized or un- parenthesized.
Example: A + B
Here, A & B are operands and + is operand
Prefix or Polish Expression: In this expression, the operator appears before its
operand.
Example: + A B
Here, A & B are operands and + is operand
Postfix or Reverse Polish Expression: In this expression, the operator appears after
its operand.
Example: A B +
Here, A & B are operands and + is operand
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Precedence of the operators
The first problem with understanding the meaning of expressions and statements
is finding out the order in which the operations are performed.
Example: assume that a =4, b =c =2, d =e =3 in below expression
X=a/b–c+d*e–a*c
((4/2)-2) + (3*3)-(4*2)
=0+9-8
=1
OR
(4/ (2-2 +3)) *(3-4)*2
= (4/3) * (-1) * 2
= -2.66666
The first answer is picked most because division is carried out before subtraction,
and multiplication before addition.
If we wanted the second answer, write expression differently using parentheses to
change the order of evaluation
X= ((a / ( b – c + d ) ) * ( e – a ) * c
In C, there is a precedence hierarchy that determines the order in which operators
are evaluated. Below figure contains the precedence hierarchy for C.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
The operators are arranged from highest precedence to
lowest. Operators with highest precedence are evaluated
first.
The associativity column indicates how to evaluate
operators with the same precedence.
For example, the multiplicative operators have left-to-
right associativity.
This means that the expression a * b / c % d / e is
equivalent to ( ( ( ( a * b ) / c ) % d ) / e )
Parentheses are used to override precedence, and
expressions are always evaluated from the innermost
parenthesized expression first
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
INFIX TO POSTFIX CONVERSION
An algorithm to convert infix to a postfix expression as follows:
1. Fully parenthesize the expression.
2. Move all binary operators so that they replace their corresponding right
parentheses.
3. Delete all parentheses.
Example: Infix expression: a/b -c +d*e -a*c Fully parenthesized :
((((a/b)-c) + (d*e))-a*c))
:ab/e–de*+ac*
Example [Parenthesized expression]: Parentheses make the translation
process more difficult because the equivalent postfix expression will be
parenthesis-free.
The expression a*(b +c)*d which results abc +*d* in postfix. Figure shows the
translation process.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
The analysis of the examples suggests a precedence-based scheme for stacking and
unstacking operators.
The left parenthesis complicates matters because it behaves like a low-
precedence operator when it is on the stack and a high-precedence one when it is
not.
It is placed in the stack whenever it is found in the expression, but it is unstacked
only when its matching right parenthesis is found.
There are two types of precedence, in-stack precedence (isp) and incoming
precedence (icp).
Algorithm InfixToPostfix
Input: An infix expression
Output: Equivalent postfix expression
1. Initialize an empty stack
2. Push EOS (end of string marker) onto the stack
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
3. Repeat until token = EOS(end of string marker)
token ← getNextToken(symbol)
if token = OPERAND then
print symbol // directly add operand to output
else if token = RPAREN then
while stack[top] ≠ LPAREN do
print pop()
pop() // discard the left parenthesis
else // operator or LPAREN
while ISP[stack[top]] ≥ ICP[token] do
print pop()
push(token)
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
4. Repeat until stack is empty
token ← pop()
if token ≠ EOS then
print token
5. Print newline
ISP[] (In-Stack Precedence): precedence of operators already in the stack.
ICP[] (Incoming Precedence): precedence of incoming operators.
Operands → printed immediately.
Operators → compared using precedence rules before pushing to stack.
Parentheses → handled specially:
( gets pushed without popping.
) pops until matching ( is found.
RPAREN(Right Parenthesis)
Example run:
Infix: A + B * C
Steps → Postfix: A B C * +
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
EVALUATION OF POSTFIX EXPRESSION
The evaluation process of postfix expression is simpler
than the evaluation of infix expressions because there are
no parentheses to consider.
To evaluate an expression, make a single left-to-right scan
of it.
Place the operands on a stack until an operator is found.
Then remove from the stack, the correct number of
operands for the operator, perform the operation, and
place the result back on the stack and continue this
fashion until the end of the expression.
We then remove the answer from the top of the stack.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Pseudocode: Function to evaluate a postfix expression
Algorithm EvalPostfix
Input: Postfix expression
Output: Evaluated result
1. Initialize an empty stack
2. token ← getToken(symbol, n)
3. while token ≠ eos do
if token = OPERAND then
push(symbol - '0') // convert char digit to int
else
op2 ← pop() // remove top element
op1 ← pop() // remove next element
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
switch(token):
case PLUS:
push(op1 + op2)
case MINUS:
push(op1 - op2)
case TIMES:
push(op1 * op2)
case DIVIDE:
push(op1 / op2)
case MOD:
push(op1 % op2)
token ← getToken(symbol, n)
4. return pop() // final result from stack
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
Pseudocode: Function to get a token from the input string
Function getToken(symbol, n)
Input: symbol (character), n (index in expression string)
Output: precedence value (token type)
1. symbol ← expr[n]
2. n ← n + 1
3. switch(symbol) do
case '(' : return LPAREN
case ')' : return RPAREN
case '+' : return PLUS
case '-' : return MINUS
case '/' : return DIVIDE
case '*' : return TIMES
case '%' : return MOD
case end of string : return EOS
default : return OPERAND
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
C program ON Converts infix → postfix
Evaluates the postfix expression
Uses a function to get the next token from the input string
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
// --- Stack for infix to postfix ---
char stack[MAX];
int top = -1;
// Push function
void push(char item) {
if(top >= MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = item;
}
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
// Pop function
char pop() {
if(top == -1) {
return '\0';
} else {
return stack[top--];
}
}
// Return precedence of operators
int precedence(char op) {
switch(op) {
case '(': return 0;
case '+':
case '-': return 1;
case '*':
case '/': return 2;
}
return -1;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
// Get next token from input
char getToken(char expr[], int *index) {
return expr[(*index)++];
}
// Display current stack
void displayStack() {
if(top == -1) {
printf("Empty");
} else {
for(int i=0; i<=top; i++)
printf("%c", stack[i]);
}
}
// Convert infix to postfix with step-by-step display
void infixToPostfix(char infix[], char postfix[]) {
int i = 0, k = 0;
char token;
int step = 1;
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
printf("\n%-6s %-8s %-12s %-12s\n", "Step", "Token", "Stack", "Output");
printf("--------------------------------------------\n");
while((token = getToken(infix, &i)) != '\0') {
if(isdigit(token)) { // Operand
postfix[k++] = token;
} else if(token == '(') {
push(token);
} else if(token == ')') {
while(top != -1 && stack[top] != '(')
postfix[k++] = pop();
if(top != -1) pop(); // Remove '(' safely
} else { // Operator
while(top != -1 && precedence(stack[top]) >= precedence(token))
postfix[k++] = pop();
push(token);
}
// Display step
printf("%-6d %-8c %-12s %-12s\n", step++, token, stack, postfix);
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
while(top != -1)
postfix[k++] = pop();
postfix[k] = '\0';
}
// Evaluate postfix (numeric only)
int evalPostfix(char postfix[]) {
int evalStack[MAX];
int topEval = -1;
int i = 0;
char token;
while((token = postfix[i++]) != '\0') {
if(isdigit(token)) {
evalStack[++topEval] = token - '0';
} else {
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
int op2 = evalStack[topEval--];
int op1 = evalStack[topEval--];
switch(token) {
case '+': evalStack[++topEval] = op1 + op2; break;
case '-': evalStack[++topEval] = op1 - op2; break;
case '*': evalStack[++topEval] = op1 * op2; break;
case '/': evalStack[++topEval] = op1 / op2; break;
}
}
}
return evalStack[topEval];
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
int main() {
char infix[MAX], postfix[MAX];
printf("Enter infix expression (single-digit numbers only for evaluation): ");
scanf("%s", infix);
top = -1; // Reset stack before conversion
infixToPostfix(infix, postfix);
printf("\nPostfix expression: %s\n", postfix);
// Evaluate numeric postfix
int numeric = 1;
for(int i = 0; postfix[i]; i++) {
if(!isdigit(postfix[i]) && postfix[i] != '+' && postfix[i] != '-' &&
postfix[i] != '*' && postfix[i] != '/')
numeric = 0;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT
if(numeric) {
int result = evalPostfix(postfix);
printf("Evaluation result: %d\n", result);
} else {
printf("Postfix evaluation skipped (contains non-numeric operands).\n");
}
return 0;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIRMVIT