C Program for Infix to Prefix Conversion

C Program for Infix to Prefix Conversion.
Source: Dr. G T Raju, Professor & Head, Dept. of CSE, RNSIT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define SIZE 50            /* Size of Stack */
#include<string.h>
#include <ctype.h>
char s[SIZE];
int top=-1;       /* Global declarations */
 
push(char elem)
{                       /* Function for PUSH operation */
    s[++top]=elem;
}
 
char pop()
{                      /* Function for POP operation */
    return(s[top--]);
}
 
int pr(char elem)
{                 /* Function for precedence */
    switch(elem)
    {
    case '#': return 0;
    case ')': return 1;
    case '+':
    case '-': return 2;
    case '*':
    case '/': return 3;
    }
}
 
main()
{                         /* Main Program */
    char infx[50],prfx[50],ch,elem;
    int i=0,k=0;
    printf("\n\nRead the Infix Expression ? ");
    scanf("%s",infx);
    push('#');
    strrev(infx);
    while( (ch=infx[i++]) != '\0')
    {
        if( ch == ')') push(ch);
        else
            if(isalnum(ch)) prfx[k++]=ch;
            else
                if( ch == '(')
                {
                    while( s[top] != ')')
                        prfx[k++]=pop();
                    elem=pop(); /* Remove ) */
                }
                else
                {       /* Operator */
                    while( pr(s[top]) >= pr(ch) )
                        prfx[k++]=pop();
                    push(ch);
                }
    }
    while( s[top] != '#')     /* Pop from stack till empty */
        prfx[k++]=pop();
    prfx[k]='\0';          /* Make prfx as valid string */
    strrev(prfx);
    strrev(infx);
    printf("\n\nGiven Infix Expn: %s  Prefix Expn: %s\n",infx,prfx);
}

11 Responses to “C Program for Infix to Prefix Conversion”

  1. line 52: while( pr(s[top]) >= pr(ch) )
    modify as
    while( pr(s[top]) > pr(ch) )
    now correct ans.
    Btw great simple prog. I searched too many places but never found this.
    Hats off.

    Reply
  2. test the output for input case (1+1) and figure out where it went wrong…………………………………happy coding\\\\\

    Reply
  3. I want to solve this program…..any solve this???

    #define SIZE 50
    #include
    #include
    #include

    char s[SIZE];
    int top = -1;
    void i2p(char[]);

    void push(char data)
    {
    s[++top] = data;
    }

    char pop()
    {
    return s[top–];
    }

    int stack_empty()
    {
    if(top == -1)
    return 1;
    else
    return 0;
    }

    int precstack(char elem)
    {
    switch(elem)
    {
    case ‘)’:
    return 1;
    case ‘+’:
    case ‘-‘:
    return 3;
    case ‘*’:
    case ‘/’:
    return 5;
    case ‘^’:
    return 7;
    }
    }

    int precinput(char elem)
    {
    switch(elem)
    {
    case ‘(‘:
    return 1;
    case ‘+’:
    case ‘-‘:
    return 4;
    case ‘*’:
    case ‘/’:
    return 6;
    case ‘^’:
    return 8;
    }
    }

    void strreverse(char s[])
    {
    int i, len = 0;
    char temp;
    len = strlen(s) – 1;
    for(i = 0; i < strlen(s); i++)
    {
    temp = s[i];
    s[i] = s[len];
    s[len–] = temp;
    }

    }

    int main()
    {
    char infx[50],ch;
    scanf("%s",infx);
    printf("Prefix expression is : \n");
    // printf("%s\n" ,i2p(infx));
    i2p(infx);
    return 0;
    }

    void i2p(char infx[])
    {
    char prfx[50], ch, elem;
    int i = 0, k = 0;
    strreverse(infx);
    while((ch=infx[i++]) != '\0')
    {
    if( ch == ')') push(ch);
    else if(isalnum(ch))
    prfx[k++]=ch;
    else if( ch = '(')
    {
    while( s[top] != ')')
    prfx[k++]=pop();
    elem=pop();
    }
    else
    {
    while(stack_empty() != 1)
    {

    if(precinput(ch) <=precstack(s[top]))

    prfx[k++]=pop();
    else
    break;
    }
    push(ch);
    }
    }
    while( stack_empty() != 0)

    prfx[k++]=pop();
    prfx[k]='\0';
    strreverse(prfx);
    strreverse(infx);

    printf("%s\n" ,prfx);
    }

    Reply
    • Nipun goel

      yeah ,i did it on wipro campus arena and definitely not going to tell you before the competition is over.

      Reply
  4. Ravi fulani

    can anyone tell me what this lines mean while (pr(s[top]) >= pr(ch))……………………………….

    Reply
  5. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63

    #define SIZE 50 /* Size of Stack */
    #include
    #include
    char s[SIZE];
    int top=-1; /* Global declarations */

    push(char elem)
    { /* Function for PUSH operation */
    s[++top]=elem;
    }

    char pop()
    { /* Function for POP operation */
    return(s[top–]);
    }

    int pr(char elem)
    { /* Function for precedence */
    switch(elem)
    {
    case ‘#’: return 0;
    case ‘)’: return 1;
    case ‘+’:
    case ‘-‘: return 2;
    case ‘*’:
    case ‘/’: return 3;
    }
    }

    main()
    { /* Main Program */
    char infx[50],prfx[50],ch,elem;
    int i=0,k=0;
    printf(“\n\nRead the Infix Expression ? “);
    scanf(“%s”,infx);
    push(‘#’);
    strrev(infx);
    while( (ch=infx[i++]) != ‘\0’)
    {
    if( ch == ‘)’) push(ch);
    else
    if(isalnum(ch)) prfx[k++]=ch;
    else
    if( ch == ‘(‘)
    {
    while( s[top] != ‘)’)
    prfx[k++]=pop();
    elem=pop(); /* Remove ) */
    }
    else
    { /* Operator */
    while( pr(s[top]) >= pr(ch) )
    prfx[k++]=pop();
    push(ch);
    }
    }
    while( s[top] != ‘#’) /* Pop from stack till empty */
    prfx[k++]=pop();
    prfx[k]=’\0′; /* Make prfx as valid string */
    strrev(prfx);
    strrev(infx);
    printf(“\n\nGiven Infix Expn: %s Prefix Expn: %s\n”,infx,pr

    Reply
  6. archit singal

    please i am getting run time error in this program can anyone solve this and tell my mistake

    #include
    #include
    #include
    struct stack
    {
    int top;
    char items[50];
    };
    void push(struct stack*,char);
    int pop(struct stack*);
    int pr(struct stack*,char);
    void main()
    {
    struct stack s;
    char infx[50];
    int element;
    char poststr[50];
    printf(“enter the expression in the infix form to convert it into prefix\n”);
    gets(infx);
    strrev(infx);
    struct stack*p=&s;
    push(&s,’#’);
    char ch;
    int i,j;
    while((ch=infx[i++])!=’\0′)
    {
    if(ch=='(‘)
    {
    push(&s,ch);
    }
    if(isalnum(ch))
    {
    poststr[j++]=ch;
    }
    else
    {
    if(ch==’)’)
    {
    while(p->items[p->top]!='(‘)
    {
    poststr[j++]=pop(&s);
    }
    element=pop(&s); /*popping the ( element from the stack */
    }
    while(pr(&s,p->items[p->top])>pr(&s,ch))
    {
    poststr[j++]=pop(&s);
    }
    push(&s,ch);

    }
    }
    while(p->items[p->top]!=’#’)
    {
    poststr[j++]=pop(&s);
    }
    strrev(poststr);
    printf(“the required answer is as folows : %s”,poststr);
    }
    int pr(struct stack*p,char ele)
    {
    switch(ele)
    {
    case ‘+’:return 0;break;
    case ‘-‘:return 0;break;
    case ‘*’:return 1;break;
    case ‘/’:return 1;break;
    case ‘$’:return 2;break;
    }
    }
    void push(struct stack*p,char ele)
    {
    p->items[++(p->top)]=ele;
    }
    int pop(struct stack*p)
    {
    return(p->items[(p->top)–]);
    }

    Reply

Leave a Reply