Transform the Expression

I think that this problem should give out a list of 'symbols' like ,-,*, etc.
As it didnt mention that any non alphabet is to be considered as a symbol.

a simple infix to postfix transformation????

Does anyone know if the ^ operator is for Exponent or binary XOr? They have different precedence.

It's the power operation.

Is it needed to take care of precedence of the operators?? It is not mentioned in the problem.

From what I can see, the operators are completely paranthesized.

if you assume that everything is parenthesized, and that everything not a lower case letter or a parenthesis is an operator, then you will solve the problem.

A SIGSEGV is usually caused if you try to access memory that is not available to your program. It is a segfault. Check the FAQ for more information.

All inputs are fully parantetized. I see nothing wrong with the inputs you have given. They perfectly fit the input definition provided in the statement and as such are valid.

Is there any special case in this too? Because for sample inputs I am getting correct output, but when I submit, it says wrong answer. I have considered operators +,-,/,*,^ .

The code is tested against test cases other than the sample ones.

Is an expression like (a+b+c) valid?

No, the test cases are in accordance with the format specified.

this is one of the problems where using psyco with Python makes sense, though it's still way slower than a C program with the algorithm I used.

I dont know why I am still getting "SIGSEGV" error while I try to submit for ONP problem. Can anybody help me out?

SIGSEGV indicates a segfault. Check the FAQ and www.codechef.com/wiki for more details. You might want to check for areas in the code where you might be accessing memory you are not supposed to or which doesn't exist.

are there more operators apart from +,-,/,*,^ ?

No.

Just pointing out a small spelling error...

In the 'Input' section of the problem description, it should be 'less than', not 'less then'.

anybody has input data for testing this problem?

I think the problem statement needs to be a little more specific, like if we have to consider upper and lower case to the single letters and which operations are supported. Is it just the ones showed as example (+ - *) or the complete basic operations (+ - * /) or does it even include more symbols like exponentiation (^) or left (-)

of course i'm blind and didn't saw that the exponentiation is actually included...

do v have to put input like abc or the numerical value and get the answer?

For u who working with python, my esperrience below might help.

I always get "runtime error" for this task, today i submit, and still get "runtime error" and then i submit my second code for the purpose to get at least "wrong answer" :

for i in range(t_input):
infix=raw_input()
print 'wtf'

I am shock when i get "correct answer" with time 0.78 s. Then i submit again my wrong submission and finally get "wrong answer". Then i go to my account and look into my "RECENT ACTIVITY FOR THIS USER" and get check mark for first submission and get cross mark for the other.

I know i'm newbie but this is too weird for me. Can someone explain it to me?

i cannot use getche() to get my input... ????

In the Sample problems we don't need to check the operator precedence.. are there other cases in which it is required.. as m getting wrong answer but have tried many combinations according to the sample cases given.

That is already mentioned in earlier comments.

its saying wrong answer pls help me

still wrong answer pls help

Does "Time Limit Exceeded" mean that the solution was correct but only the time limit was not met?

FAQ

@Stephen Merriman : Thanks

With respect to the post from "Aseem Kumar - 23rd Aug,2009 14:52:48.", in reply to which "Admin - 23rd Aug,2009 18:03:51" says that expression of the form (m+(n*o)- p) is totally valid expression. This expression further transforms to (m+x-p). I wonder as to how this can be correct as it is stated in the question that "(no expressions like a*b*c)". Should we handle these kind of expressions as well?

@Stephen Merriman : Thanks

With respect to the post from "Aseem Kumar - 23rd Aug,2009 14:52:48.", in reply to which "Admin - 23rd Aug,2009 18:03:51" says that expression of the form (m+(n*o)- p) is totally valid expression. This expression further transforms to (m+x-p). I wonder as to how this can be correct as it is stated in the question that "(no expressions like a*b*c)". Should we handle these kind of expressions as well?

Does the "SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:" contain only the 1st correct submission only is it? I submitted my solution which took 0.45 Sec and later I improved my algorithm (offcourse seeing the implementation in other language) and reduced the runtime to 0.19. I do not see an entry for this.

Can anyone help me out with my solution. It says :"wrong answer". But I could not point out the problem on my own.

here it goes : http://www.codechef.com/viewsolution/243885

Are there any exceptional test cases?

I hve solved problems in my computer using Turbo C++ IDE...it gives correct solutions...but when i submit it...it sayz error...!!! I can't fix the problem...!!!

You haven't made any submissions to this problem. Did you mean Small Factorials instead? If so, you should read the FAQ. Also, your most recent submission doesn't work for any large inputs - try some.

my program is working perfectly fine for single infix expression.... i am using gets function to collect the infix expression...... but to collect the number of infix expressions ie the first input i cant use scanf bec gets doesnt work wen used after scanf plz guide me............

printf("enter the number of expressions to convert:n);

scanf("%d",&y);??

k=1;

while(k<=y)

{

 printf(" enter the infix expression:n");

gets(infix);????

Why not just continue to use scanf then? Much simpler than trying to use gets.

(By the way, your output must be exactly what the problem statement tells you to print out.. it doesn't start with the word 'enter'..)

i will remove the print f s while submitting in code chef...... in case i want 2 use scanf while taking in the infix expression i should give only fixed length infix expressions or i should be taking an input of size of the infix exp every time.........

like

for(i=0;i<=4;i++)

scanf("%c",&infix[i]); // for giving (2+3) this is fine... but for giving ((2*3)-(1*2)) i hav 2 change the i<=4 to i<=14..... i cant do this 4 each input?......

Respected admin, I have 2 Question 2 ask?

1) From the above given comments, I m not sure whether to check for Precedence of Operators or not b'cause there are already present inside parenthesis?

2)which operators should i check for ... i have taken all the other ASCII characters as operators xcept (97-122,a-z) and (41 , 42 i.e (, ) )....or should i check for only basic operations like +,-,*,^,/ ?

PLease Help as soon as possible .. I have submitted my code 6 times and all time wrong answer ! U can also have a look at my code !

Thanks ! :)

Respected Admin,

Sir I have completed this Problem but before that i got about 6 wrong answers and they were only due to i used link-list for making stacks, but this time i used array for making stack and voila it was a correct submission...Can u just clear my doubt why i was getting wrong answer when i was using link-list,Although it was giving correct answer for every possible INFIX notation in DEVC++.

Thanks ! :)

can anyone plz tell me what's wrong wid this code? i'm getting the right output on ma gcc compiler!

thanx :)

#include<stdio.h>
#include<string.h>
#define MAX 20
char stack[MAX];
int top=-1;
char pop();
void push(char item);
int prcd(char symbol)
{
switch(symbol)
{
case '+':
case '-':return 2;
case '*':
case '/':return 4;
case '^':
case '$':return 6;
case '(':
case ')':
case '#':return 1;
}
}
int isoperator(char symbol)
{
switch(symbol)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '$':
case '(':
case ')':return 1;
default:return 0;
}
}
void convertip(char infix[],char postfix[]){
int i,symbol,j=0;
char test[MAX];
stack[++top]='#';
for(i=0;i<strlen(infix);i++){
symbol=infix[i];
if(isoperator(symbol)==0){
postfix[j]=symbol;
j++;
}
else{
if(symbol=='(')push(symbol);
else if(symbol==')'){
while(stack[top]!='('){
postfix[j]=pop();
j++;
}
pop();//pop out (.
}
else{
if(prcd(symbol)>prcd(stack[top]))
push(symbol);
else{
while(prcd(symbol)<=prcd(stack[top])){
postfix[j]=pop();
j++;
}
push(symbol);
}//end of else.
}//end of else.
}//end of else.
}//end of for.
while(stack[top]!='#')
{
postfix[j]=pop();
j++;
}
postfix[j]='';//null terminate string.
}

void push(char item){
top++;
stack[top]=item;
}
char pop(){
char a;
a=stack[top];
top--;
return a;
}

int main(){
unsigned int inputs,i;
char infix[400],postfix[400];
scanf("%d",&inputs);
for(i=0;i<inputs;i++){
scanf("%s",infix);
convertip(infix,postfix);
printf("%s",postfix);
}
return 0;
}

hi

I've submitted the solution many times but everytime I'm getting a wrong answer. I've tried different ways to solve but nothing seems working. Can I find out what I'm missing. Thanks

#include<stdio.h>
#include<stdlib.h>
#define stacksize 100
#include<string.h>
int top=-1;
char st[stacksize];
void push(char a);
char pop();
char peek();
void push(char a)
{
   
     if(top==(stacksize-1))
     printf("stack full");
     else
     {
         ++top;
         //printf("hi%d",top);
         st[top]=a;
         
         }}
char pop()
{
    if(top==-1)
    return 0;
    else
    {
        //top = top-1;
        return st[top--];
        }}        
char peek()
{
    if(top==-1)
    return 0;
    else
    return st[top];
    }
char p[8][2]={{'(',-1},{'+',1},{'-',1},{'*',2},{'/',2},{'%',2},{'^',3},{')',4}};
int main()
{
     
int ch,i,j,m,k=0,n,test;
char a[400];char pd[100][400];char expr[400];char a1[400];

//printf("enter expression");
scanf("%d",&test);
//printf("%s",a);

//for(i=0;a[i]!='';i++)
//printf("%c",a[i]);
if(test < 100)
{
for(m=0;m<test;m++)
{
                   scanf("%s",a1);
                   strcpy(pd[m],a1);
                   }}
for(m=0;m<test;m++)
{
strcpy(a,pd[m]);
for( i=0;a[i]!='';i++)
{
    //printf("%c",a[i]);
     if(a[i] == '(')
     {
             //printf("one");
             push(a[i]);
             }
             else if(a[i]>='a' && a[i]<='z')
             {
              //printf("two");
              expr[k++] = a[i];
              }
                else if(a[i] == ')')
                {
                   //printf("three");
                     char item;
                item=pop();
               
                                while(item!='(')
                                {
                                expr[k++] = item;
                                item = pop();
                                }
                                }
                               else
                               {
                                               //printf("four");
                                    int precedence;
                                    for( j=0;j<8;j++)
                                    {
                                            if(p[j][0] == a[i])
                                               precedence = p[j][1];
                                              
                                               }
                                               //printf("%d",precedence);
                                               int precedence1;
                                               char rj = peek();
                                        for( j=0;j<8;j++)
                                            {
                                            if(p[j][0] == rj)
                                               precedence1 = p[j][1];
                                               } 
                                            //printf("%d",precedence1);
                                              if(precedence1 >= precedence)
                                               {
                                                            char rt = pop();
                                                            expr[k++] = rt;
                                                            }
                                                            else
                                                            push(a[i]);
                                                            }
                                                            }
                                                           
                 n=k;
                 for(i=0;i<n;i++)
                 printf("%c",expr[i]);
                 printf("n");
                 k=0;                
                 }
                                  
                                                    

return 0;
         }

my code is not getting accepted.It shows run time error.How can i resolve it?

@admin:

On my system I'm getting correct answer for many test cases I've created and also for the sample input given in the problem. May I know what is going wrong. My solution is : http://www.codechef.com/viewsolution/360251

Thank you.

how can i challenge my friends on facebook.

when i click on the link i cant see my friends list

I just found out that not returning 0 in main will produce a Runtime Error!!!!

Is it a convention or necessity to return 0? Logically, if a program runs successfully shouldn't it return 1?

It is a necessity to return 0 (as mentioned in the FAQ). Returning anything else is exactly what signals a runtime error.

Thanks!

@admin: y cannt i submit solution to this problem???? tryin it from morning.... it says cannt submit solution itseems :(

SUMBODY reply .. zzZZzz.. need to move on to next problem..

Can u tell why i am getting wrong answer: i hv run the program for the test cases given and others

my code is

http://www.codechef.com/viewsolution/404848

i got the answer : but i wish to ask that why i was getting wrong answer when i used gets() instead of scanf() in getting infix string as input

fflush(stdin) is undefined and should never be used. See http://c-faq.com/stdio/gets_flush2.html

#include<stdio.h>
#include<string.h>
int stack[100];int top =0;
int push(int f)
{top++;stack[top] = f;}
int pop()
{top--;return(stack[top+1]);}
int pre1(int d){
switch(d){
case 43:
case 45:
return 1;
break;
case 42:
case 47:
return 3 ;
break;
case  94:
return 6;
break;
case 40:
return 9;
break;
case 41:
return 0;
break;
default:
return 7;
break;}}
int pre2(int d){
switch(d){
case 43:
case 45:
return 2;
break;
case 42:
case 47:
return 4;
break;
case  94:
return 5;
break;
case 40:
return 0;
break;
default:
return 8;
break;}}
int main()
{stack[top] = '(';
char a[400];
int l,n,i,j,u,k;
scanf("%d",&n);
for(k=1;k<=n;k++){
scanf("%s",&a);
l = strlen(a);
a[l]=')';
for(i=0;i<l;i++){
j =a[i];
if(pre1(j)>pre2(stack[top])){push(j);}
else{ while(pre1(j)<pre2(stack[top]))
{
printf("%c",pop());}
if(pre1(j) == pre2(stack[top]))
u = pop();
else
push(j);}}
printf("n");}
}
error shown in this code is RUNTIME ERROR ,and run time error  is due "The most common reasons are using too much memory or dividing by zero"..but my memory is 1.6 M and i did'nt divide by zero..can any one tell me whats the error in my code ..please.

hey can somebody plzz tell me why m i getting a wrong ans! I have tried almost every possible test case , even (!a) and (a) as well. but stil I cant find d mistake. http://www.codechef.com/viewsolution/407705 is my code

hey can somebody plzz tell me why m i getting a wrong ans! I have tried almost every possible test case , even (!a) and (a) as well. but stil I cant find d mistake. http://www.codechef.com/viewsolution/407705 is my code

yeeh solved!!!

#include<stdio.h>



char stack[200];
int Top=-1;
char infix[400],postfix[400];
void PUSH(char x)
{
if(Top==200-1)
printf("n Over flow in stack");
else
stack[++Top]=x;
}


char POP()
{
if(Top==-1)
{
return ('');
}
else
return(stack[Top--]);
}

int precedence(char d)
{
int value=0;
switch(d)
{
case '^':value=5;
break;
case '*':
case '/':value=4;
break;
case '-':
case '+':value=3;
break;
}
return value;
}

int main()
{
char c;
int p1=0,p2=0,i=0,j=0,testcase,z=0;

printf("n Enter the number of test cases=");
scanf("%d",&testcase);
while(testcase--)
{
Top=-1;
p1=0;p2=0;i=0;j=0;
printf(" n Enter the infix statement=");
scanf("%s",&infix);
while(infix[i]!='')
{
if( infix[i]>='a' && infix[i]<='z')
{
postfix[j]=infix[i];
j++;
}
else if(infix[i]=='^'||infix[i]=='*' || infix[i]=='/' ||infix[i]=='+' || infix[i]=='-')
{
p1=precedence(infix[i]);
Y : p2=precedence(stack[Top]);
if(p1<=p2)
{
c=POP();
postfix[j]=c;
j++;
goto Y;

}
else
PUSH(infix[i]);
}
else if( infix[i]=='(')
PUSH(infix[i]);
else if(infix[i]==')')
{
while((c=POP())!='(')
{
postfix[j]=c;
j++;
}
}
i++;
}
postfix[++j]='';
printf(" n %s",postfix);
z++;
}

return 1;
}

Why am i getting runtime error?

Try returning 0 , return 1 means that something went wrong

Im getting runtime error with this soultion 
http://www.codechef.com/viewsolution/455706

It runs ok on my pc.

Anyone have some advice ?

http://www.codechef.com/viewsolution/468651

I am getting this as wrogn answer. Any help

nice problem.

@Admin, why my program always takes 1.6M, no matter how much memory I use.

Even if I submit that Life, Universe and everything problem which needs only one variable in the program and simple loop and if statement. Still I get 1.6M ?