Week 5 Lecture 1

Stacks
A stack is a linear data structure where elements are stored in the LIFO (Last In First Out)
principle where the last element inserted would be the first element to be deleted.
Read more on:
https://www.javatpoint.com/data-structure-stack,
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

Stack Operations
 push(): When we insert an element in a stack then the operation is known as a push. If the stack
is full then the overflow condition occurs.
 pop(): When we delete an element from the stack, the operation is known as a pop. If the stack
is empty means that no element exists in the stack, this state is known as an underflow state.
 isEmpty(): It determines whether the stack is empty or not.
 isFull(): It determines whether the stack is full or not.'
 peek(): It returns the element at the given position.
 count(): It returns the total number of elements available in a stack.
 display(): It prints all the elements available in the stack.
 Search(): it searches a value in the stack.
Implementing Stacks Using C++ (there are some logical and syntax errors in the code,
simple copy pasting won’t work, you have to analyze the code)
1 – Initializing the stack array

2 - Checking for empty or full stack - O(1)

3 - Pusing value in a stack - O(1)

4 - poping value out of a stack - O(1)

5 - Counting total ellements in the stack - O(1)

6 – Peeking at certain index of stack - O(1)

7 – Change the value at specific index of stack - O(1)

8 – Search a value in the stack (linear search) - O(n)

9 - Display the all stack values - O(n)

10 – Delete the stack form the memory and main() function

Double Stacks
In the double stack data structure, one array is indeed used to store two stacks, but it’s not divided
into halves for each stack. Instead, the two stacks grow towards each other.
 Stack 1 starts from the beginning (index 0) of the array and grows towards the end.
 Stack 2 starts from the end of the array and grows towards the beginning.
 Both stacks can dynamically take up more space as long as there is unoccupied space in the
array. If they meet in the middle, the array is fully occupied and no more elements can be
pushed into either stack.
 push1(int x) and push2(int x) methods are used to add elements to the first and second stack
respectively. If there’s no space left, it will print “Stack Overflow”.
 pop1() and pop2() methods are used to remove elements from the first and second stack
respectively. If there are no elements left in the stack, it will print “Stack Underflow”.


Question related to stacks
Balanced Parentheses: Given a string of parentheses, brackets, and braces, determine whether they
are balanced. This is a classic problem that can be solved using a stack.
Minimum Element in Stack: Design a stack that supports push, pop, and retrieving the minimum
element in constant time. We need two stacks, one stack for storing the values, the second stack
only stores the minimum values.

It can be achieved using a variable to track the minimum value during push and pop operations is a
valid and efficient approach, and it provides constant time complexity for finding the minimum.

Another approach can be to use additional stack and allows you to maintain the minimum value
with each operation in constant time

Reversing a stack. It can be done using another stack

Reversing a stack using recursion.

Yes, when a recursive function is called, each invocation of the function creates a new frame on the
call stack. These frames store information about the function's local variables, parameters, and the
point in the code where the function was called. Each recursive call adds a new frame to the stack.
Week 6
Infix, Prefix and Postfix notations
Source: https://www.codingninjas.com/studio/library/expression-evaluation-using-stack
The way to write arithmetic expression is known as a notation. An arithmetic expression can be
written in three different but equivalent notations, i.e., without changing the essence or output of an
expression. These notations are:
 Infix
 Prefix
 Postfix

Infix notations are normal notations, that are used by us while write different mathematical
expressions. For example, (a + b – c)

The Prefix and Postfix notations are quite different.

Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For
example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish
Notation.

Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style, the operator is
postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is
equivalent to its infix notation a + b.

No Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+
2 (a + b) * c *+abc ab+c*
3 a * (b + c) *a+bc abc+*
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) * (c + d) *+ab+cd ab+cd+*
6 ((a + b) * c) - d -*+abcd ab+c*d-

When implementing a stack to solve the prefix, the sting (expression) is

evaluated form right to left.

When implementing a stack to solve the postfix, the sting (expression) is

evaluated form left to right.
Solving the postfix notation using stacks (right to left)
Postfix expression: 2 5 3 6 + * * 15 / 2 –
Character Action Operand Stack
2 Push to the operand stack 2
5 Push to the operand stack 5, 2
3 Push to the operand stack 3, 5, 2
6 Push to the operand stack 6, 3, 5, 2
+ Pop 6 and 3 from the stack 5, 2
6 + 3 = 9, push to operand stack 9 ,5, 2
* Pop 9 and 5 from the stack 2
9 * 5 = 45, push to operand stack 45, 2
* Pop 45 and 2 from the stack
45 * 2 = 90, push to stack 90
15 Push to stack 15, 90
/ Pop 15 and 90 from the stack
90 / 15 = 6, push to stack 6
2 Push to the stack 2, 6
- Pop 2 and 6 from the stack
6 - 2 = 4, push to stack 4

2 5 3 6 + * * 15 / 2 –
2 5 9 * * 15 / 2 –
2 45 * 15 / 2 –
90 15 / 2 –
62–
4
Solving the postfix notation using stacks (left to right)
Prefix expression: - / * 2 * 5 + 3 6 5 2

Character Action Operand Stack

2 Push to the operand stack 2
5 Push to the operand stack 5, 2
6 Push to the operand stack 6, 5, 2
3 Push to the operand stack 3, 6, 5, 2
+ Pop 3 and 6 from the stack 5, 2
3 + 6 = 9, push to operand stack 9, 5, 2
5 Push to the operand stack 5, 9, 5, 2
* Pop 5 and 9 from the stack 5, 2
5 * 9 = 45, push to operand stack 45, 5, 2
2 Push to operand stack 2, 45, 5, 2
* Pop 2 and 45 from the stack 5, 2
2 * 45 = 90, push to stack 90, 5, 2
/ Pop 90 and 5 from the stack 2
90 / 5 = 18, push to stack 18, 2
- Pop 18 and 2 from the stack
18 - 2 = 16, push to stack 16

-/*2*5+3652
-/*2*5952
- / * 2 45 5 2
- / 90 5 2
- 18 2
16
Initializing the stack

Push and Pop

Peek and IsEmpty
Evaluate Prefix
Main Function

Converting infix to postfix or prefix

No Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+
2 (a + b) * c *+abc ab+c*
3 a * (b + c) *a+bc abc+*
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) * (c + d) *+ab+cd ab+cd+*
6 ((a + b) * c) - d -*+abcd ab+c*d-

When to Push an Operator onto the Stack:

 If the stack is empty, push the scanned operator onto the stack.
 If the scanned operator is a left parenthesis (, push it onto the stack.
 If the scanned operator has higher precedence than the operator on the top of the stack, push it
onto the stack.

When to Pop an Operator from the Stack:

 If the scanned operator is a right parenthesis ), pop operators from the stack and add them to the
output until a left parenthesis ( is encountered. Then, pop and discard the left parenthesis.
 If the scanned operator has less than or equal to precedence than the operator on the top of the
stack, pop the operator from the stack and add it to the output.
 After fully scanning the infix expression, if there are still operators left in the stack, pop them
out and add them to the output.
Converting Infix Expressions to Postfix
Step-by-step dry run of converting the infix expression A + B * C / E - F to
postfix using a stack:
1. Input: A + B * C / E - F
2. Stack: Empty
3. Postfix: Empty

Step 1: Scan A, which is an operand. Add it to the postfix expression.

1. Input: + B * C / E - F
2. Stack: Empty
3. Postfix: A

Step 2: Scan +, which is an operator. As the stack is empty, push + onto the stack.
1. Input: B * C / E - F
2. Stack: +
3. Postfix: A

Step 3: Scan B, which is an operand. Add it to the postfix expression.

1. Input: * C / E - F
2. Stack: +
3. Postfix: A B

Step 4: Scan *, which is an operator. The operator on the top of the stack is +, and * has higher
precedence than +. So, push * onto the stack.
1. Input: C / E - F
2. Stack: + *
3. Postfix: A B

Step 5: Scan C, which is an operand. Add it to the postfix expression.

1. Input: / E - F
2. Stack: + *
3. Postfix: A B C

Step 6: Scan /, which is an operator. The operator on the top of the stack is *, and / has the same
precedence as *. So, pop * from the stack and add it to the postfix expression. Then, push / onto the
stack.
1. Input: E - F
2. Stack: + /
3. Postfix: A B C *

Step 7: Scan E, which is an operand. Add it to the postfix expression.

1. Input: - F
2. Stack: + /
3. Postfix: A B C * E

Step 8: Scan -, which is an operator. The operator on the top of the stack is /, and - has lower
precedence than /. So, pop / and + from the stack and add them to the postfix expression. Then,
push - onto the stack.
1. Input: F
2. Stack: -
3. Postfix: A B C * E / +
Step 9: Scan F, which is an operand. Add it to the postfix expression.
1. Input: Empty
2. Stack: -
3. Postfix: A B C * E / + F

Step 10: The input is empty. Pop all the remaining operators from the stack and add them to the
postfix expression.
1. Input: Empty
2. Stack: Empty
3. Postfix: A B C * E / + F –

So, the postfix expression of A + B * C / E - F = A B C * E / + F -.

Convert the infix expression (a + b) * c to postfix using a stack:

1. Input: (a + b) * c
2. Stack: Empty
3. Postfix: Empty

Step 1: Scan (, which is an operator. As the stack is empty, push ( onto the stack.
1. Input: a + b) * c
2. Stack: (
3. Postfix: Empty

Step 2: Scan a, which is an operand. Add it to the postfix expression.

1. Input: + b) * c
2. Stack: (
3. Postfix: a

Step 3: Scan +, which is an operator. As the operator on the top of the stack is (, push + onto the
stack.
1. Input: b) * c
2. Stack: ( +
3. Postfix: a

Step 4: Scan b, which is an operand. Add it to the postfix expression.

1. Input: ) * c
2. Stack: ( +
3. Postfix: a b

Step 5: Scan ), which is a closing parenthesis. Pop operators from the stack and add them to the
postfix expression until a matching opening parenthesis is found. Pop and discard the opening
parenthesis.
1. Input: * c
2. Stack: Empty
3. Postfix: a b +

Step 6: Scan *, which is an operator. As the stack is empty, push * onto the stack.
1. Input: c
2. Stack: *
3. Postfix: a b +

Step 7: Scan c, which is an operand. Add it to the postfix expression.

1. Input: Empty
2. Stack: *
3. Postfix: a b + c

Step 8: The input is empty. Pop all the remaining operators from the stack and add them to the
postfix expression.
1. Input: Empty
2. Stack: Empty
3. Postfix: a b + c *

So, the postfix expression of (a + b) * c = a b + c *.

Convert the infix expression a / b + c / d to postfix using a stack:

1. Input: a / b + c / d
2. Stack: Empty
3. Postfix: Empty

Step 1: Scan a, which is an operand. Add it to the postfix expression.

1. Input: / b + c / d
2. Stack: Empty
3. Postfix: a

Step 2: Scan /, which is an operator. As the stack is empty, push / onto the stack.
1. Input: b + c / d
2. Stack: /
3. Postfix: a

Step 3: Scan b, which is an operand. Add it to the postfix expression.

1. Input: + c / d
2. Stack: /
3. Postfix: a b

Step 4: Scan +, which is an operator. The operator on the top of the stack is /, and + has lower
precedence than /. So, pop / from the stack and add it to the postfix expression. Then, push + onto
the stack.
1. Input: c / d
2. Stack: +
3. Postfix: a b /

Step 5: Scan c, which is an operand. Add it to the postfix expression.

1. Input: / d
2. Stack: +
3. Postfix: a b / c

Step 6: Scan /, which is an operator. The operator on the top of the stack is +, and / has higher
precedence than +. So, push / onto the stack.
1. Input: d
2. Stack: + /
3. Postfix: a b / c

Step 7: Scan d, which is an operand. Add it to the postfix expression.

1. Input: Empty
2. Stack: + /
3. Postfix: a b / c d

Step 8: The input is empty. Pop all the remaining operators from the stack and add them to the
postfix expression.
1. Input: Empty
2. Stack: Empty
3. Postfix: a b / c d / +

So, the postfix expression of a / b + c / d = a b / c d / +.

Converting Infix Expressions to Prefix

Convert the infix expression ((a + b) * c) - d to prefix using a stack:
1. Input: ((a + b) * c) - d
2. Stack: Empty
3. Prefix: Empty

Step 1: Scan d, which is an operand. Add it to the prefix expression.

1. Input: ((a + b) * c) - d
1. Stack: Empty
2. Prefix: d

Step 2: Scan -, which is an operator. As the stack is empty, push - onto the stack.
1. Input: ((a + b) * c) - d
2. Stack: -
3. Prefix: d

Step 3: Scan ), which is a closing parenthesis. Push it onto the stack.

1. Input: ((a + b) * c) - d
2. Stack: - )
3. Prefix: d

Step 4: Scan c, which is an operand. Add it to the prefix expression.

1. Input: ((a + b) * c) - d
2. Stack: - )
3. Prefix: d c

Step 5: Scan *, which is an operator. As the operator on the top of the stack is ), push * onto the
stack.
1. Input: ((a + b) * c) - d
2. Stack: - ) *
3. Prefix: d c

Step 6: Scan ), which is a closing parenthesis. Push it onto the stack.

1. Input: ((a + b) * c) - d
2. Stack: - ) * )
3. Prefix: d c

Step 7: Scan b, which is an operand. Add it to the prefix expression.

1. Input: ((a + b) * c) - d
2. Stack: - ) * )
3. Prefix: d c b

Step 8: Scan +, which is an operator. As the operator on the top of the stack is ), push + onto the
stack.
1. Input: ((a + b) * c) - d
2. Stack: - ) * ) +
3. Prefix: d c b

Step 9: Scan a, which is an operand. Add it to the prefix expression.

1. Input: ((a + b) * c) - d
2. Stack: - ) * ) +
3. Prefix: d c b a

Step 10: Scan (, which is an opening parenthesis. Pop operators from the stack and add them to the
prefix expression until a matching closing parenthesis is found. Pop and discard the closing
parenthesis.
1. Input: ((a + b) * c) - d
2. tack: - ) *
3. Prefix: d c b a +

Step 11: Scan (, which is an opening parenthesis. Pop operators from the stack and add them to the
prefix expression until a matching closing parenthesis is found. Pop and discard the closing
parenthesis.
1. Input: ((a + b) * c) - d
2. Stack: -
3. Prefix: d c b a + *

Step 12: The input is empty. Pop all the remaining operators from the stack and add them to the
prefix expression.
1. Input: Empty
2. Stack: Empty
3. Prefix: d c b a + * -

So, the prefix expression of ((a + b) * c) - d = - * + a b c d.

Convert the infix expression (a + b) * c to prefix by reading it from right to left:

Input: (a + b) * c
Stack: Empty
Prefix: Empty

Step 1: Scan c, which is an operand. Add it to the prefix expression.

 Input: (a + b) * c
 Stack: Empty
 Prefix: c

Step 2: Scan *, which is an operator. As the stack is empty, push * onto the stack.
 Input: (a + b) * c
 Stack: *
 Prefix: c

Step 3: Scan ), which is a closing parenthesis. Push it onto the stack.

 Input: (a + b) * c
 Stack: * )
 Prefix: c

Step 4: Scan b, which is an operand. Add it to the prefix expression.

 Input: (a + b) * c
 Stack: * )
 Prefix: c b

Step 5: Scan +, which is an operator. As the operator on the top of the stack is ), push + onto the
stack.
 Input: (a + b) * c
 Stack: * ) +
 Prefix: c b

Step 6: Scan a, which is an operand. Add it to the prefix expression.

 Input: (a + b) * c
 Stack: * ) +
 Prefix: c b a

Step 7: Scan (, which is an opening parenthesis. Pop operators from the stack and add them to the
prefix expression until a matching closing parenthesis is found. Pop and discard the closing
parenthesis.
 Input: (a + b) * c
 Stack: *
 Prefix: c b a +

Step 8: The input is empty. Pop all the remaining operators from the stack and add them to the
prefix expression.
 Input: Empty
 Stack: Empty
 Prefix: c b a + *

So, the prefix expression of (a + b) * c = * + a b c.