Question ============================================ Write a C program to conve

Question

Question

============================================

Write a C program to convert INFIX expression to PREFIX expression.Use suitable data structure.

============================================

ATTENTION

The assignment is to convert INFIX to ""PREFIX"" and not "POSTFIX" as sir mentioned in class.

============================================

Input to program

The program should read the infix expression string from the standard input (i.e keyboard)

The expression can have following binary operators only:

Operators Operation

+ Addition

- Subtraction

/ Division

* Multiplication

$ Exponentiation

() Parentheses

For simplicity assume that the operands are single digit numbers. for eg 23 means operand1 = 2 & operand2 = 3

and should not be interpreted as two digit number 23.

Example infix expression string: "(2+3*5/7)$2"

Use command line arguments to take the input from user.

Example : in2prefix.exe (2+3*5/7)$2

** Assume the expression may contain both Parentheses and exponentiation **

** Your code should take care of both possibilities **

============================================

Output of program

Print the PREFIX expression as the output if the INFIX expression is correct otherwise print the message "Invalid Expression!".

============================================

Program file submission

Submit a single file with name in2prefix.c.

============================================

Evaluation

The submitted code will be evaluated only if it compiles succesfullly in a gcc compiler & runs without any run time error.

Please comment wherever necessary.

Explanation / Answer

// Infix to prefix conversion
// input example >> c:/assignment>in2prefix.exe a+b*c
//multiple parenthesis are allowed but use only small brackets i.e ()

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define IPSIZE 25
int prcd(char optr) //precedence values
{
   switch(optr)
   {
       case '$': return (5) ; break; //exponential
       case '(': return (4) ; break;
       case ')': return (-1) ; break;
       case '/': return (3) ; break;
       case '*': return (2) ; break;
       case '+': return (1) ; break;
       case '-': return (1) ; break;
       default : return (0); break;
   }
}

int main(int arg,char *argv[])
{
   int l,index,optrindex=-1,i,j=0;
   char symb;
   char input[IPSIZE+1],*output,*optr,*finaloutput;
//printf("Please give the input infix string (Max length %d) terminating by enter. ",IPSIZE);
//printf("Operators available are ( )(small brackets), +, -, *, /, $(exponential). ");
//scanf("%s",argv[1]);
strcpy(input,argv[1]);
l=strlen(input);
if (l<3){
   printf(" ERROR : Minmum length of input should be 3 ");
   goto end;
}
index=l-1;
output=(char*)malloc(sizeof(char)*(l));     //Dynamically Array Allocation
optr=(char*)malloc(sizeof(char)*(l));
while(l--)
{
   symb=input[l];              // input will be procedded from right to left
   if(!prcd(symb)) // if symb is not an operator
   {
       output[index]=symb;
           index--;  
   }
   else
       {
           if(((optrindex==-1) || optr[optrindex]==')')&& prcd(symb)!=5 && prcd(symb)!=4 && prcd(symb)!=-1)
           {//either oprator array is empty or closed bracket is last operator && symb is not $,(or )
               optrindex++;
               optr[optrindex]=symb;   
           }
           else
           {
          
               if(prcd(symb)==-1)
               {//close bracket
                   output[index]=symb;
                   index--;
                   optrindex++;
                   optr[optrindex]=symb;
                  
               }
               else if(prcd(symb)==4)
               {//open bracket
                   while(!(optr[optrindex]==')'))
                   {
                       output[index]=optr[optrindex];
                       index--;
                       optrindex--;
                   }
                   output[index]=symb;
                   index--;
                   optrindex--;
               }
               else
               {
                   while(1)
                   {// do operation until all element having more precedence than symb are popped out
                       if(symb=='$' && optr[optrindex]=='$')
                       {
                           output[index]=optr[optrindex];
                           index--;  
                           optrindex--;
                       }
                  
                       else if (prcd(symb)<prcd(optr[optrindex]))
                       {
                           output[index]=optr[optrindex];
                           index--;  
                           optrindex--;
                       }
                       else
                       {
                           optrindex++;
                           break;
                       }
                   }
                   optr[optrindex]=symb;
               }  
           }      
       }
}  
while(!(optrindex==-1))
{//after scaning whole input, operator in operator array are popped out
   output[index]=optr[optrindex];
   index--;
   optrindex--;
}
finaloutput=(char*)malloc(sizeof(char)*(l+1));
for(i=0;i<strlen(input);i++)
   {// removing parenthesis
       if(output[i]=='(' || output[i]==')'){}
       else{
           finaloutput[j]=output[i];
           j++;
       }          
   }
   finaloutput[j]=''; // to make finaloutput a string
   printf(" prefix output == %s ",finaloutput);
end:   
   return 0;
}//end

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.