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);
}

10 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

Leave a Reply