Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Module-2 The Stack – Definition and examples, primitive operations, Example. Representing Stacks in C, Example: Infix, Postfix and Prefix,

converting an Expression from Infix to Prefix and Program. Text Book -1- Chapter – 2.1-2.3

Recursion – Recursive Definition and Processes, Recursion in C, Writing Recursive Programs. Recursions - Text Book -1-Chapter – 3.1-3.3

The Stack – Definition and examples

What is Stack Data Structure?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It behaves like a stack of plates, where the last plate added is

the first one to be removed.

Think of it this way:

● Pushing an element onto the stack is like adding a new plate on top.

● Popping an element removes the top plate from the stack.

LIFO (Last In First Out) Principle in Stack Data Structure:

This strategy states that the element that is inserted last will come out first. You can take a pile of plates kept on top of each other as a real-life

example. The plate which we put last is on the top and since we remove the plate that is at the top, we can say that the plate that was put last comes

out first.

Representation of Stack Data Structure:

Stack follows LIFO (Last In First Out) Principle so the element which is pushed last is popped first.

Types of Stack Data Structure:

● Fixed Size Stack : As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is

made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs.

Dr. Nataraju A B Page - 1

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

● Dynamic Size Stack : A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the

new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack.

Basic (Primitive) Operations on Stack Data Structure:

In order to make manipulations in a stack, there are certain operations provided to us.

● push() to insert an element into the stack

● pop() to remove an element from the stack

● top() Returns the top element of the stack.

● isEmpty() returns true if stack is empty else false.

● isFull() returns true if the stack is full else false.

Push Operation in Stack Data Structure:

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

Algorithm for Push Operation:

● Before pushing the element to the stack, we check if the stack is full .

● If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the element to the stack.

● Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is inserted at top position .

● The elements can be pushed into the stack till we reach the capacity of the stack.

Pop Operation in Stack Data Structure:

Dr. Nataraju A B Page - 2

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow

condition.

Algorithm for Pop Operation:

● Before popping the element from the stack, we check if the stack is empty .

● If the stack is empty (top == -1), then Stack Underflows and we cannot remove any element from the stack.

● Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1) and return the stored top value.

Top or Peek Operation in Stack Data Structure:

Returns the top element of the stack.

Algorithm for Top Operation:

● Before returning the top element from the stack, we check if the stack is empty.

● If the stack is empty (top == -1), we simply print “Stack is empty”.

● Otherwise, we return the element stored at index = top .

Dr. Nataraju A B Page - 3

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

isEmpty Operation in Stack Data Structure:

Returns true if the stack is empty, else false.

Algorithm for isEmpty Operation :

● Check for the value of top in stack.

● If (top == -1) , then the stack is empty so return true .

● Otherwise, the stack is not empty so return false .

isFull Operation in Stack Data Structure:

Returns true if the stack is full, else false.

Algorithm for isFull Operation:

● Check for the value of top in stack.

● If (top == capacity-1), then the stack is full so return true .

Dr. Nataraju A B Page - 4

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

● Otherwise, the stack is not full so return false .

Representing Stacks in C

Implementation of Stack Data Structure:

The basic operations that can be performed on a stack include push, pop, and peek. There are two ways to implement a stack –

● Using Array

● Using Linked List

In an array-based implementation, the push operation is implemented by incrementing the index of the top element and storing the new element at

that index. The pop operation is implemented by returning the value stored at the top index and then decrementing the index of the top element.

In a linked list-based implementation, the push operation is implemented by creating a new node with the new element and setting the next pointer of

the current top node to the new node. The pop operation is implemented by setting the next pointer of the current top node to the next node and

returning the value of the current top node.

// C program for array implementation of stack

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

// A structure to represent a stack

struct Stack {

int top;

unsigned capacity;

int* array;

Dr. Nataraju A B Page - 5

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

};

// function to create a stack of given capacity. It initializes size of stack as 0

struct Stack* createStack(unsigned capacity)

{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->capacity = capacity;

stack->top = -1;

stack->array = (int*)malloc(stack->capacity * sizeof(int));

return stack;

// Stack is full when top is equal to the last index

int isFull(struct Stack* stack)

return stack->top == stack->capacity - 1;

// Stack is empty when top is equal to -1

int isEmpty(struct Stack* stack)

return stack->top == -1;

// Function to add an item to stack. It increases top by 1

void push(struct Stack* stack, int item)

if (isFull(stack))

return;

stack->array[++stack->top] = item;

printf("%d pushed to stack\n", item);

// Function to remove an item from stack. It decreases top by 1

int pop(struct Stack* stack)

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack->top--];

Dr. Nataraju A B Page - 6

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

// Function to return the top from stack without removing it

int peek(struct Stack* stack)

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack->top];

// Driver program to test above functions

int main()

struct Stack* stack1 = createStack(100);

push(stack1, 10);

push(stack1, 20);

push(stack1, 30);

printf("%d popped from stack\n", pop(stack1));

return 0;

Output

10 pushed into stack

20 pushed into stack

30 pushed into stack

30 Popped from stack

Top element is : 20

Elements present in stack : 20 10

Advantages of Array Implementation:

● Easy to implement.

● Memory is saved as pointers are not involved.

Disadvantages of Array Implementation:

● It is not dynamic i.e., it doesn’t grow and shrink depending on needs at runtime. [But in case of dynamic sized arrays like vector in C++,

list in Python, ArrayList in Java, stacks can grow and shrink with array implementation as well].

● The total size of the stack must be defined beforehand.

Dr. Nataraju A B Page - 7

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Implementation of Stack Data Structure using Linked List:

// C program for linked list implementation of stack

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

// A structure to represent a stack

struct StackNode {

int data;

struct StackNode* next;

};

struct StackNode* newNode(int data)

struct StackNode* stackNode

= (struct StackNode*)malloc(sizeof(struct StackNode));

stackNode->data = data;

stackNode->next = NULL;

return stackNode;

int isEmpty(struct StackNode* root)

return !root;

void push(struct StackNode** root, int data)

struct StackNode* stackNode = newNode(data);

stackNode->next = *root;

*root = stackNode;

printf("%d pushed to stack\n", data);

int pop(struct StackNode** root)

if (isEmpty(*root))

return INT_MIN;

struct StackNode* temp = *root;

*root = (*root)->next;

Dr. Nataraju A B Page - 8

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

int popped = temp->data;

free(temp);

return popped;

int peek(struct StackNode* root)

if (isEmpty(root))

return INT_MIN;

return root->data;

int main()

struct StackNode* root = NULL;

push(&root, 10);

push(&root, 20);

push(&root, 30);

printf("%d popped from stack\n", pop(&root));

printf("Top element is %d\n", peek(root));

return 0;

Output

10 pushed to stack

20 pushed to stack

30 pushed to stack

30 popped from stack

Top element is 20

Elements present in stack : 20 10

Advantages of Linked List implementation:

 The linked list implementation of a stack can grow and shrink according to the needs at runtime.
 It is used in many virtual machines like JVM.

Disadvantages of Linked List implementation:

 Requires extra memory due to the involvement of pointers.
 Random accessing is not possible in stack.

Advantages of Stack Data Structure:

 Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable for a wide range of applications.

Dr. Nataraju A B Page - 9

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

 Efficiency: Push and pop operations on a stack can be performed in constant time (O(1)) , providing efficient access to data.
 Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element added to the stack is the first one removed. This behavior is useful in many

scenarios, such as function calls and expression evaluation.

 Limited memory usage: Stacks only need to store the elements that have been pushed onto them, making them memory-efficient compared to other data structures.

Disadvantages of Stack Data Structure:

 Limited access: Elements in a stack can only be accessed from the top, making it difficult to retrieve or modify elements in the middle of the stack.
 Potential for overflow: If more elements are pushed onto a stack than it can hold, an overflow error will occur, resulting in a loss of data.
 Not suitable for random access: Stacks do not allow for random access to elements, making them unsuitable for applications where elements need to be accessed in a

specific order.
 Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of elements that need to be stored is unknown or highly variable.

Example : Infix, Postfix and Prefix,

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 writing different mathematical expressions. 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.

Infix to Prefix Conversion

To convert infix to prefix, we can follow these steps:

1. Reverse the infix expression.

2. Convert the reversed infix expression to postfix.

3. Reverse the resulting postfix expression to get the prefix expression.

Infix to Prefix Conversion

To convert infix to prefix (a+b*c), we can reverse the infix expression, perform infix to postfix conversion on the reversed expression, and then reverse the resulting postfix

expression.

1. Reverse the infix expression: c * b + a

2. Perform infix to postfix conversion on the reversed expression.

3. Reverse the resulting postfix expression to get the prefix expression.

Step 1: Reverse the Infix Expression

The reversed infix expression is: c * b + a

Step 2: Perform Infix to Postfix Conversion

Using the same process as before:

1. Scan c: Add to output.

Dr. Nataraju A B Page - 10

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

○ Output: c

○ Stack: (empty)

2. Scan *: Push onto stack.

○ Output: c

○ Stack: *

3. Scan b: Add to output.

○ Output: c b

○ Stack: *

4. Scan +: Push onto stack.

○ Output: c b

○ Stack: *+

5. Scan a: Add to output.

○ Output: c b a

○ Stack: *+

Step 3: Pop Remaining Operators

6. Pop + and add to output.

○ Output: c b a +

○ Stack: *

7. Pop * and add to output.

○ Output: c b a + *

○ Stack: (empty)

Prefix Expression

The prefix expression for a + b * c is * + a b c.

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.

Example

Expression 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/+

Dr. Nataraju A B Page - 11

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Expression No Infix Notation Prefix Notation Postfix Notation

5 (a + b) * (c + d) *+ab+cd ab+cd+*

6 ((a + b) * c) - d -*+abcd ab+c*d-

Infix Expressions
Infix expressions are mathematical expressions where the operator is placed between its operands. This is the most common mathematical

notation used by humans. For example, the expression “2 + 3” is an infix expression, where the operator “+” is placed between the operands “2” and

“3”.

Infix notation is easy to read and understand for humans, but it can be difficult for computers to evaluate efficiently. This is because the order of

operations must be taken into account, and parentheses can be used to override the default order of operations.

Common way of writing Infix expressions:

● Infix notation is the notation that we are most familiar with. For example, the expression “2 + 3” is written in infix notation.

● In infix notation, operators are placed between the operands they operate on. For example, in the expression “2 + 3”, the addition operator

“+” is placed between the operands “2” and “3”.

● Parentheses are used in infix notation to specify the order in which operations should be performed. For example, in the expression “(2 +

3) * 4”, the parentheses indicate that the addition operation should be performed before the multiplication operation.

Operator precedence rules:

Infix expressions follow operator precedence rules, which determine the order in which operators are evaluated. For example, multiplication and

division have higher precedence than addition and subtraction. This means that in the expression “2 + 3 * 4”, the multiplication operation will be

performed before the addition operation.

Here’s the table summarizing the operator precedence rules for common mathematical operators:

Operator Precedence

Parentheses () Highest

Exponents ^ High

Multiplication * Medium

Dr. Nataraju A B Page - 12

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Division / Medium

Addition + Low

Subtraction – Low

Converting an Expression from Infix to Prefix and Program.

Write a program to convert an Infix expression to Postfix form.

Infix expression: The expression of the form “a operator b” (a + b) i.e., when an operator is in-between every pair of operands.

Postfix expression: The expression of the form “a b operator” (ab+) i.e., When every pair of operands is followed by an operator.

Input: A + B * C + D

Output: ABC*+D+

A + (B * C) parentheses for emphasis

A + (BC *) convert the multiplication

A (BC *) + convert the addition

ABC * +. postflx form

How to convert an Infix expression to a Postfix expression?

To convert infix expression to postfix expression, use the stack data structure. Scan the infix expression from left to right. Whenever we get an

operand, add it to the postfix expression and if we get an operator or parenthesis add it to the stack by maintaining their precedence.

Below are the steps to implement the above idea:

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, put it in the postfix expression.

3. Otherwise, do the following

● If the precedence and associativity of the scanned operator are greater than the precedence and associativity of the operator in the stack

[or the stack is empty or the stack contains a ‘(‘ ], then push it in the stack. [‘^‘ operator is right associative and other operators like ‘+‘,’–‘,’*‘ and ‘/‘

are left-associative].

1. Check especially for a condition when the operator at the top of the stack and the scanned operator both are ‘^‘. In this condition, the

precedence of the scanned operator is higher due to its right associativity. So it will be pushed into the operator stack.

Dr. Nataraju A B Page - 13

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

2. In all the other cases when the top of the operator stack is the same as the scanned operator, then pop the operator from the stack because

of left associativity due to which the scanned operator has less precedence.

● Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator.
1. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned

operator in the stack.)

4. If the scanned character is a ‘(‘, push it to the stack.

5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.

6. Repeat steps 2-5 until the infix expression is scanned.

7. Once the scanning is over, Pop the stack and add the operators in the postfix expression until it is not empty.

8. Finally, print the postfix expression.

Parsing Expression

As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into

either postfix or prefix notations and then computed.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// Function to return precedence of operators

int prec(char c) {

if (c == '^')

return 3;

else if (c == '/' || c == '*')

return 2;

else if (c == '+' || c == '-')

return 1;

else

return -1;

// Function to return associativity of operators

char associativity(char c) {

if (c == '^')

return 'R';

return 'L'; // Default to left-associative

// The main function to convert infix expression to postfix expression

void infixToPostfix(char s[]) {

char result[1000];

int resultIndex = 0;

int len = strlen(s);

char stack[1000];

int stackIndex = -1;

for (int i = 0; i < len; i++) {

char c = s[i];

// If the scanned character is an operand, add it to the output string.

if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {

Dr. Nataraju A B Page - 14

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

result[resultIndex++] = c;

// If the scanned character is an ‘(‘, push it to the stack.

else if (c == '(') {

stack[++stackIndex] = c;

}
// If the scanned character is an ‘)’, pop and add to the output string from the stack

// until an ‘(‘ is encountered.

else if (c == ')') {

while (stackIndex >= 0 && stack[stackIndex] != '(') {

result[resultIndex++] = stack[stackIndex--];

stackIndex--; // Pop '('

// If an operator is scanned

else {

while (stackIndex >= 0 && (prec(s[i]) < prec(stack[stackIndex])

|| prec(s[i]) == prec(stack[stackIndex])

&& associativity(s[i]) == 'L')) {

result[resultIndex++] = stack[stackIndex--];

stack[++stackIndex] = c;

// Pop all the remaining elements from the stack

while (stackIndex >= 0) {

result[resultIndex++] = stack[stackIndex--];

result[resultIndex] = '\0';

printf("%s\n", result);

// Driver code

int main() {

char exp[] = "a+b*(c^d-e)^(f+g*h)-i";

// Function call

infixToPostfix(exp);

return 0;

Few examples of INFIX to POSTFIX conversion …

Case - 1

To convert the infix expression a + b * c to postfix notation, we follow the Shunting Yard algorithm step by step. Here’s the detailed process:

1. Initialize:

○ Create an empty stack for operators and an empty list for the output.

2. Process each token:

○ If the token is an operand (i.e., variable or number), add it to the output list.

Dr. Nataraju A B Page - 15

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

○ If the token is an operator, pop operators from the stack to the output list until an operator with less precedence is at the top of the stack or the stack is empty, then push

the current operator onto the stack.

○ If the token is a left parenthesis (, push it onto the stack.

○ If the token is a right parenthesis ), pop from the stack to the output list until a left parenthesis is at the top of the stack. Remove the left parenthesis from the stack.

3. After processing all tokens:

○ Pop any remaining operators in the stack to the output list.

Step-by-Step Conversion:

1. Token: a

○ Operand: Add to output

○ Output: a

○ Stack: []

2. Token: +

○ Operator: Push onto stack

○ Output: a

○ Stack: ['+']

3. Token: b

○ Operand: Add to output

○ Output: a b

○ Stack: ['+']

4. Token: *

○ Operator: Push onto stack

○ Output: a b

○ Stack: ['+', '*']

5. Token: c

○ Operand: Add to output

○ Output: a b c

○ Stack: ['+', '*']

6. End of expression:

○ Pop remaining operators in stack to output

○ Output: a b c * +

○ Stack: []

Postfix Expression:

The postfix notation of the given infix expression a+b*c is: abc*+

This is the final converted postfix expression.

Case - 2

To convert the infix expression (a + b) * c to postfix notation, we use the Shunting Yard algorithm step by step. Here’s the detailed process:

1. Initialize:

○ Create an empty stack for operators and an empty list for the output.

Dr. Nataraju A B Page - 16

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

2. Process each token:

○ If the token is an operand (i.e., variable or number), add it to the output list.

○ If the token is an operator, pop operators from the stack to the output list until an operator with less precedence is at the top of the stack or the stack is empty, then push the current

operator onto the stack.

○ If the token is a left parenthesis (, push it onto the stack.

○ If the token is a right parenthesis ), pop from the stack to the output list until a left parenthesis is at the top of the stack. Remove the left parenthesis from the stack.

3. After processing all tokens:

○ Pop any remaining operators in the stack to the output list.

Step-by-Step Conversion:

1. Token: (

○ Left parenthesis: Push onto stack

○ Output: ``

○ Stack: ['(']

2. Token: a

○ Operand: Add to output

○ Output: a

○ Stack: ['(']

3. Token: +

○ Operator: Push onto stack

○ Output: a

○ Stack: ['(', '+']

4. Token: b

○ Operand: Add to output

○ Output: a b

○ Stack: ['(', '+']

5. Token: )

○ Right parenthesis: Pop until left parenthesis

○ Output: a b +

○ Stack: []

6. Token: *

○ Operator: Push onto stack

○ Output: a b +

○ Stack: ['*']

7. Token: c

○ Operand: Add to output

○ Output: a b + c

○ Stack: ['*']

8. End of expression:

○ Pop remaining operators in stack to output

○ Output: a b + c *

○ Stack: []

Postfix Expression:

The postfix notation of the given infix expression (a + b) * c is: ab+c*

Case - 3

Dr. Nataraju A B Page - 17

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

To convert the infix expression a + (b * (c - d) * x / y) - z to postfix notation, we will again use the Shunting Yard algorithm step by step:

Step-by-Step Conversion:

1. Initialize:

○ Create an empty stack for operators and an empty list for the output.

2. Process each token:

○ If the token is an operand (i.e., variable or number), add it to the output list.

○ If the token is an operator, pop operators from the stack to the output list until an operator with less precedence is at the top of the stack or the stack is empty, then push the current

operator onto the stack.

○ If the token is a left parenthesis (, push it onto the stack.

○ If the token is a right parenthesis ), pop from the stack to the output list until a left parenthesis is at the top of the stack. Remove the left parenthesis from the stack.

3. After processing all tokens:

○ Pop any remaining operators in the stack to the output list.

Process Tokens:

1. Token: a

○ Operand: Add to output

○ Output: a

○ Stack: []

2. Token: +

○ Operator: Push onto stack

○ Output: a

○ Stack: ['+']

3. Token: (

○ Left parenthesis: Push onto stack

○ Output: a

○ Stack: ['+', '(']

4. Token: b

○ Operand: Add to output

○ Output: a b

○ Stack: ['+', '(']

5. Token: *

○ Operator: Push onto stack

○ Output: a b

○ Stack: ['+', '(', '*']

6. Token: (

○ Left parenthesis: Push onto stack

○ Output: a b

○ Stack: ['+', '(', '*', '(']

7. Token: c

○ Operand: Add to output

○ Output: a b c

○ Stack: ['+', '(', '*', '(']

8. Token: -

○ Operator: Push onto stack

○ Output: a b c

○ Stack: ['+', '(', '*', '(', '-']

Dr. Nataraju A B Page - 18

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

9. Token: d

○ Operand: Add to output

○ Output: a b c d

○ Stack: ['+', '(', '*', '(', '-']

10. Token: )

○ Right parenthesis: Pop until left parenthesis

○ Output: a b c d -

○ Stack: ['+', '(', '*']

11. Token: *

○ Operator: Pop from stack (same precedence) then push

○ Output: a b c d - *

○ Stack: ['+', '(', '*']

12. Token: x

○ Operand: Add to output

○ Output: a b c d - x *

○ Stack: ['+', '(', '*']

13. Token: /

○ Operator: Push onto stack

○ Output: a b c d - * x

○ Stack: ['+', '(', '*', '/']

14. Token: y

○ Operand: Add to output

○ Output: a b c d - x y / *

○ Stack: ['+', '(', '*', '/']

15. Token: )

○ Right parenthesis: Pop until left parenthesis

○ Output: a b c d - x y / *

○ Stack: ['+', '(']

16. Token: -

○ Operator: Pop from stack until lower precedence then push

○ Output: a b c d - x y / * +

○ Stack: ['-']

17. Token: z

○ Operand: Add to output

○ Output: a b c d - x y / * + z

○ Stack: ['-']

18. End of expression:

○ Pop remaining operators in stack to output

○ Output: a b c d - x y / * + z -

○ Stack: []

Postfix Expression:

The postfix notation of the given infix expression “a + (b * (c - d) * x / y) - z” is: a b c d - * x * y / + z -

This is the final converted postfix expression.

Recursion – Recursive Definition and Processes,

Dr. Nataraju A B Page - 19

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

Recursion means "defining a problem in terms of itself". This can be a very powerful tool in writing algorithms. Recursion comes directly from

Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i)

= F(i-1) + F(i-2)

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function

Properties of Recursion:

Recursion has some important properties. Some of which are mentioned below:

● The primary property of recursion is the ability to solve a problem by breaking it down into smaller sub-problems, each of which can be

solved in the same way.

● A recursive function must have a base case or stopping criteria to avoid infinite recursion.

● Recursion involves calling the same function within itself, which leads to a call stack.

● Recursive functions may be less efficient than iterative solutions in terms of memory and performance.

Types of Recursion:

1. Direct recursion: When a function is called within itself directly it is called direct recursion. This can be further categorized into four

types:

● Tail recursion,

● Head recursion,

● Tree recursion and

● Nested recursion.

2. Indirect recursion: Indirect recursion occurs when a function calls another function that eventually calls the original function and it

forms a cycle.

Factorial Function

5 ! = 5*4*3*2*1 =>120

this outcome can be obtained using loops / recursion

n ! = 1 if n==0

n ! = n * (n-1) * (n-2) * …. * 1 if n > 0

// C program to find factorial of given number

#include <stdio.h>

// function to find the factorial of given number

unsigned int factorial(unsigned int n)

if (n == 0)

return 1;

return n * factorial(n - 1);

Dr. Nataraju A B Page - 20

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

int main()

int num = 5;

printf("Factorial of %d is %d", num, factorial(num));

return 0;

Fibonacci Sequence

The Fibonacci sequence is the sequence of integers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

// Fibonacci Series using Recursion

#include <stdio.h>

int fib(int n)

if (n <= 1)

return n;

return fib(n - 1) + fib(n - 2);

int main()

int n = 9;

printf("%dth Fibonacci Number: %d", n, fib(n));

return 0;

Binary Search

Dr. Nataraju A B Page - 21

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

The algorithm for binary search looks like this

// C program to implement binary search using recursion

#include <stdio.h>

// A recursive binary search function. It returns location

// of x in given array arr[l..r] if present, otherwise -1

int binarySearch(int arr[], int l, int r, int x)

// checking if there are elements in the subarray

if (r >= l) {

// calculating mid point

int mid = l + (r - l) / 2;

// If the element is present at the middle itself

if (arr[mid] == x)

return mid;

// If element is smaller than mid, then it can only

// be present in left subarray

if (arr[mid] > x) {

return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present in right

// subarray

return binarySearch(arr, mid + 1, r, x);

// We reach here when element is not present in array

return -1;

// driver code

int main(void)

// taking a sorted array

int arr[] = { 2, 3, 4, 10, 40 };

int size = sizeof(arr) / sizeof(arr[0]);

// element to be searched

int x = 10;

Dr. Nataraju A B Page - 22

Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore

// calling binary search

int index = binarySearch(arr, 0, size - 1, x);

if (index == -1) {

printf("Element is not present in array");

else {

printf("Element is present at index %d", index);

return 0;

Recursion in C,

A xxxxxx

Writing Recursive Programs. Recursions

A xxxxxx

Dr. Nataraju A B Page - 23