CH 2: Stack

2.1. Basic Concept of Stack, Stack as an ADT, Stack Operations, Stack

Applications
2.2 Conversion from infix to postfix/prefix expression, Evaluation of postfix/ prefix
expressions
Introduction

● A stack is an ordered collection of items into which new items may be

inserted and from which items may be deleted at one end, called the top of
the stack.
● The deletion and insertion in a stack is done from top of the stack.
● The following fig shows the stack containing items:
Introduction [2]

● Intuitively, a stack is like a pile of plates where we can only (conveniently)

remove a plate from the top and can only add a new plate on the top.
● In computer science we commonly place numbers on a stack, or perhaps
place records on the stack.
Applications of Stack

Stack is used directly and indirectly in the following fields:

● To evaluate the expressions (postfix, prefix)

● To keep the page-visited history in a Web browser
● To perform the undo sequence in a text editor
● Used in recursion
● To pass the parameters between the functions in a C program
● Can be used as an auxiliary data structure for implementing algorithms
● Can be used as a component of other data structures
Stack Operation

- The following operations can be performed on a stack:

- PUSH operation: The push operation is used to add (or push or insert)
elements in a stack
- When we add an item to
a stack, we say that we
pushed it onto the stack.
- The last item put into the
stack is at the top.
Stack Operation [2]

● POP operation: The pop operation is used to remove or delete the top
element from the stack.
● When we remove an
item, we say that we
popped it from the
stack.
● When an item popped,
it is always the top
item which is removed.
Stack Operation [3]
● The PUSH and the POP operations are the basic or primitive operations on a
stack.
Some others operations are:
● CreateEmptyStack operation: This operation is used to create an empty
stack.
● IsFull operation: The isfull operation is used to check whether the stack is full
or not ( i.e. stack overflow)
● IsEmpty operation: The isempty operation is used to check whether the stack
is empty or not. (i. e. stack underflow)
● Top operations: This operation returns the current item at the top of the stack.
However this operation doesn’t remove the current item.
Stack as an ADT
A stack of elements of type T is a finite sequence of elements of T together with the
following operations:
● CreateEmptyStack(S): Create or make stack S be an empty stack
● Push(S, x): Insert x at one end of the stack, called its top
● Top(S): If stack S is not empty; then retrieve the element at its top but don’t
delete.
● Pop(S): If stack S is not empty; then delete the element at its top
● IsFull(S): Determine if S is full or not.
Return true if S is full stack; return false otherwise
● IsEmpty(S): Determine if S is empty or not.
Return true if S is an empty stack; return false otherwise.
Stack Implementation

Steps:

1. Initially, we get empty stack. The top of an empty stack is set to -1.
2. Next, we push an element into the stack. The top of the stack will now point to
the element just pushed.
3. Whenever, we push element into the stack, the top is incremented so as to
point to the recent element.
4. Whenever a pop operation is performed, the top element is removed from the
stack and top is decrement to point to the next element.
5. If the stack becomes empty, the top will be set to -1.
Stack Implementation [2]
Stack Implementation [3]

● Using array - Static Stack Implementation

● Using linked list - Dynamic Stack implementation

Static Stack Representation in C Dynamic Stack

Representation in C

struct Stack{
struct Node{
Int top;
int data;
Int data[MAX];
struct Node *next;
Static Stack Implementation

Algorithm InitializeEmptyStack(S)

1. Start
2. Assign the value to top to -1. ie s->top = -1
3. Stop
Static Stack Implementation[2]

Algorithm isFull(S)

1. Start
2. Check if the top of S is equal to MAX-1, return true
ie
if(s->top == MAX-1)
return true;
3. Else return false
4. Stop
Static Stack Implementation[3]

Algorithm isEmpty(S)

1. Start
2. Check if the top of S is equal to -1, return true
ie
if(s->top == -1)
return true;
3. Else return false
4. Stop
Static Stack Implementation[4]

Algorithm push(S,x)

1. Start
2. Check if the S is full,
2.1. if full then display “Stack is full” and exit
2.2. Else, go to step 3
3. Increment top by 1 ie s->top += 1
4. Place the item x into “top” ie: s->items[s->top] = x
5. Stop
Static Stack Implementation[4]

Algorithm pop(S)

1. Start
2. Check if the S is empty,
2.1. if empty then display “Stack is empty” and exit
2.2. Else, go to step 3
3. Place the item at “top” to x ie:
x = s->items[s->top]
4. Decrement top by 1 ie s->top -= 1
5. Stop
Dynamic Stack Implementation

Algorithm InitializeEmptyStack(S)

1. Start
2. Assign S to null pointer
3. Stop
Dynamic Stack Implementation[2]

Algorithm isFull(S)

1. Start
2. Try allocating a new node as new
3. If new is a valid pointer, then

3.1. free new

3.2. return false

1. Else if new is null, return true.

2. Stop
Dynamic Stack Implementation[3]

Algorithm isEmpty(S)

1. Start
2. Check if S is null,
3. If so, return true
4. Else if S is a valid pointer, return false.
5. Stop
Dynamic Stack Implementation[4]
Algorithm push(S,x)
1. Start
2. Check if S is full, if so then
2.1 display “Stack is full”
2.2 return
1. Allocate a new node as newNode with data as x.
2. Start with a node pointer p = S
3. Move p to next node until p->next != null
4. Set p->next = newNode.
5. Stop
Dynamic Stack Implementation[4]
Algorithm pop(S)
1. Start
2. Check if S is empty, if so then
2.1 display “Stack is empty”
2.2 return
1. Initialize a node pointer p = S
2. Set x = p->data and S = p->next
3. Delete p
4. Return the value of x
5. Stop
Infix, Prefix and Postfix Notation
● One of the applications of the stack is to evaluate the arithmetic expression.
● We can represent the arithmetic expressions following three types of notation:
○ Infix Prefix Postfix
● Infix expression: It is an ordinary mathematical notation of expression where
operator is written in between the operands.
Example: A+B. Here ‘+’ is an operator and A and B are called operands
● Prefix notation: In prefix notation the operator precedes the two operands. That
is the operator is written before the operands. It is also called polish notation.
Example: +AB
● Postfix notation: In postfix notation the operators are written after the operands
so it is called the postfix notation (post mean after). In this notation the operator
follows the two operands.
Example: AB+
● Both prefix and postfix are parenthesis free expressions.
Infix, Prefix and Postfix Notation [2]

● Examples: [find the types]

○ A+B
○ + AB
○ AB +
○ (A + B) * C
○ *+ABC
○ AB+C*
Infix to Postfix Conversion
● First convert the sub-expression to postfix that is to be evaluated first and
repeat this process.
● Substitute intermediate postfix sub-expression by any variable whenever
necessary that makes it easy to convert.
● To convert an infix expression to its postfix equivalent:
○ We first convert the innermost parentheses to postfix, resulting as a new operand
○ In this fashion parenthesis can be successively eliminated until the entire expression is
converted
○ The last pair of parenthesis to be opened within a group of parenthesis encloses the first
expression within the group to be transformed
○ This last in, first-out behavior suggests the use of a stack
Infix to Postfix Conversion [2]
Precedence rule:
● While converting infix to postfix you have to consider the precedence rule,
and the precedence rules are as follows:
○ Exponentiation ( the expression A$B is A raised to the B power, so that 3$2=9)
○ Multiplication/Division
○ Addition/Subtraction
● When un-parenthesized operators of the same precedence are scanned, the
order is assumed to be left to right except in the case of exponentiation,
where the order is assumed to be from right to left.
○ A+B+C means (A+B)+C
○ A$B$C means A$(B$C)
● By using parenthesis we can override the default precedence. Ex: A + (B* C).
Infix to Postfix Conversion [3]

● Use the following rule to convert it in postfix:

1. Parenthesis for emphasis

2. Convert the multiplication

3. Convert the addition

4. Post-fix form
Infix to Postfix Conversion [4]

A + (B * C). Infix form

=>A + (B * C)

=>A + (BC*) Convert the Multiplication

=>A (BC*) + Convert the addition

=>ABC*+ Post-fix form

Infix to Postfix Conversion [4]
Algorithm:
1. Scan one character at a time of an infix expression from left to right
2. Opstack = the empty stack
3. Repeat till there is data in infix expression
a. if scanned character is ‘(‘ then push it to opstack
b. if scanned character is operand then push it to poststack
c. if scanned character is operator then
if(opstack!=-1)
while(precedence (opstack[otos])>precedence(scan character)) then
pop and push it into poststack
Otherwise
push into opstack
d. if scanned character is ‘)’ then
pop and push into poststack until ‘(‘ is not found and ignore both symbols
4. pop and push into poststack until opstack is not empty.
5. Return
Infix to Postfix Conversion [5]
Algorithm Tracing: Infix Expression - ((A-(B+C))*D)$(E+F)
Infix to Postfix Conversion [5]

Convert the infix expression to postfix

Infix to prefix conversion
● The precedence rule is same as that of previous case; only change is that the
operator is placed before the operands rather than after them.
● The prefix of
A+B-C is -+ABC. Ex:
A $ B * C – D + E / F / (G + H)
● Ex: => A $ B * C – D + E / F /(+GH)
=> $AB* C – D + E / F /(+GH)
A+B-C (infix) => *$ABC-D+E/F/(+GH)
=> *$ABC-D+(/EF)/(+GH)
=>(+AB)-C => *$ABC-D+//EF+GH
=> -+ABC (prefix) => (-*$ABCD) + (//EF+GH)
=> +-*$ABCD//EF+GH
Infix to prefix conversion[2]

Algorithm

● Step 1: Reverse the infix expression. Note that while reversing the infix
expression, the left and right parentheses are interchanged.
● Step 2: Obtain the postfix expression of the input expression as obtained in
[1].
● Step 3: Reverse the postfix expression to obtain the prefix expression.
Infix to prefix conversion[3]

● Ex: Infix expression: (A+B$C)*D+E$5

● String reversal => 5$E+D*(C$B+A)
● Obtaining the postfix expression of the given infix as:

5E$DCB$A+*+

● Reverse the result to get prefix expression:

+*+A$BCD$E5
Infix to prefix conversion[4]

Obtain the prefix expression of the given expressions:

Evaluating postfix expression

Algorithm

1. Add the unique symbol # at the end of array pstack.

2. Scan the symbol of postfix expression one by one from the left to right.
3. Do the following with each symbol until # is encountered:
a. If the symbol is operand, push into stack.
b. If the symbol is operator, the pop last 2 elements of the stack and evaluate it as :
Pstack[top-1] operator pstack[top]
Push the result into the stack
4. Pop the element of the stack which will be the value of evaluation of postfix
expression.
Evaluating postfix expression [2]
Ex: Evaluation of

ABCD$+*EF$GH/*-

Where A=4,B=5, C=4,

D=2, E=2, F=2, G=9 & F=3

DO THIS:
123+*321-+* => ??
Evaluation of prefix expression

Algorithm:

1. Begin with initializing opndstack as an empty operand stack.

2. Scan infix expression one char at a time from right to left.
3. Do the following until no more characters in infix expressions.
a. If the scan char is operand, push it to opndstack
b. If the scan char is operator, pop opndstack[top] and opndstack[top-1] and perform the
specified operation as:
Opndstack[top] operator opndstack[top-1]
Push the result into stack
4. Pop opndstack and display the required value.
Evaluation of prefix expression[2]

Ex: -*+4325 Do THIS:

/+53–42
Check for balancing of parenthesis
Algorithm:
1. Declare a character stack S as empty stack.
2. Now traverse the expression string from left to right.
3. If the current character is a starting parenthesis (‘(‘ or ‘{‘ or ‘[‘) then push it
to S.
4. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from
stack and if the popped character is the matching starting bracket then ok,
else brackets are not balanced.
5. After complete traversal, if there is some starting bracket left in stack then
“not balanced”
Check for balancing of parenthesis[2]