Data Structures Module-III

 Module-III

III) Exercise Programs on Stack Applications

a) Implement stack operations using

                 i) Arrays     ii) Linked List

b) Conversion of Infix Expression to postfix Expression.

c) Evaluation of Postfix Expression

d) Write a program to reverse given linked list using stack.

 

b) Conversion of Infix Expression to postfix Expression.

Source Code:-

#include<stdio.h>

#include<stdlib.h>

#include<ctype.h>

void push(char);

char pop();

int priority(char);

int top=-1;

char stack[20];

int main()

{

 

    char postfix[30],infix[30],ch;

    int i,j=0;

    printf("\n enter infix expression\n");

    gets(infix);

    for(i=0;infix[i]!='\0';i++)

    {

        ch=infix[i];

        if(ch=='(')

            push(ch);

        else if(ch==')')

        {

            while(stack[top]!='('&&top!=-1)

            {

                postfix[j]=pop();

                j++;

            }

            pop();

        }

        else if(isalpha(ch)||isdigit(ch))

        {

            postfix[j]=ch;

            j++;

        }

        else

        {

            while(priority(ch)<=priority(stack[top])&&top!=-1)

            {

                postfix[j]=pop();

                j++;

            }

            push(ch);

        }

    }

    while(top!=-1)

    {

        postfix[j]=pop();

        j++;

    }

    postfix[j]='\0';

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

    return 0;

}

void push(char x)

{

    top++;

    stack[top]=x;

}

char pop()

{

    return stack[top--];

}

int priority(char ch)

{

    if(ch=='(')

    return 0;

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

        return 1;

    else if(ch=='*'||ch=='/'||ch=='%')

        return 2;

    else if(ch=='^')

        return 3;

}

Output:

enter infix expression

a+b*c-d/f

 result is abc*+df/-

--------------------------------

Process exited after 37.74 seconds with return value 0

Press any key to continue . . .

  

c) Evaluation of Postfix Expression

Source code:-

#include<stdio.h>

#include<stdlib.h>

#include<ctype.h>

#include<math.h>

int stack[20];

char postfix[20],ch;

void push(int);

int pop();

int top=-1,res;

int main()

{

    int i,op1,op2;

    printf("\n enter postfix expression\n");

    gets(postfix);

    for(i=0;postfix[i]!='\0';i++)

    {

        ch=postfix[i];

        if(isdigit(ch))

            push(ch-48);

        else

        {

            op2=pop();

            op1=pop();

            switch(ch)

            {

                case'+':push(op1+op2);

                break;

                case'-':push(op1-op2);

                break;

                case'*':push(op1*op2);

                break;

                case'/':push(op1/op2);

                break;

                case'%':push(op1%op2);

                break;

                case'^':res=pow(op1,op2);

                push(res);

                break;

            }

        }

    }

    printf("\n the result of postfix expression is %d",pop());

    return 0;

}

void push(int x)

{

    top++;

    stack[top]=x;

}

int pop()

{

    return stack[top--];

}

Output:-

enter postfix expression

6523+8*+3+*

 

 the result of postfix expression is 288

--------------------------------

Process exited after 22.08 seconds with return value 0

Press any key to continue . . .

 

d) Write a program to reverse given linked list using stack.

#include<stdio.h>

#include<malloc.h>

struct node

{

    int data;

    struct node* next;

};

//Globally initialized head pointer

struct node* head = NULL;

 //function prototyping

struct node* create_node(int);

void insert_begin(int);

void reverse_list();

void print();

int main()

{

    /* Create some nodes and insert data into them */

    insert_begin(10);

    insert_begin(90);

    insert_begin(31);

    insert_begin(78);

    insert_begin(99);

    printf("Linked List before reversed: \n");

    print();

    reverse_list();

    printf("\nLinked List after reversed: \n");

    print();

    return 0;

}

struct node* create_node(int data)

{

    struct node* new_node = (struct node*) malloc (sizeof(struct node));

    if (new_node == NULL)

    {

        printf("Memory can't be allocated for new node");

        return NULL;

    }

    else

    {

        new_node -> data = data;

        new_node -> next = NULL;

        return new_node;

    }

}

void insert_begin(int data)

{

    struct node* new_node = create_node(data);

    if (new_node != NULL)

    {

        new_node -> next = head;

        head = new_node;

    }

}

void reverse_list()

{

    if (head == NULL)

    {

        return;

    }

     //create a stack of size of 100

    struct node* stack[100];

    int top = -1;

    struct node* temp = head;

     // push list node into the stack

    while (temp != NULL)

    {

        top += 1;

        stack[top] = temp;

        temp = temp->next;

    }

     // make a new head node

    head = stack[top];

    temp = stack[top];

     // pop the nodes from the stack and insert them at the end of the last node

    while (--top >= 0)

    {

        temp->next = stack[top];

        temp = stack[top];

    }

    // terminate the list

    temp->next = NULL;

}

void print()

{

    struct node* temp = head;

    while (temp != NULL)

    {

        printf("%d --> ", temp->data);

        temp = temp->next;

    }

    printf("NULL \n");

}

 

Output:

Linked List before reversed:

99 --> 78 --> 31 --> 90 --> 10 --> NULL

 

Linked List after reversed:

10 --> 90 --> 31 --> 78 --> 99 --> NULL

 

 


Comments

Post a Comment

Popular posts from this blog

ML QP

  Machine Learning Lab External 1. a) Create a small dataset with at least 10 records and 4 columns: ·          Age (numeric) ·          Height (numeric) ·          Weight (numeric) ·          City (categorical, with possible values: "City A", "City B", "City C")    b) Ensure that some entries in the Age and Weight columns contain missing values. ·          Handle missing data by: o    Replacing missing values in the Age column with the average age . o    Replacing missing values in the Weight column with the median weight .    c) Normalize the Age , Height , and Weight columns using min-max scaling to bring       all values between 0 and 1.    d) Display the original dataset, th...
Read more

Data Structures Module_V

  Module – V   1. Binary Tree Traversals using Linked List Inorder: #include <stdio.h> #include <stdlib.h>   struct Node {     int data;     struct Node* left;     struct Node* right; };   // Function to perform inorder traversal void inorderTraversal(struct Node* root)  {       // Empty Tree     if (root == NULL)         return;       // Recur on the left subtree     inorderTraversal(root->left);       // Visit the current node     printf("%d ", root->data);       // Recur on the right subtree     inorderTraversal(root->right); }   // Function to create a new node struct Node* newNode(int data)  {       struct Node* node = (struct Node*)malloc(size...
Read more

Data Structures Module-IV

  Module-IV 1) Implementation of Queue Operations using                      i) Arrays    ii) Linked List 2) Implementation of Circular Queue Operations using                      i) Arrays    ii) Linked List 3) Implement Dequeue using Linked List.   1) a) Implementation of Queue Operations using Arrays. #include<stdio.h> #include<stdlib.h> #define SIZE 5 void enqueue(); void dequeue(); void display(); int queue[SIZE],front=-1,rear=-1,ele; int main() {     int ch;     while(1)     {     printf("\n menu");     printf("\n 1.enqueue\n 2.dequeue\n 3.display");     printf("\n enter ur choice");     scanf("...
Read more