My algorithm
- Start from the left
- if it encounters an operator checks the what is to the right of the operator
- if at the right it finds an operand shifts the operator to the right
- if the program finds a bracket to the right it shifts the operator to wherever the bracket closes
- else it leaves the operator wherever it is
I know the stack method but i wanted to implement my own method, and i’m getting right answers for whatever test cases i’ve entered on my own and also the sample test cases
Here’s my code
#include <stdio.h>
#include <string.h>
char postfix[405];
int isOperator(char s)
{
if((s==’+’)|| (s==’-’)||(s==’/’)||(s==’*’)||(s==’^’))
{
return 1;
}
else{
return 0;
}
}
int isOperand(char s){
if(!isOperator(s) && s!=’(’ && s!= ‘)’)
{
return 1;
}
else{
return 0;
}}
int WhereShift(char s[],int i){
int open=0,j=0;
if(isOperand(s[i+1])&&s[i+1]!=’\0’)
{
//printf("%d",i);
return i+1;
}
else if(/isOperand(s[i-1]) &&/ s[i+1]==40)
{
open=1;
for(j=i+2;open>0;j++)
{
if(s[j]==41)
open–;
if(s[j]==40)
open++;
}
return j-1;
}
/else if(s[i-1]==41 && s[i+1]==40)
{
open=1;
for(j=i+2;open>0;j++)
{
if(s[j]==41)
open–;
if(s[j]==40)
open++;
}
return j-1;
}/
else {
return i;
}
}
void shift(char *s, int i, int j)
{
char temp = s[i];
int k;
for(k=i;k<j;k++){
s[k]=s[k+1];
}
s[j]=temp;
//printf("%c%d",temp,j);
//printf("%c",s[j]);
}
void removeBrackets(char *s){
int i;
int k=0;
for(i=0;i<strlen(s);i++){
if(s[i]!=41 && s[i]!=40){
postfix[k++]=s[i];
}
}
}
int main()
{
char s[405];
int t,i,j;
scanf("%d",&t);
for(j=0;j<t;j++){
scanf("%s",s);
for(i=0;i<strlen(s);i++){
if(isOperator(s[i])){
//printf("%d",WhereShift(s,i));
shift(s,i,WhereShift(s,i));
//printf("%s\n",s);
}
}
removeBrackets(s);
//printf("%s",s);
printf("%s\n",postfix);
//printf("%c\n",s[strlen(s)-1]);
}
return 0;
}