Saturday, 22 February 2025
Time complexity in DSA with C
Infix ,prefix and postfix notation in DSA with C
1. Infix Notation
Definition:
In infix notation, the operator is placed between the operands. This is the most commonly used
notation in arithmetic expressions.
Example:
• A + B
• A * (B + C)
Order of Operations:
• Operators are evaluated according to their precedence (e.g., multiplication before addition).
• Parentheses () are used to change the order of evaluation.
Basic Example:
In the expression A + B * C:
• According to the operator precedence, multiplication is done before addition, so it's
equivalent to A + (B * C).
Conversion of Infix to Postfix/Prefix:
Infix expressions must be converted to either postfix or prefix notation for easier computation by
computers.
2. Prefix Notation (Polish Notation)
Definition:
In prefix notation, the operator is placed before the operands.
Example:
• + A B (Equivalent to A + B in infix)
• * + A B C (Equivalent to (A + B) * C in infix)
Order of Operations:
• The operator appears before its operands.
• This means the operator is evaluated first, followed by its operands.
Conversion of Infix to Prefix:
The rules for converting infix to prefix are:
• Reverse the expression (reverse the order of operands and operators).
• Convert the reversed expression to postfix.
• Reverse the postfix expression to obtain the prefix.
Example Program:
Here’s an example in Python to convert an infix expression to prefix:
def precedence(c):
if c == '+' or c == '-':
return 1
elif c == '*' or c == '/':
return 2
elif c == '^':
return 3
return 0
def infix_to_prefix(expression):
expression = expression[::-1]
stack = []
output = []
for char in expression:
if char.isalnum():
output.append(char)
elif char == ')':
stack.append(char)
elif char == '(':
while stack and stack[-1] != ')':
output.append(stack.pop())
stack.pop()
else:
while (stack and precedence(char) < precedence(stack[-1])):
output.append(stack.pop())
stack.append(char)
while stack:
output.append(stack.pop())
return ''.join(output[::-1])
# Test the function
expression = "(A-B/C)*(A/K-L)"
print("Prefix expression: ", infix_to_prefix(expression))
3. Postfix Notation (Reverse Polish Notation)
Definition:
In postfix notation, the operator is placed after the operands.
Example:
• A B + (Equivalent to A + B in infix)
• A B C + * (Equivalent to A * (B + C) in infix)
Order of Operations:
• Operands are followed by operators.
• Each operator operates on the operands that appear immediately before it.
Conversion of Infix to Postfix:
The rules for converting infix to postfix are:
• If the current token is an operand, add it to the postfix expression.
• If the current token is an operator, pop operators from the stack to the output until you find
an operator with lower precedence or a left parenthesis. Then push the operator onto the
stack.
• If the current token is a left parenthesis (, push it onto the stack.
• If the current token is a right parenthesis ), pop operators from the stack until you encounter
a left parenthesis, which is discarded.
Example Program:
Here’s an example in Python to convert an infix expression to postfix:
def precedence(c):
if c == '+' or c == '-':
return 1
elif c == '*' or c == '/':
return 2
elif c == '^':
return 3
return 0
def infix_to_postfix(expression):
stack = []
output = []
for char in expression:
if char.isalnum():
output.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop()
else:
while stack and precedence(char) <= precedence(stack[-1]):
output.append(stack.pop())
stack.append(char)
while stack:
output.append(stack.pop())
return ''.join(output)
# Test the function
expression = "(A-B/C)*(A/K-L)"
print("Postfix expression: ", infix_to_postfix(expression))
Comparison of Infix, Prefix, and Postfix
Notation Example Order of Operations Parentheses
Needed? Advantages
Infix A + B *
C
Operators are evaluated
based on precedence Yes (for clarity) Most commonly used and
understood
Prefix + A * B
C
Operators appear first,
followed by operands No
No parentheses needed, easier
for compilers
Postfix A B C *
+
Operators appear after
operands No
No parentheses, easier for
machine evaluation
Applications:
1. Prefix and Postfix are easier for computers to evaluate:
o Computers don't need to worry about operator precedence or parentheses in these
notations.
o Commonly used in stack-based algorithms (evaluating expressions).
2. Postfix notation is used in various calculators:
o Reverse Polish Notation (RPN) is used in many calculators and some programming
languages for arithmetic expression evaluation.
3. Prefix notation is useful in certain compilers:
o Prefix expressions simplify parsing in compilers, where the operators precede
operands.
Friday, 21 February 2025
File Handling in C language with examples
File Handling in C:
File handling allows a C program to read from and write to files. This is an essential concept for
working with data persistence in C programming. Files can be of two main types:
1. Text Files – Contains readable data (ASCII characters).
2. Binary Files – Contains data in binary format (non-readable).
Basic File Operations:
In C, files can be manipulated using a set of functions provided in the stdio.h library. The most
commonly used file functions are:
1. fopen() – Opens a file.
2. fclose() – Closes a file.
3. fprintf() / fputs() – Write to a file.
4. fscanf() / fgets() – Read from a file.
5. fseek() – Move the file pointer.
6. ftell() – Get the current position of the file pointer.
7. feof() – Check for end of file.
File Opening Modes:
The fopen() function is used to open a file. It takes two arguments: the name of the file and the
mode in which the file should be opened. The modes are:
• "r" – Open a file for reading. If the file doesn't exist, the program will fail.
• "w" – Open a file for writing. If the file exists, it is overwritten.
• "a" – Open a file for appending. New data is written at the end of the file.
• "r+" – Open a file for both reading and writing.
• "w+" – Open a file for both reading and writing. It creates a new file or overwrites the
existing file.
• "a+" – Open a file for both reading and appending.
Example Programs for File Handling:
1. Program to Write Data to a File
This program demonstrates how to open a file in "write" mode and write data into it.
#include <stdio.h>
int main() {
FILE *file;
char data[] = "This is a test file containing some text data.";
// Open file for writing
file = fopen("testfile.txt", "w");
if (file == NULL) {
printf("Unable to open the file.\n");
return 1;
}
// Write data to the file
fprintf(file, "%s", data);
// Close the file
fclose(file);
printf("Data has been written to testfile.txt\n");
return 0;
}
Explanation:
• fopen("testfile.txt", "w"): Opens the file testfile.txt in "write" mode. If the file does not exist,
it is created. If the file already exists, its content is overwritten.
• fprintf(): Writes the string data to the file.
• fclose(file): Closes the file to save the data.
2. Program to Read Data from a File
This program demonstrates how to open a file in "read" mode and read data from it.
#include <stdio.h>
int main() {
FILE *file;
char ch;
// Open file for reading
file = fopen("testfile.txt", "r");
if (file == NULL) {
printf("Unable to open the file.\n");
return 1;
}
// Read and print content of the file
while ((ch = fgetc(file)) != EOF) {
printf("%c", ch);
}
// Close the file
fclose(file);
return 0;
}
Explanation:
• fopen("testfile.txt", "r"): Opens the file testfile.txt for reading. If the file does not exist, the
program terminates.
• fgetc(file): Reads a character from the file. It continues reading characters until it encounters
EOF (End Of File).
• fclose(file): Closes the file after reading.
3. Program to Append Data to a File
This program demonstrates how to append data to an existing file.
#include <stdio.h>
int main() {
FILE *file;
char data[] = "\nAppending some new data to the file.";
// Open file for appending
file = fopen("testfile.txt", "a");
if (file == NULL) {
printf("Unable to open the file.\n");
return 1;
}
// Append data to the file
fprintf(file, "%s", data);
// Close the file
fclose(file);
printf("Data has been appended to testfile.txt\n");
return 0;
}
Explanation:
• fopen("testfile.txt", "a"): Opens the file testfile.txt in "append" mode. If the file does not
exist, it is created.
• fprintf(): Appends the data to the file at the end.
• fclose(file): Closes the file after writing.
4. Program to Read Data Using fscanf
This program reads data from a file using the fscanf() function, which works like scanf() but reads
from a file.
#include <stdio.h>
int main() {
FILE *file;
char name[50];
int age;
// Open file for reading
file = fopen("testfile.txt", "r");
if (file == NULL) {
printf("Unable to open the file.\n");
return 1;
}
// Read data from the file
fscanf(file, "%s %d", name, &age);
// Print the data
printf("Name: %s\n", name);
printf("Age: %d\n", age);
// Close the file
fclose(file);
return 0;
}
Explanation:
• fscanf(file, "%s %d", name, &age): Reads a string (%s) and an integer (%d) from the file.
• fclose(file): Closes the file after reading.
5. Program to Copy One File to Another
This program copies the contents of one file to another.
#include <stdio.h>
int main() {
FILE *source, *destination;
char ch;
// Open source file for reading
source = fopen("source.txt", "r");
if (source == NULL) {
printf("Unable to open source file.\n");
return 1;
}
// Open destination file for writing
destination = fopen("destination.txt", "w");
if (destination == NULL) {
printf("Unable to open destination file.\n");
fclose(source);
return 1;
}
// Copy contents from source to destination
while ((ch = fgetc(source)) != EOF) {
fputc(ch, destination);
}
printf("File has been copied successfully.\n");
// Close both files
fclose(source);
fclose(destination);
return 0;
}
• fopen("source.txt", "r"): Opens the source file for reading.
• fopen("destination.txt", "w"): Opens the destination file for writing.
• fgetc(source): Reads one character at a time from the source file.
• fputc(ch, destination): Writes the character to the destination file.
• fclose(source) and fclose(destination): Close both files after copying.
1. Program to Write Data to a File
This simple program demonstrates how to write data to a file using fprintf().
#include <stdio.h>
int main() {
FILE *file;
file = fopen("testfile.txt", "w"); // Open file for writing
if (file == NULL) {
printf("Unable to open file\n");
return 1;
}
fprintf(file, "Hello, this is a test file.\n");
fprintf(file, "This is written using C file handling.\n");
fclose(file); // Close the file
printf("Data written to file successfully\n");
return 0;
}
Explanation:
• fopen("testfile.txt", "w"): Opens the file in write mode. If the file doesn't exist, it is created.
If it exists, it is overwritten.
• fprintf(file, "text"): Writes the given string to the file.
• fclose(file): Closes the file after writing.
2. Program to Read Data from a File
This program demonstrates how to read data from a file using fgetc().
#include <stdio.h>
int main() {
FILE *file;
char ch;
file = fopen("testfile.txt", "r"); // Open file for reading
if (file == NULL) {
printf("Unable to open file\n");
return 1;
}
// Read and print characters from the file until EOF
while ((ch = fgetc(file)) != EOF) {
printf("%c", ch); // Print each character
}
fclose(file); // Close the file
return 0;
}
Explanation:
• fopen("testfile.txt", "r"): Opens the file in read mode.
• fgetc(file): Reads one character at a time from the file. The loop continues until EOF (End Of
File) is encountered.
• fclose(file): Closes the file after reading.
3. Program to Append Data to a File
This program demonstrates how to append data to an existing file using fprintf().
#include <stdio.h>
int main() {
FILE *file;
// Open file in append mode
file = fopen("testfile.txt", "a");
if (file == NULL) {
printf("Unable to open file\n");
return 1;
}
// Append new data to the file
fprintf(file, "\nThis line is added to the file using append mode.");
fclose(file); // Close the file
printf("Data has been appended to the file\n");
return 0;
}
Explanation:
• fopen("testfile.txt", "a"): Opens the file in append mode. If the file doesn't exist, it is
created.
• fprintf(file, "text"): Appends the given string to the end of the file.
4. Program to Copy One File to Another
This program demonstrates how to copy the contents of one file to another.
#include <stdio.h>
int main() {
FILE *source, *destination;
char ch;
// Open the source file for reading
source = fopen("source.txt", "r");
if (source == NULL) {
printf("Unable to open source file\n");
return 1;
}
// Open the destination file for writing
destination = fopen("destination.txt", "w");
if (destination == NULL) {
printf("Unable to open destination file\n");
fclose(source);
return 1;
}
// Copy content from source to destination
while ((ch = fgetc(source)) != EOF) {
fputc(ch, destination);
}
printf("File has been copied successfully\n");
fclose(source);
fclose(destination);
return 0;
}
C Language Notes: Pointers with examples
1. Introduction to Pointers:
A pointer in C is a variable that stores the memory address of another variable. Instead of holding a
data value itself, it holds the location of a variable in memory. This allows for indirect access and
manipulation of variables.
Syntax for Declaring Pointers:
type *pointer_name;
• type: The data type of the variable the pointer will point to (e.g., int, float, char).
• pointer_name: The name of the pointer.
2. Declaring and Initializing Pointers:
• Declaring a pointer:
• int *ptr; // Pointer to an integer
• Initializing a pointer:
• int x = 10;
• int *ptr = &x; // ptr stores the address of x
• Address-of operator (&): Used to get the address of a variable.
3. Dereferencing Pointers:
Dereferencing a pointer means accessing the value stored at the address the pointer is pointing to.
• Dereference operator (*): Used to access the value stored at the pointer's address.
• int x = 10;
• int *ptr = &x;
• printf("%d", *ptr); // Output: 10
4. Pointer Arithmetic:
Pointers can be incremented or decremented, which will move them to the next or previous memory
location of the same type. The amount the pointer moves depends on the size of the data type it is
pointing to.
• Incrementing a pointer:
• ptr++; // Moves the pointer to the next memory location of the same data type
• Decrementing a pointer:
• ptr--; // Moves the pointer to the previous memory location
5. Pointers and Arrays:
In C, the name of an array is a pointer to the first element of the array. Hence, arrays and pointers are
closely related.
int arr[] = {1, 2, 3};
int *ptr = arr; // ptr points to the first element of the array
printf("%d", *ptr); // Output: 1 (value at arr[0])
6. Pointers to Pointers:
A pointer to a pointer is a pointer that stores the address of another pointer.
int x = 10;
int *ptr1 = &x;
int **ptr2 = &ptr1;
printf("%d", **ptr2); // Output: 10
7. Functions and Pointers:
Pointers can be passed to functions, allowing functions to modify the actual values of variables.
#include <stdio.h>
void updateValue(int *ptr) {
*ptr = 20; // Modifies the value of the original variable
}
int main() {
int num = 10;
updateValue(&num);
printf("%d", num); // Output: 20
return 0;
}
Common Pointer Operations in C:
• Address-of operator (&): To get the address of a variable.
• Dereference operator (*): To get the value stored at a memory address.
• Pointer arithmetic: To increment or decrement pointers.
Programs with Solutions:
1. Program to Demonstrate Pointer Basics
#include <stdio.h>
int main() {
int num = 5;
int *ptr = #
printf("Value of num: %d\n", num);
printf("Address of num: %p\n", &num);
printf("Value at ptr (Dereferenced): %d\n", *ptr);
printf("Address stored in ptr: %p\n", ptr);
return 0;
}
Explanation:
• &num gives the address of num.
• *ptr dereferences the pointer and gives the value stored at the address ptr points to.
2. Program to Demonstrate Pointer Arithmetic
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int *ptr = arr;
printf("First element: %d\n", *ptr);
ptr++;
printf("Second element: %d\n", *ptr);
ptr++;
printf("Third element: %d\n", *ptr);
return 0;
}
Explanation:
• We use pointer arithmetic (ptr++) to access the next element in the array.
• ptr++ moves the pointer to the next integer (size of int).
3. Program to Swap Two Numbers Using Pointers
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int main() {
int x = 5, y = 10;
printf("Before swap: x = %d, y = %d\n", x, y);
swap(&x, &y);
printf("After swap: x = %d, y = %d\n", x, y);
return 0;
}
Explanation:
• The swap function uses pointers to modify the actual values of x and y.
4. Program to Demonstrate Pointer to Pointer
#include <stdio.h>
int main() {
int x = 5;
int *ptr1 = &x;
int **ptr2 = &ptr1;
printf("Value of x: %d\n", x);
printf("Value using ptr1: %d\n", *ptr1);
printf("Value using ptr2: %d\n", **ptr2);
return 0;
}
• ptr2 is a pointer to the pointer ptr1. We can access the value of x by dereferencing ptr2
twice.
5. Program to Demonstrate Function with Pointer
#include <stdio.h>
void square(int *num) {
*num = (*num) * (*num);
}
int main() {
int n = 4;
square(&n);
printf("Squared value: %d\n", n); // Output: 16
return 0;
}
Explanation:
• The function square takes a pointer as an argument and modifies the original value of n
through dereferencing.
6. Program to Find Length of String Using Pointer
#include <stdio.h>
int stringLength(char *str) {
int length = 0;
while (*str != '\0') {
length++;
str++;
}
return length;
}
int main() {
char str[] = "Hello, world!";
int length = stringLength(str);
printf("Length of the string: %d\n", length); // Output: 13
return 0;
}
• The function stringLength uses a pointer to traverse through the string and count the
number of characters until the null character \0 is encountered.
Sure! Here are some additional C programming exercises focusing on pointers, arrays, and memory
management for you to practice.
1. Program to Reverse an Array Using Pointers
#include <stdio.h>
void reverseArray(int *arr, int size) {
int *start = arr;
int *end = arr + size - 1;
int temp;
while (start < end) {
temp = *start;
*start = *end;
*end = temp;
start++;
end--;
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
reverseArray(arr, size);
printf("\nReversed Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Explanation:
• The function reverseArray uses pointers start and end to reverse the elements of the array.
2. Program to Find Maximum and Minimum Using Pointers
#include <stdio.h>
void findMaxMin(int *arr, int size, int *max, int *min) {
*max = *min = *arr;
for (int i = 1; i < size; i++) {
if (*(arr + i) > *max) {
*max = *(arr + i);
}
if (*(arr + i) < *min) {
*min = *(arr + i);
}
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMin(arr, size, &max, &min);
printf("Max: %d\n", max);
printf("Min: %d\n", min);
return 0;
}
Explanation:
• The function findMaxMin takes pointers to max and min values and updates them with the
maximum and minimum values of the array.
3. Program to Copy One String to Another Using Pointers
#include <stdio.h>
void copyString(char *src, char *dest) {
while (*src != '\0') {
*dest = *src;
src++;
dest++;
}
*dest = '\0'; // Null-terminate the destination string
}
int main() {
char src[] = "Hello, World!";
char dest[50];
copyString(src, dest);
printf("Source String: %s\n", src);
printf("Destination String: %s\n", dest);
return 0;
}
Explanation:
• The function copyString copies characters from src to dest using pointer arithmetic.
4. Program to Concatenate Two Strings Using Pointers
#include <stdio.h>
void concatenateStrings(char *str1, char *str2, char *result) {
while (*str1 != '\0') {
*result = *str1;
str1++;
result++;
}
while (*str2 != '\0') {
*result = *str2;
str2++;
result++;
}
*result = '\0'; // Null-terminate the result string
}
int main() {
char str1[] = "Hello, ";
char str2[] = "World!";
char result[50];
concatenateStrings(str1, str2, result);
printf("Concatenated String: %s\n", result);
return 0;
}
Explanation:
• The function concatenateStrings concatenates two strings str1 and str2 into result using
pointers.
5. Program to Count Occurrences of a Character in a String Using Pointers
#include <stdio.h>
int countOccurrences(char *str, char ch) {
int count = 0;
while (*str != '\0') {
if (*str == ch) {
count++;
}
str++;
}
return count;
}
int main() {
char str[] = "Programming in C is fun!";
char ch = 'g';
int count = countOccurrences(str, ch);
printf("Character '%c' occurs %d times in the string.\n", ch, count);
return 0;
}
Explanation:
• The function countOccurrences traverses the string and counts the occurrences of the
character ch.
6. Program to Swap Two Numbers Using Pointers Without a Temporary Variable
#include <stdio.h>
void swap(int *a, int *b) {
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
int main() {
int x = 10, y = 20;
printf("Before swap: x = %d, y = %d\n", x, y);
swap(&x, &y);
printf("After swap: x = %d, y = %d\n", x, y);
return 0;
}
Explanation:
• The function swap swaps the values of x and y without using a temporary variable, by using
mathematical operations with pointers.
7. Program to Reverse a String Using Pointers
#include <stdio.h>
void reverseString(char *str) {
char *start = str;
char *end = str;
char temp;
// Move the 'end' pointer to the last character
while (*end != '\0') {
end++;
}
end--; // Move back to the last valid character
// Swap characters between start and end pointers
while (start < end) {
temp = *start;
*start = *end;
*end = temp;
start++;
end--;
}
}
int main() {
char str[] = "Hello";
printf("Original String: %s\n", str);
reverseString(str);
printf("Reversed String: %s\n", str);
return 0;
}
Explanation:
• The function reverseString uses two pointers to reverse the characters in the string in place.
8. Program to Allocate Memory Dynamically for an Array of Integers Using Pointers
#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr;
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
// Dynamically allocate memory for n integers
arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", arr + i); // Using pointer arithmetic
}
printf("Array elements are:\n");
for (int i = 0; i < n; i++) {
printf("%d ", *(arr + i)); // Using pointer arithmetic
}
// Free dynamically allocated memory
free(arr);
return 0;
}
Explanation:
• The program dynamically allocates memory for an array of integers using malloc. It then
allows the user to input values, displays them, and frees the memory once done.
9. Program to Find Factorial of a Number Using Recursion and Pointers
#include <stdio.h>
int factorial(int *n) {
if (*n <= 1) {
return 1;
} else {
(*n)--;
return *n * factorial(n);
}
}
int main() {
int num = 5;
printf("Factorial of %d is %d\n", num, factorial(&num));
return 0;
}
Explanation:
• The factorial function calculates the factorial of a number recursively, using a pointer to
modify the value of n.
10. Program to Compare Two Strings Using Pointers
#include <stdio.h>
int compareStrings(char *str1, char *str2) {
while (*str1 != '\0' && *str2 != '\0') {
if (*str1 != *str2) {
return 0; // Strings are not equal
}
str1++;
str2++;
}
return (*str1 == *str2); // Both strings are equal if both pointers end at '\0'
}
int main() {
char str1[] = "hello";
char str2[] = "hello";
if (compareStrings(str1, str2)) {
printf("The strings are equal.\n");
} else {
printf("The strings are not equal.\n");
}
return 0;
}
Explanation:
• The function compareStrings compares two strings character by character and returns 1 if
they are equal, and 0 if they are not.