Two dimension (2D) array: 

A two-dimensional array is nothing but a matrix, that has rows and columns in it. For e.g.

    int a[3][4];

    float b[10][10];

Multidimensional array :

Any array which has a dimension higher than One is a multidimensional array. 2D array is also a multidimensional array.

E.g. of 3D array

    int a[3][2][4];

Here, the first subscript specifies a plane number, the second subscript a row number and the third a column number.

DIFFERENCE :

 Every 2D array is a multidimensional array but the other way round is not necessary(for example a 3D array is also a multidimensional array but its surely not 2D).

Let A be an array of type T and has n elements then it satisfied the following operations:

• CREATE(A): Create an array A
• INSERT(A,X): Insert an element X into an array A in any location
• DELETE(A,X): Delete an element X from an array A
• MODIFY(A,X,Y): modify element X by Y of an array A
• TRAVELS(A): Access all elements of an array A
• MERGE(A,B): Merging elements of A and B into a third array C

Thus by using a one-dimensional array we can perform above operations thus an array acts as an ADT.

The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n. The complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones.

The process of finding complexity of given algorithm by counting number of steps and number of memory references used by using RAM model is called detailed analysis. For detailed time complexity algorithm we count the number of steps and finally add all steps and calculate their big oh notation. Similarly for detailed analysis of space complexity we count the number of memory references and finally add all steps and find their big oh notation.

E.g.

#include<stdio.h>

int main()

{

    int i, n, fact=1;

    printf("Enter a number to calculate factorial:");

    scanf("%d",&n);

    for(i=1; i<=n; i++)

            fact = fact*i;

    printf("Factorial of %d=%d", n, fact);

    return 0;

}

Time Complexity:

The declaration statement takes 1 step.

Printf statement takes 1 step.

Scanf statement takes 1 step.

In for loop:

    i=1 takes 1 step

    i<=n takes (n+1) step

    i++ takes n step

    within for loop fact=fact*i takes n step

printf statement takes 1 step

return statement takes 1 step

Total time complexity = 1+1+1+1+n+1+n+n+1+1

           = 3n+7

           = O(n)

Space complexity:

total memory references used = 3 = O(1)

Array in C is used to store elements of same types whereas Pointers are address variables which stores the address of a another variable. Now array variable is also having a address which can be pointed by a pointer and array can be navigated using pointer. Benefit of using pointer for array is two folds, first, we store the address of dynamically allocated array to the pointer and second, to pass the array to a function. Following are the differences in using array and using pointer to array.

• sizeof() operator prints the size of array in case of array and in case of pointer, it prints the size of int.
• assignment array variable cannot be assigned address of another variable but pointer can take it.
• first value first indexed value is same as value of pointer. For example, array[0] == *p.
• iteration array elements can be navigated using indexes using [], pointer can give access to array elements by using pointer arithmetic. For example, array[2] == *(p+2)

Example:

#include <stdio.h>
void printElement(char* q, int index){
   printf("Element at index(%d) is: %c\\n", index, *(q+index));
}
int main() {
   char arr[] = {'A', 'B', 'C'};
   char* p = arr;
   printf("Size of arr[]: %d\\n", sizeof(arr));
   printf("Size of p: %d\\n", sizeof(p));
   printf("First element using arr is: %c\\n", arr[0]);
   printf("First element using p is: %c\\n", *p);
   printf("Second element using arr is: %c\\n", arr[1]);
   printf("Second element using p is: %c\\n", *(p+1));
   printElement(p, 2);
   return 0;
}

Output:

Size of arr[]: 3
Size of p: 8
First element using arr is: A
First element using p is: A
Second element using arr is: B
Second element using p is: B
Element at index(2) is: C

Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture

The analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them.

Big  Oh notation

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture

Features of algorithm:

1. Input - Every algorithm must take zero or more number of input values from external.
2. Output - Every algorithm must produce an output as result.
3. Definiteness - Every statement/instruction in an algorithm must be clear and unambiguous (only one interpretation)
4. Finiteness - For all different cases, the algorithm must produce result within a finite number of steps.
5. Effectiveness - Every instruction must be basic enough to be carried out and it also must be feasible.
6. Correctness: Correct set of output values must be produced from the each set of inputs.

Big-O notation is a metrics used to find algorithm complexity. Basically, Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

__________________________________________

Analysis of Selection Sort

Time Complexity:

The selection sort makes first pass in n-1 comparison, the second pass in n-2 comparisons and so on.

Time complexity = (n-1) + (n-2) + (n-3) + …………………………. +2 +1

= O(n2)

Space Complexity:

Since no extra space besides 5 variables is needed for sorting

Space complexity = O(n)

Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

Quick-Sort vs Merge-Sort

Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets.
whereas
Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets.

Merge sort has the following performance characteristics:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)

Quicksort has the following performance characteristics:

• Best case: O(n)
• Average case: O(n log n)
• Worst case: O(n2)

The process of allocating memory at runtime is known as dynamic memory allocation. Library routines known as memory management functions are used for allocating and freeing memory during execution of a program. These functions are defined in stdlib.h header file.

A 2D array can be dynamically allocated in C using a single pointer. This means that a memory block of size row*column*dataTypeSize is allocated using malloc and pointer arithmetic can be used to access the matrix elements.

A program that demonstrates this is given as follows:

#include <stdio.h>
#include <stdlib.h> 
int main() {
   int row = 2, col = 3;
   int *arr = (int *)malloc(row * col * sizeof(int)); 
   int i, j;
   for (i = 0; i < row; i++)
      for (j = 0; j < col; j++)
         *(arr + i*col + j) = i + j;    
   printf("The matrix elements are:\\n");
   for (i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%d ", *(arr + i*col + j)); 
      }
      printf("\\n");
   }
   free(arr); 
   return 0;
}

The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n. The complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones.

The process of finding complexity of given algorithm by counting number of steps and number of memory references used by using RAM model is called detailed analysis. For detailed time complexity algorithm we count the number of steps and finally add all steps and calculate their big oh notation. Similarly for detailed analysis of space complexity we count the number of memory references and finally add all steps and find their big oh notation.

E.g.

#include<stdio.h>

int main()

{

    int i, n, fact=1;

    printf("Enter a number to calculate factorial:");

    scanf("%d",&n);

    for(i=1; i<=n; i++)

            fact = fact*i;

    printf("Factorial of %d=%d", n, fact);

    return 0;

}

Time Complexity:

The declaration statement takes 1 step.

Printf statement takes 1 step.

Scanf statement takes 1 step.

In for loop:

    i=1 takes 1 step

    i<=n takes (n+1) step

    i++ takes n step

    within for loop fact=fact*i takes n step

printf statement takes 1 step

return statement takes 1 step

Total time complexity = 1+1+1+1+n+1+n+n+1+1

           = 3n+7

           = O(n)

Space complexity:

total memory references used = 3 = O(1)

Given Infix expression.

A + (((B-C) * (D-E) + F)/G) $ (H-I)

Converting it to postfix:

 Therefore, postfix expression of given infix expression is: ABC-DE-*F+G/HI-$+

Now, 

Evaluating the postfix expression for the given values:

A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1

ABC-DE-*F+G/HI-$+

6 2 4 - 3 8 - * 2  +3 / 5 1 - $ +

Algorithm to convert infix to postfix expression using stack is given below:

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Given,

Infix expression = (A + B)*(C - D)

Converting to postfix:

Postfix expression of given infix is A B + C D - *

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void push(int);

void pop();

void display();

int stack[SIZE], top = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

          case 1: printf("Enter the value to be insert: ");

                  scanf("%d",&value);

                  push(value);

                  break;

          case 2: pop();

                  break;

          case 3: display();

                  break;

          case 4: exit(0);

          default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void push(int value){

   if(top == SIZE-1)

      printf("\\nStack is Full!!! Insertion is not possible!!!");

   else{

      top++;

      stack[top] = value;

      printf("\\nInsertion success!!!");

   }

}

void pop(){

   if(top == -1)

      printf("\\nStack is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", stack[top]);

      top--;

   }

}

void display(){

   if(top == -1)

      printf("\\nStack is Empty!!!");

   else{

      int i;

      printf("\\nStack elements are:\\n");

      for(i=top; i>=0; i--)

          printf("%d\\n",stack[i]);

   }

}

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Stack as ADT

A stack of elements of type T is a finite sequence of elements of T together with the operations

• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
•  IsFull(S): Determine if S is full or not. Return true if S is full stack; return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty stack; return false otherwise.

Thus by using a stack we can perform above operations thus a stack acts as an ADT.

Primitive operations of stack

The following operations can be performed on a stack:

1. PUSH operation: The push operation is used to add (or push or insert) elements in a Stack.

ü  When we add an item to a stack, we say that we push it onto the stack

ü  The last item put into the stack is at the top

2. POP operation: The pop operation is used to remove or delete the top element from the stack.

  üwe remove an item, we say that we pop item from the stack.

 üWhen an item popped, it is always the top item which is removed.

The PUSH and the POP operations are the basic or primitive operations on a stack. Some others operations are:

• CreateEmptyStack operation: This operation is used to create an empty stack.
• IsFull operation: The isfull operation is used to check whether the stack is full or not ( i.e. stack overflow)
•  IsEmpty operation: The isempty operation is used to check whether the stack is empty or not. (i. e. stack underflow)
• Top operations: This operation returns the current item at the top of the stack, it doesn’t remove it

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Difference between Stack and Queue

Program to implement stack operations

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void push(int);

void pop();

void display();

int stack[SIZE], top = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

          case 1: printf("Enter the value to be insert: ");

                  scanf("%d",&value);

                  push(value);

                  break;

          case 2: pop();

                  break;

          case 3: display();

                  break;

          case 4: exit(0);

          default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void push(int value){

   if(top == SIZE-1)

      printf("\\nStack is Full!!! Insertion is not possible!!!");

   else{

      top++;

      stack[top] = value;

      printf("\\nInsertion success!!!");

   }

}

void pop(){

   if(top == -1)

      printf("\\nStack is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", stack[top]);

      top--;

   }

}

void display(){

   if(top == -1)

      printf("\\nStack is Empty!!!");

   else{

      int i;

      printf("\\nStack elements are:\\n");

      for(i=top; i>=0; i--)

          printf("%d\\n",stack[i]);

   }

}

The expression in which operator is written in after the operands is called postfix expression. For example: AB+

Algorithm to evaluate value of postfix expression

1.      Create a stack to store operands.

2.      Scan the given expression from left to right.

3.      a) If the scanned character is an operand, push it into the stack.

      b)  If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.

4.      Repeat step 3 till all the characters are scanned.

5.      When the expression is ended, the number in the stack is the final result.

Given,

infix expression = (A+B*C)+(D-E/ F)

Now, converting it into postfix:

The  postfix expression of given infix expression is: A B C * + D E F / - +

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Algorithm for evaluation of postfix expression

1. Create a stack to store operands.

2.  Scan the given expression from left to right.

3. a) If the scanned character is an operand, push it into the stack.

      b) If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.

4. Repeat step 3 till all the characters are scanned.

5. When the expression is ended, the number in the stack is the final result.

Example:

Let the given expression be “456*+“. We scan all elements one by one.

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Now,

To convert postfix to prefix we use following algorithm:

1. Read the Postfix expression from left to right

2. If the symbol is an operand, then push it onto the Stack

3. If the symbol is an operator, then pop two operands from the Stack 

Create a string by concatenating the two operands and the operator before them. 

    string = operator + operand2 + operand1 

        And push the resultant string back to Stack

4. Repeat the above steps until end of Prefix expression.

Stack

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Implementation of stack using array

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void push(int);

void pop();

void display();

int stack[SIZE], top = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

          case 1: printf("Enter the value to be insert: ");

                  scanf("%d",&value);

                  push(value);

                  break;

          case 2: pop();

                  break;

          case 3: display();

                  break;

          case 4: exit(0);

          default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void push(int value){

   if(top == SIZE-1)

      printf("\\nStack is Full!!! Insertion is not possible!!!");

   else{

      top++;

      stack[top] = value;

      printf("\\nInsertion success!!!");

   }

}

void pop(){

   if(top == -1)

      printf("\\nStack is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", stack[top]);

      top--;

   }

}

void display(){

   if(top == -1)

      printf("\\nStack is Empty!!!");

   else{

      int i;

      printf("\\nStack elements are:\\n");

      for(i=top; i>=0; i--)

          printf("%d\\n",stack[i]);

   }

}

E.g.

Queue

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.

Implementation of Queue using array

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void enQueue(int);

void deQueue();

void display();

int queue[SIZE], front = -1, rear = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Insertion\\n2. Deletion\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

         case 1: printf("Enter the value to be insert: ");

                scanf("%d",&value);

                enQueue(value);

                break;

         case 2: deQueue();

                break;

         case 3: display();

                break;

         case 4: exit(0);

         default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void enQueue(int value){

   if(rear == SIZE-1)

      printf("\\nQueue is Full!!! Insertion is not possible!!!");

   else{

      if(front == -1)

         front = 0;

      rear++;

      queue[rear] = value;

      printf("\\nInsertion success!!!");

   }

}

void deQueue(){

   if(front == rear)

      printf("\\nQueue is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", queue[front]);

      front++;

      if(front == rear)

         front = rear = -1;

   }

}

void display(){

   if(rear == -1)

      printf("\\nQueue is Empty!!!");

   else{

      int i;

      printf("\\nQueue elements are:\\n");

      for(i=front; i<=rear; i++)

         printf("%d\\t",queue[i]);

   }

}

E.g.

Given postfix expression:

AB + C*DC – -FG + $

Expression tree for given expression is constructed below:

Given postfix expression:

AB − C + DEF − + $

Converting it into infix:

 The infix expression of given postfix expression is: (((A-B)+C)$ (D-(E-F)))

Abstract data types are a set of data values and associated operations that are precisely independent of any particular implementation. Generally the associated operations are abstract methods. E.g. stack, queue etc.

Stack as an ADT

A stack of elements of type T is a finite sequence of elements of T together with the operations

• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
•  IsFull(S): Determine if S is full or not. Return true if S is full stack; return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty stack; return false otherwise.

Thus by using a stack we can perform above operations thus a stack acts as an ADT.

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5.  If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5.  If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Stack as ADT

A stack of elements of type T is a finite sequence of elements of T together with the operations

• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
•  IsFull(S): Determine if S is full or not. Return true if S is full stack; return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty stack; return false otherwise.

Thus by using a stack we can perform above operations thus a stack acts as an ADT.

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).