INFIX INTO PREFIX Expression - DSTC using C Language (Source Code Implemented)

INFIX INTO PREFIX Expression
Implemented using C Language

C Language Code: 

---

INTOPRE.C

---

 //   DSTC  --- INTOPRE.C  .....
// using the Stacks ... in linked list s

#include "stack.h"
#include<string.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0

int isOperand(char a)
{
    if(a>='0' && a<='9')
        return TRUE;
    else
        return FALSE;
}

int prec(char op)
{
    switch(op) {
case '$':
    return 3;
case '*': case '/':case '%':
    return 2;
case '+': case '-':
    return 1;
    };
    return 0;
}

void main()
{
    char in[80];
    char pre[80];
    void reverse(char arr[]);
    int i,k;
    char c;

    Stack *s;
    s=GetStack();
    clrscr();

    printf("Enter Infix expression: ");
    gets(in);

 

 

for(i=strlen(in)-1,k=0;i>=0;i--)
    {
        if(isOperand(in[i]))
            pre[k++]=in[i];
        else
        {
            if(empty(s) || in[i]==')')
                //if intially stack is empty
                //or current operator is '('
                //then push current operator
                push(s,in[i]);
            else if(in[i]=='(')
            {
                //pop all the operators till '('
                //is encountered
                while((c=pop(s))!=')')
                    pre[k++]=c;
            }
            else if(prec(in[i]) < prec(s->top->info))
            {
                //if precedence of current operator is
                //less than or equal to the operator at the
                //top of the stack, then pop all
                //higher or equal precedence operators
                while(prec(in[i]) <= prec(s->top->info) && !empty(s))
                    pre[k++]=pop(s);
                push(s,in[i]);
            }
            else
 push(s,in[i]);
        }
    }
    //pop all the remaining operators
    while(!empty(s))
        pre[k++]=pop(s);
    pre[k++]='\0';

 

 

    reverse(pre);
    printf("The prefix expression is: %s", pre);
}

void reverse(char arr[])
{
    int i,j;
    char c;
    i=strlen(arr)-1;
    j=0;
    while(i>=(strlen(arr)/2))
    {
        c=arr[i];
        arr[i]=arr[j];
        arr[j]=c;
        j++;
        i--;
    }
}

---

STACK.H

---

 // DSTC ---- STACK.H .....
// stacks using LINKED LIST ...

#include <stdio.h>
#include <stdlib.h>
typedef struct nd
{
    int info;
    struct nd *next;
}Node;

typedef struct {
    Node *top;
}Stack;

Stack * GetStack()
{
    Stack *temp;
    temp=(Stack *)malloc(sizeof(Stack));
    temp->top=NULL;
    return temp;
}

Node * GetNode()
{
    Node *n;
    n=(Node *)malloc(sizeof(Node));
    return n;
}

int empty(Stack *s)
{
    if(s->top==NULL)
        return 1;
    else
        return 0;
}

void push(Stack *s, int i)
{
    Node *n;
    n=GetNode();
    n->info=i;
    n->next=s->top;
    s->top=n;
}

int pop(Stack *s)
{
    int i;
    Node *t;
    if(s->top==NULL)
    {
        printf("Stack underflow\n");
        return NULL;
    }

    i=s->top->info;
    t=s->top;
    s->top=t->next;
    free(t);
    return i;
}