Problem in converting infix expression to a prefix one

Question

Here I am converting an infix expression to a prefix expression.

For some test cases my result is perfect.

But for certain test cases I get an output which is correct according to some sites but wrong according to other sites. So I am in a dilemma as to whether my code is correct or not.

For example, if infix expression is:

A+B*C+D

then output according to my code is:

+A+*BCD

But some site mentions the output as:

++A*BCD

for the same input.

#include<stdio.h>
#include<string.h>
int main()
{
    int top=-1,k=0,i,l,top2=-1,j,a,t,m,t1;
    char s[100] ,s2[100],n, main[100];
    char q[100],p[100];
    printf("\nenter string :");
    gets(main);
    for(i=strlen(main)-1;i>=0;i--)
    {
        if(main[i]=='(')
        {
          q[k]=')';
        }
        else if(main[i]==')')
        {
            q[k]='(';
        }
        else
        {
            q[k]=main[i];
        }

        q[k+1]='\0';
        k++;
    }
    k=0;
    strcat(q,")");
    s[++top]='(';
    for(i=0;i<strlen(q);i++)
    {

        if(q[i]>='a' && q[i]<='z'   || q[i]>='A' && q[i]<='Z' || q[i]>='0' && q[i]<='9')
        {
            p[k]=q[i];
            p[k+1]='\0';
            k++;
        }

        else if (q[i]=='(')
        {
            s[++top]=q[i];
        }

        else if (q[i]==')')
        {
            for(j=top;j>=0;j--)
            {
                if(s[j]!='(')
                {
                    s[top--];
                    p[k]=s2[top2];
                    p[k+1]='\0';
                    s2[top2--];
                    k++;

                }
                else
                    break;
            }
            s[top--];

        }
        else if(q[i]=='+' || q[i]=='-' || q[i]=='*' || q[i]=='/' || q[i]=='^' || q[i]=='%')
        {

              if(q[i]=='+' || q[i]=='-')
            {
               n='1';
            }
            else if(q[i]=='*' || q[i]=='/' || q[i]=='%')
            {
                n='2';
            }
            else if (q[i]=='^')
            {
               n='3';
            }

                t=n-48;

             if(top2!=-1)
             {
           for(j=top;j>=0;j--)
           {
              t1=s[j]-48;

               if(t<=t1 )
               {
                    s[top--];
                    p[k]=s2[top2];
                    p[k+1]='\0';
                    k++;
                    s2[top2--];

               }
               else if(s[j]=='(')
                        break;

            }
            }
             s[++top]=n;
             s2[++top2]=q[i];
        }
}
k=0;
for(i=strlen(p)-1;i>=0;i--)
{
    main[k]=p[i];
    main[k+1]='\0';
    k++;
}
printf("\nFINAL ANSWER :\n");
printf("\n%s",main);
}

But according to the algorithm of infix to prefix conversion, output I get is: ````+A+*BCD```` — Umang, Apr 18 '20 at 07:18
Then I think you have a bug somewhere. See also https://scanftree.com/Data_Structure/infix-to-prefix — Paul Ogilvie, Apr 18 '20 at 08:39
Suggest reading [infix prefix postfix expressions](https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html) — user3629249, Apr 18 '20 at 17:36
the posted code causes the compiler to output a LONG string of warning messages. Starting with the variable declaration: `main[100];` as 'main' is the (must have) name for the starting point function. When compiling, always enable the warnings, then fix those warnings. ( for `gcc`, at a minimum use: `-Wall -Wextra -Wconversion -pedantic -std=gnu11` ) Note: other compilers use different options to produce the same results. — user3629249, Apr 18 '20 at 17:42
regarding: `gets(main);` the function: `gets()` has been depreciated for years and completely removed from the C language (about) 2009. Suggest using the function: `fgets()`, which has a different parameter list, so suggest reading the MAN page for `fgets()` — user3629249, Apr 18 '20 at 17:43
regarding: `for(i=strlen(main)-1;i>=0;i--)` the function: `strlen()` returns the offset to the last character, it does not include the trailing NUL byte. So the `-1` is probably wrong. Also, `strlen()` returns a `size_t`, not a `int`, so the declaration of `i` should be `size_t i;` not `int i;`. — user3629249, Apr 18 '20 at 17:46
OT: for ease of readability and understanding: 1) please consistently indent the code. Suggest each indent level be 4 spaces. 2) please follow the axiom: *only one statement per line and (at most) 1 variable declaration per statement. — user3629249, Apr 18 '20 at 17:51
regarding: `if(q[i]>='a' && q[i]<='z' || q[i]>='A' && q[i]<='Z' || q[i]>='0' && q[i]<='9')` Please use parens to clarify. Even the compiler complained with: *untitled2.c:34:22: warning: suggest parentheses around ‘&&’ within ‘||’ [-Wparentheses]* — user3629249, Apr 18 '20 at 17:53
regarding: `t=n-48;` Since the preceding `if/else if` chain is missing a final `else` the variable 'n' might be used with out being initialized — user3629249, Apr 18 '20 at 18:06
the posted code contains a LOT of calculated values that are never used and contains a LOT of unused variables. Please correct. — user3629249, Apr 18 '20 at 18:08

Problem in converting infix expression to a prefix one

0 Answers0