Iteration in Programming

 

📌 Iteration in Programming

Iteration refers to the process of executing a set of instructions repeatedly until a certain condition is met. It is commonly implemented using loops.

---

1️⃣ Types of Iteration (Loops)

(a) Entry-Controlled Loops (Condition checked first)

🔹 For Loop → Used when the number of iterations is known.
🔹 While Loop → Used when the number of iterations is not known in advance.

(b) Exit-Controlled Loop (Condition checked after execution)

🔹 Do-While Loop → Executes at least once before checking the condition.

---

2️⃣ Iteration Using Loops in C

📌 (a) For Loop (Definite Iteration)

#include <stdio.h>
int main() {
    for (int i = 1; i <= 5; i++) {
        printf("Iteration %d\n", i);
    }
    return 0;
}

🔹 Output:

nginx

Iteration 1
Iteration 2
Iteration 3
Iteration 4
Iteration 5

---

📌 (b) While Loop (Indefinite Iteration)

#include <stdio.h>
int main() {
    int i = 1;
    while (i <= 5) {
        printf("Iteration %d\n", i);
        i++;
    }
    return 0;
}

🔹 Used when the number of repetitions is unknown beforehand.

---

📌 (c) Do-While Loop (Execute at Least Once)

#include <stdio.h>
int main() {
    int i = 1;
    do {
        printf("Iteration %d\n", i);
        i++;
    } while (i <= 5);
    return 0;
}

🔹 Executes at least once, even if the condition is false.

---

3️⃣ Iteration in Arrays (Traversing Elements)

#include <stdio.h>
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < size; i++) {
        printf("Element %d: %d\n", i, arr[i]);
    }
    return 0;
}

🔹 Iterates through an array using a loop.

---

4️⃣ Infinite Loops (Use with Caution!)

while (1) { 
    printf("This is an infinite loop!\n"); 
}

🔹 Use break to exit an infinite loop.

 

📌 Evaluation of Postfix Expression Using Stack

Postfix notation (Reverse Polish Notation - RPN) is an operator notation where operators are placed after their operands. This eliminates the need for parentheses and follows a straightforward evaluation using a stack.

---

1️⃣ Why Use Postfix Notation?

✅ No Parentheses Needed → Operator precedence is naturally handled.
✅ Easier Computation → Uses a stack for evaluation.
✅ Used in Compilers & Calculators → Faster execution.

---

2️⃣ Algorithm for Evaluating a Postfix Expression

1️⃣ Scan the postfix expression from left to right.
2️⃣ If an operand (0-9, A-Z) appears, push it onto the stack.
3️⃣ *If an operator (+, -, , /, ^) appears:

• Pop the top two elements from the stack.
• Apply the operator on these elements.
• Push the result back onto the stack.
  4️⃣ Final value in the stack is the result.

---

3️⃣ Example Walkthrough

Evaluate:

6 2 + 5 * 8 4 / -

🔹 Step-by-step Stack Processing

Step	Symbol	Stack After Processing
1	6	6
2	2	6 2
3	+	8
4	5	8 5
5	*	40
6	8	40 8
7	4	40 8 4
8	/	40 2
9	-	38

✅ Final Answer: 38

---

4️⃣ C Program: Evaluate Postfix Expression Using Stack

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

// Push function
void push(int value) {
    stack[++top] = value;
}

// Pop function
int pop() {
    if (top == -1) return -1;
    return stack[top--];
}

// Evaluate postfix expression
int evaluatePostfix(char* postfix) {
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(postfix[i] - '0');  // Convert char to int
        } else {
            int val2 = pop();
            int val1 = pop();
            switch (postfix[i]) {
                case '+': push(val1 + val2); break;
                case '-': push(val1 - val2); break;
                case '*': push(val1 * val2); break;
                case '/': push(val1 / val2); break;
            }
        }
    }
    return pop();
}

int main() {
    char postfix[MAX];
    printf("Enter postfix expression: ");
    scanf("%s", postfix);
    
    printf("Result: %d\n", evaluatePostfix(postfix));
    return 0;
}

---

5️⃣ Complexity Analysis

🔹 Time Complexity: O(n) (Each character is processed once).
🔹 Space Complexity: O(n) (For stack storage).

---

6️⃣ Summary Table of Postfix Evaluation Steps

Operation	Time Complexity
Scanning Expression	O(n)
Push Operand	O(1)
Pop Operand	O(1)
Compute & Push Result	O(1)
Final Result	O(1)

 

📌 Application of Stack: Prefix and Postfix Expressions

Stacks are extensively used in expression evaluation and conversion, particularly for handling prefix and postfix expressions. These notations eliminate the need for parentheses and operator precedence rules, making computations more efficient.

🚀 Topics Covered:

✅ Infix, Prefix, and Postfix Notations
✅ Why Stacks are Used in Expression Evaluation
✅ Conversion from Infix to Postfix & Prefix
✅ Evaluating Postfix Expressions using Stack

---

1️⃣ Expression Notations

(a) Infix Notation (Standard Form)

• Operators are between operands.
• Requires operator precedence and parentheses for clarity.
• Example:

  
  (3 + 5) * 2
  

(b) Prefix Notation (Polish Notation)

• Operators before operands.
• Example:

  
  * + 3 5 2  → Equivalent to (3 + 5) * 2
  

(c) Postfix Notation (Reverse Polish Notation - RPN)

• Operators after operands.
• Example:

  
  3 5 + 2 *  → Equivalent to (3 + 5) * 2
  

💡 Why Use Prefix/Postfix?

• No need for parentheses.
• Easier and faster computation using stacks.
• Widely used in compilers and calculators.

---

2️⃣ Why Stacks are Used in Expression Evaluation?

Stacks help in: ✔ Converting infix expressions to postfix or prefix.
✔ Evaluating postfix expressions efficiently.

---

3️⃣ Conversion: Infix to Postfix Using Stack

Algorithm to Convert Infix to Postfix

1️⃣ Scan the infix expression from left to right.
2️⃣ Operands (A-Z, 0-9) → Directly append to the result.
3️⃣ *Operators (+, -, , /, ^) → Push to stack, considering precedence.
4️⃣ Parentheses Handling

• '(' → Push to stack.
• ')' → Pop from stack until '(' is found.
  5️⃣ Pop remaining operators after scanning.

Example:

Convert:

A + B * C  

🔹 Stack Process

Step	Symbol	Stack	Postfix Expression
1	A		A
2	+	+	A
3	B	+	A B
4	*	+ *	A B
5	C	+ *	A B C
6	(End)		A B C * +

✅ Postfix Expression:

A B C * +

C Implementation: Infix to Postfix Conversion

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

// Push function
void push(char c) {
    stack[++top] = c;
}

// Pop function
char pop() {
    if (top == -1) return -1;
    return stack[top--];
}

// Operator precedence function
int precedence(char c) {
    if (c == '^') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;
}

// Convert infix to postfix
void infixToPostfix(char* infix) {
    char postfix[MAX];
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        if (isalnum(infix[i])) {  
            postfix[j++] = infix[i];  // Append operand to postfix
        } 
        else if (infix[i] == '(') {
            push(infix[i]);
        } 
        else if (infix[i] == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop();  // Remove '('
        } 
        else {
            while (top != -1 && precedence(stack[top]) >= precedence(infix[i])) {
                postfix[j++] = pop();
            }
            push(infix[i]);
        }
    }

    while (top != -1) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';
    
    printf("Postfix: %s\n", postfix);
}

int main() {
    char infix[MAX];
    printf("Enter infix expression: ");
    scanf("%s", infix);
    
    infixToPostfix(infix);
    return 0;
}

🔹 Time Complexity: O(n)

---

4️⃣ Evaluating Postfix Expression Using Stack

Algorithm for Postfix Evaluation

1️⃣ Scan the postfix expression from left to right.
2️⃣ Operands (A-Z, 0-9) → Push onto stack.
3️⃣ *Operators (+, -, , /, ^) → Pop two operands, apply the operation, push result.
4️⃣ Final value in the stack is the result.

Example:

Evaluate:

6 2 + 5 * 8 4 / -

Step	Symbol	Stack After Processing
1	6	6
2	2	6 2
3	+	8
4	5	8 5
5	*	40
6	8	40 8
7	4	40 8 4
8	/	40 2
9	-	38

✅ Final Answer: 38

---

C Implementation: Postfix Evaluation

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

// Push function
void push(int value) {
    stack[++top] = value;
}

// Pop function
int pop() {
    if (top == -1) return -1;
    return stack[top--];
}

// Evaluate postfix expression
int evaluatePostfix(char* postfix) {
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(postfix[i] - '0');  // Convert char to int
        } else {
            int val2 = pop();
            int val1 = pop();
            switch (postfix[i]) {
                case '+': push(val1 + val2); break;
                case '-': push(val1 - val2); break;
                case '*': push(val1 * val2); break;
                case '/': push(val1 / val2); break;
            }
        }
    }
    return pop();
}

int main() {
    char postfix[MAX];
    printf("Enter postfix expression: ");
    scanf("%s", postfix);
    
    printf("Result: %d\n", evaluatePostfix(postfix));
    return 0;
}

🔹 Time Complexity: O(n)

---

5️⃣ Summary Table: Stack Operations in Expression Handling

Operation	Time Complexity
Infix to Postfix	O(n)
Postfix Evaluation	O(n)
Prefix Evaluation	O(n)

---

Push & Pop, Array and Linked Implementation of Stack in C

 

1️⃣ Stack Using Array in C

An array-based stack uses a fixed-size array to store elements, and a top variable to track the topmost element.

📌 Structure of Stack using Array

#include <stdio.h>
#define MAX 100  // Maximum stack size

int stack[MAX];  // Array to store stack elements
int top = -1;    // Stack is empty initially

// Push operation (Insert an element)
void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = value;
}

// Pop operation (Remove an element)
int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

// Display Stack Elements
void display() {
    if (top == -1) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack elements: ");
    for (int i = top; i >= 0; i--)
        printf("%d ", stack[i]);
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    display();
    
    printf("Popped: %d\n", pop());
    display();
    
    return 0;
}

🔹 Time Complexity:

• Push: O(1)
• Pop: O(1)
• Display: O(n)

---

2️⃣ Stack Using Linked List in C

A linked list-based stack dynamically allocates memory, so there's no size limitation. Each node contains a data value and a pointer to the next node.

📌 Structure of Stack using Linked List

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Top pointer to track stack top
struct Node* top = NULL;

// Push operation (Insert an element)
void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Heap Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

// Pop operation (Remove an element)
int pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    int value = top->data;
    struct Node* temp = top;
    top = top->next;
    free(temp);
    return value;
}

// Display Stack Elements
void display() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }
    struct Node* temp = top;
    printf("Stack elements: ");
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    display();

    printf("Popped: %d\n", pop());
    display();

    return 0;
}

🔹 Time Complexity:

• Push: O(1)
• Pop: O(1)
• Display: O(n)

---

3️⃣ Key Differences: Array vs. Linked List Stack

Feature	Stack Using Array	Stack Using Linked List
Size	Fixed, pre-defined	Dynamic, no limit
Memory Usage	Uses contiguous memory	Uses extra memory for pointers
Insertion/Deletion	O(1) but size limited	O(1) and dynamic
Overflow Risk	Yes (if array is full)	No (unless heap is full)
Underflow Risk	Yes (if stack is empty)	Yes (if stack is empty)

Stacks: Abstract Data Type & Primitive Stack Operations

 📌 Stacks: Abstract Data Type & Primitive Stack Operations

A stack is a fundamental Abstract Data Type (ADT) that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. Stacks are widely used in programming for tasks like expression evaluation, recursion management, and memory allocation.

In this post, we will cover:
✅ Definition & Characteristics of Stacks
✅ Stack Representation
✅ Basic Stack Operations (Push, Pop, Peek, and IsEmpty)
✅ Applications of Stacks

---

1️⃣ Stack as an Abstract Data Type (ADT)

A Stack ADT defines a collection of elements with the following operations:

• Push → Adds an element to the top of the stack.
• Pop → Removes and returns the top element of the stack.
• Peek (Top) → Returns the top element without removing it.
• isEmpty → Checks if the stack is empty.

A stack can be implemented using:

• Arrays (Fixed size, faster access but less flexible).
• Linked Lists (Dynamic size, but requires extra memory for pointers).

---

2️⃣ Stack Representation

(a) Array-Based Stack

Each element is stored in an array, and a variable top keeps track of the index of the last inserted element.

#define MAX 100
int stack[MAX]; 
int top = -1;  // Stack is empty initially

---

(b) Linked List-Based Stack

Each node contains data and a pointer to the next node. The top pointer always points to the last inserted node.

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

---

3️⃣ Primitive Stack Operations

(a) Push Operation (Insert an Element)

📌 Process:
1️⃣ Check if the stack is full (for array implementation).
2️⃣ Increment the top pointer.
3️⃣ Add the element at the new top position.

C Implementation (Array-Based Stack):

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = value;
}

🔹 Time Complexity: O(1)

---

(b) Pop Operation (Remove an Element)

📌 Process:
1️⃣ Check if the stack is empty.
2️⃣ Retrieve the top element.
3️⃣ Decrease the top pointer.

C Implementation (Array-Based Stack):

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

🔹 Time Complexity: O(1)

---

(c) Peek Operation (View Top Element Without Removing It)

📌 Process:
1️⃣ Check if the stack is empty.
2️⃣ Return the top element.

C Implementation:

int peek() {
    if (top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack[top];
}

🔹 Time Complexity: O(1)

---

(d) IsEmpty Operation (Check if Stack is Empty)

📌 Process:

• If top == -1, return true (empty).
• Otherwise, return false (not empty).

C Implementation:

int isEmpty() {
    return (top == -1);
}

🔹 Time Complexity: O(1)

---

4️⃣ Applications of Stacks

✅ Function Call Management → Used in recursion to store function calls.
✅ Expression Evaluation & Conversion → Used in infix to postfix conversion and postfix evaluation.
✅ Undo/Redo Operations → Text editors maintain history using stacks.
✅ Browser Back & Forward Navigation → Maintains page history using stacks.
✅ Balancing Parentheses → Checking if an expression has balanced parentheses.

---

5️⃣ Summary Table of Stack Operations

Operation	Description	Time Complexity
Push	Inserts an element at the top	O(1)
Pop	Removes the top element	O(1)
Peek	Returns the top element	O(1)
isEmpty	Checks if the stack is empty	O(1)

Polynomial Representation and Operations: Addition, Subtraction, and Multiplication

 Polynomial Representation and Operations: Addition, Subtraction, and Multiplication

Polynomials are fundamental in mathematics and computer science, representing expressions consisting of variables and coefficients. Efficient manipulation of polynomials is crucial in various applications like computer algebra systems, physics simulations, and cryptography. In this post, we will cover polynomial representation and basic operations (addition, subtraction, and multiplication) on single-variable and two-variable polynomials.

---

1. Representation of Polynomials

Polynomials can be represented using:

• Arrays
• Linked Lists

Each term in a polynomial has:

• A coefficient (numerical value).
• A degree (power) of the variable(s).

(a) Representation of a Single-Variable Polynomial

A single-variable polynomial has only one variable (e.g., x).

Example Polynomial:

$$P(x) = 5x^3 + 4x^2 + 3x + 2$$

Array Representation:
An array stores coefficients at indices representing powers of x.

Power of x	3	2	1	0
Coefficient	5	4	3	2

C Code Example (Array Representation):

int poly[] = {2, 3, 4, 5};  // Coefficients for 2 + 3x + 4x² + 5x³

Linked List Representation:
Each node stores a coefficient and an exponent, linked to the next term.

struct Node {
    int coeff;
    int power;
    struct Node* next;
};

---

(b) Representation of a Two-Variable Polynomial

A two-variable polynomial involves two variables (e.g., x and y).

Example Polynomial:

$$P(x, y) = 3x^2y + 4xy^2 + 5x + 2y + 1$$

Linked List Representation:
Each node stores the coefficient, exponents of x and y, and a pointer to the next term.

struct Node {
    int coeff;
    int power_x;
    int power_y;
    struct Node* next;
};

---

2. Operations on Polynomials

(a) Polynomial Addition

Polynomial addition involves adding coefficients of like terms (same exponents).

Example:

$$(3x^2 + 4x + 2) + (5x^2 + 2x + 3) = 8x^2 + 6x + 5$$

Algorithm (Using Linked List):

1. Traverse both polynomials simultaneously.
2. If exponents match, add coefficients.
3. If one exponent is larger, copy that term to the result.
4. Continue until both lists are traversed.

C Code Example:

struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    while (poly1 && poly2) {
        if (poly1->power > poly2->power) {
            insertTerm(&result, poly1->coeff, poly1->power);
            poly1 = poly1->next;
        } else if (poly1->power < poly2->power) {
            insertTerm(&result, poly2->coeff, poly2->power);
            poly2 = poly2->next;
        } else {
            insertTerm(&result, poly1->coeff + poly2->coeff, poly1->power);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    return result;
}

🔹 Time Complexity: O(n) (Iterating through both lists once)

---

(b) Polynomial Subtraction

Subtracting polynomials follows the same logic as addition, but we subtract coefficients of like terms.

Example:

$$(3x^2 + 4x + 2) - (5x^2 + 2x + 3) = -2x^2 + 2x -1$$

Algorithm:

• Change the sign of all terms in the second polynomial.
• Perform addition.

C Code Example:

void subtractPolynomials(struct Node* poly1, struct Node* poly2) {
    while (poly2) {
        poly2->coeff = -poly2->coeff;
        poly2 = poly2->next;
    }
    struct Node* result = addPolynomials(poly1, poly2);
}

🔹 Time Complexity: O(n)

---

(c) Polynomial Multiplication

Multiplication of polynomials involves multiplying each term in the first polynomial with every term in the second polynomial.

Example:

$$(3x + 2) \times (4x + 1) = 12x^2 + 3x + 8x + 2 = 12x^2 + 11x + 2$$

Algorithm:

1. Multiply each term in poly1 with every term in poly2.
2. Add terms with the same exponents.

C Code Example:

struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    struct Node* temp1 = poly1;
    
    while (temp1) {
        struct Node* temp2 = poly2;
        while (temp2) {
            int coeff = temp1->coeff * temp2->coeff;
            int power = temp1->power + temp2->power;
            insertTerm(&result, coeff, power);
            temp2 = temp2->next;
        }
        temp1 = temp1->next;
    }
    return result;
}

🔹 Time Complexity: O(n²) (Every term is multiplied with every other term)

---

3. Summary Table of Polynomial Operations

Operation	Process Description	Time Complexity
Addition	Combine like terms and add coefficients	O(n)
Subtraction	Convert second polynomial to negative and perform addition	O(n)
Multiplication	Multiply each term and combine like terms	O(n²)

---

4. Applications of Polynomial Operations

• Computer Algebra Systems (e.g., MATLAB, Mathematica).
• Machine Learning & Signal Processing (Fourier Transforms).
• Physics & Engineering Simulations.
• Cryptography (Polynomial-based hashing and encoding).