Swap nibbles of a given number

#define swapNibble(num)   (( num & 0xF ) << 4 )  |  ( ( num 7 0xF0 ) >> 4 )

( num & 0xF ) << 4 ) : This grabs first nibble of nummber  and left shifts the nibble  to 4 places

( num 7 0xF0 ) >> 4 ) : And this grabs the next nibble of the number and right shifts the nibble  to 4 places

Finally we use bitwise OR  swap is completed

Stack using arrays

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

struct Stack {
    int top;
    unsigned int capacity;
    int* array;

};

//function to create a stack  , initialising with capacity as zero

struct Stack* createStack(unsigned int cap)
{
    struct Stack* newStack = (struct Stack*) malloc(sizeof(struct Stack));

    newStack->top = -1;
    newStack->capacity = cap;
    newStack->array = (int*)malloc(sizeof(int)* newStack->capacity);
    return  newStack;
}


int isFullStack(struct Stack* stack)
{
    return stack->top == stack->capacity - 1;
}

int isEmptyStack(struct Stack* stack)
{
    return stack->top ==  - 1;
}

void push(struct Stack* stack , int item )
{
    if (isFullStack(stack) == 1)
    {
        printf("Stackoverflow");
        return;
    }

    stack->array[++stack->top] = item;
    printf("Pushed on stack %d \n ", item);

}

int pop(struct Stack* stack)
{
    if (isEmptyStack(stack) == 1)
    {
        printf("Stack Underflow");
        return INT_MIN;
    }

    printf("Popped %d\n", stack->array[stack->top]);
    return stack->array[stack->top--] ;

}

void peek(struct Stack* stack)
{
    if (isEmptyStack(stack))
    {
        printf("Empty stack \n");
        return;
    }
    printf("%d\n" , stack->array[stack->top]);
    ;
}

int main()
{
    struct Stack* stack = createStack(100);
    push(stack , 1 );
    push(stack, 2);
    push(stack, 3);

    pop(stack);
    peek(stack);

    pop(stack);
    pop(stack);
    peek(stack);
    push(stack, 1);
    peek(stack);

    getchar();
    return 0;

       




}

Stack with Linked List

//STACK WITH linked list

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

struct StackNode {
    int data;
    struct StackNode* next;
};

struct StackNode* newNode(int data)
{
    struct StackNode* node = (struct StackNode*) malloc(sizeof(struct StackNode));
    node->data = data;
    return node;

}

int isEmpty(struct StackNode* root)
{
    return !root;
}

void push(struct StackNode** root, int item)
{
    struct StackNode* node = newNode(item);
    node->next = *root;

    *root = node;
    printf("pushed %d \n", item);

}

void pop(struct StackNode** root)
{
    if (isEmpty(*root))
    {
        printf("Underflow \n");
        return;
    }
    int poped = (*root)->data;
    struct StackNode* temp = *root;
    *root = (*root)->next;
    free(temp);

    printf("popped %d\n", poped);

}

void peek(struct StackNode* root)
{
    if (isEmpty(root))
    {
        printf("empty stack \n");
        return;
    }
    printf("peeked %d \n" , root->data);

}


int main()
{
    struct StackNode* stackRoot = NULL;
    push(&stackRoot, 4);
    push(&stackRoot, 6);

    pop(&stackRoot);

    peek(stackRoot);

    pop(&stackRoot);
    peek(stackRoot);
    push(&stackRoot, 6);
    peek(stackRoot);

    getchar();
    return 0;


}

Tid Bits - Stack :

Stack can be FILO - First in last out or LIFO - First in last out .
Underflow condition - When a pop operation  is performed on an empty stack
Peek Operation   : get the topmost item
Stack can be implemented using an array or a Linked List
Basic ADT : Using arrays :
            struct Stack {
                int top  ;
                unsigned int capacity ;
                int* array ;
              }
             
              Disadvantages using array :
             
              No dynamic size
              Doesnt grow or shrink using depending on needs at runtime
             
              Using Linked List :
              struct StackNode {
                int data ;
                struct StackNode* next ;
              }
             
 Balancing of symbols:
Infix to Postfix/Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals.
Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver.



We need postfix notations because compiler scans the expressions from left to right or from right to left
Consider the below expression: a op1 b op2 c op3 d
If op1 = +, op2 = *, op3 = +

The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.


The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are not required in postfix.

Efficiency of Short Hand Notation

Why x += 1 ; is more efficient than x = x+1 ?

It is related to how assembler references the memory location accesss .
The ALU uses registers for referencing values and accumulator for storing partial results .
 So , for case 1 : 
  x =  x + 1 ;
 
  MOV A , (x) ;  // Move the value at memory location x in accumultor A  . The value of x is stored in register
  ADD A , 1  ; // ADD 1 IN ACCUMULATor
  MOV (X) ,  A ; // Move the value in accumulator at memory location referenced by x
 
  for case 2 :
  x += 1
  ADD (x) , 1 ; // Add 1 at memory location referenced by x
 
  So , so coz of efficient dereferncing and no partial result generation  , short hand artihmatic noations are efficient even though at an abstract view all operations produce same results

Java tid bits :

1 : A class that implpementing an interface becomes an abstract class if it dont implements all the functions declared inside Interface and hence cant be used for instantiating objects

2 : Interfaces having only variables can be used for making set of Global Constants which can be used by other classes , just like constants declared in C header files


3 : Packages help in resuing classes across programmes
4 : Only at runtime, interpreter loads the class used from other package , during compilation , compiler only  checks whther the .class file is present in package imported

5: A java source file can only have one class declared as public because filename should be same as the public class with .java extension . But many non public classes can be defined

6:
Exception class is a subclass of Throwable , hence so do all user defined exceptions

7 : in switch case statements only constant values or literals are allowed
 final String a = "" , b = "fa";
     switch("dgh")
     {
     case "sdg":
         break;
     case a+b :
         break;
     }
    
8:  Runtime : polymorphism (overriding) and Compiletime - Inheritance of methods and attributes by subclasses

9 :  Java's interpreter do thread switching for multi threading
10 : States of a Thread :
New Born State : When an object of a class extending java.lang.Thread is made
Runnable state : on calling start()
Running state : Java runtime schedules thread calling run()

Next Greater Element

/// PRINT NEXT GREATER ELEMENT IN THE STACK FOR AN ARRAY O(N)
void printNextGreater( int arr[] ,int n )
{
    // the array item under consideration
    int next  ;
    int element ; //the current popped element
    struct stack s;
   
    //push the first element to the stack
    s.push(&s , arr[0]) ;
   
    for(int  i = 1 ; i < n ; ++i)
    {
        next = i ;
   
            while( isEmpty(s) == false )
            {
                //pop the element from the stack
                element = s.pop();
               
                //print the pairs until popped element are smaller than next
                // these are the next greater element pairs for each element in stack pushed earlier
                while ( element < next)
                {
                    printf("%d -> %d \n" , element , next );
                    if(isEmpty(s)) break;
                    element = pop(&s);
                }
               
                //if the popped element is greater than next , push it back to stack
                if(element > next )
                    push(&s , element);
               
            }
           
            //push the next to find its next greater element
            push (&s , next);
   
    }
   
    //for all remaining element in the stack , print -1 as these elements dont have next greater element
    while(isEmpty(s) == false)
    {
        printf("%d -> -1" , pop(&s));
    }
   
}

Find even or odd parity of a given unsigned number

// parity here means total number of set bits in  a number

typedef int bool ;


int parity ( unsigned int num )
{
    bool parity  = 0 ; // 0 means even parity and 1 meand odd parity
   
    while ( num )
    {
        parity  = !parity ;
        num &= n-1 ;
     }
   
    return parity;
}

i haave seen a million faces
but still my heart embraces

Evaluate Postfix

Algorithm to follow :
    Scan the characters in the expression , and
    for each character
        If the character is an operand , push it to stack
        If the character is an operator , pop the operands , evaluate result and push result back to stack
    After the loops ends scanning and evaluating , pop the value from stack and return it as the final value of the postfix expression
   

int evaluatePostfix(char* exp)
{
    //create a stack equal to expression size
    struct Stack* stack = createStack(strlen(exp));
   
    //check if stack was created successfully
    if (!stack) return -1;

    //scan all characaters in the expression one by one
    for (int i = 0; exp[i]; ++i)
    {
        //if the scanned character is a number ,push it on the stack
        if (isdigit(exp[i]) ) push(stack , ( exp[i] - '0' ) );

        //else pop the operands from stack and push back the result after evaluation
        else
        {
            int value1 = pop(stack);
            int value2 = pop(stack);
            switch (exp[i])
            {
            case '+':
                push(stack , value2 + value1 ); // value2 is the first operand because it was pushed before value1
                break;
            case '-':
                push(stack, value2 - value1); // value2 is the first operand because it was pushed before value1
                break;
            case '/':
                push(stack, value2 / value1); // value2 is the first operand because it was pushed before value1
                break;
            case '*':
                push(stack, value2 * value1); // value2 is the first operand because it was pushed before value1
                break;
            }
        }

    }

    //the last value in the stack is ours final result
    return pop(stack);


}

Post Fix to Infix

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

// Stack type
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};

// Stack Operations
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

    if (!stack)
        return NULL;

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

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

    if (!stack->array)
        return NULL;
    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}


int isOperand(char ch)
{
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

int prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-' :
        return 1;
    case '*':
    case '/':
        return 2;

    case '^':
        return 3;
    }
    return -1;
}

int infixToPostfix(char* exp)
{

    int k , i ;
    struct Stack* stack = createStack(strlen(exp));
    if (!stack)
        return -1;
    for ( i = 0, k = -1; exp[i]; ++i)
    {
        //if scanned character is an operand , add to the output
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
        // If the scanned character is an ‘(‘, push it to the stack.
        else if (exp[i] == '(')
            push(stack, exp[i]);
        //  If the scanned character is an ‘)’, pop and output from the stack
        // until an ‘(‘ is encountered.
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return -1; //invalid expression
            else
                pop(stack); // pop starting braces (
        }

        else //an operator is encountered
        {
            while (!isEmpty(stack) && prec(exp[i]) <= prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }

    }
    // pop all the operators from the stack
    while (!isEmpty(stack))
        exp[++k] = pop(stack);

    exp[++k] = '\0';
    printf("%s\n", exp);
}
// Driver program to test above functions
int main()
{
    char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
    infixToPostfix(exp);
    getchar();
    return 0;
}

Check For Balanced Expression in an expression

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”  

// a function to check if two given characters are a matching pair
bool isMatchingPair( char chr1 , char chr2   )
{
    if( chr1 == '(' && chr2 == ')')
        return 1 ;
    else if( chr1 == '{' && chr2 == '}')
        return 1 ;
    else if( chr1 == '[' && chr2 == ']')
        return 1 ;
     else
        return 0 ;
       
       
}

bool arePraenthesisBalanced (char exp[])
{
    int i = 0 ;
   
    // an empty character stack  to be made up of linked list
    struct sNode* stack = NULL;
   
    //while we dont approach the null character of the string
        while( exp[i])
        {
            // if exp[i] is a starting charcter push it
            if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
                push(&stack, exp[i]);
          
           //if the exp[i] is an ending parenthesis , pop from stack and check whether it matches as the type of starting parenthesis exp[i]
            if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
            {
                //if the stack is NULL , return false  as  this is an extra invalid parentheis
                if(stack == NULL)
                {
                    return 0 ;
                }
                 // pop the character and check if it is  not of the type of exp[i] , return false
                 else if(!(isMatchingPair(pop(&stack) , exp[i])))
                    return 0 ;
               
            }
            ++i;
          
        }
       
        //if there is something left in stack , means we found an unmatched single parenthesis type
        // return false
        if(stack  == NULL )
            return true ; //balanced
          else
            return false; //unbalanced
         
}