ONP - Transform the Expression

no tags 

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Added by:Michał Małafiejski
Date:2004-05-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource:-

hide comments
artista_14: 2015-06-28 15:09:30

STL made code shorter......Excellent problem for beginners.......

Tanuj Kumar: 2015-06-26 13:46:50

Can someone please tell whether it is possible for the SPOJ compiler to judge wrongly. Because my code worked fine on idone.com but it shows wrong answer here. P.S. My code is in C.

Here is my code
https://ideone.com/vcLVot

Last edit: 2015-06-26 14:04:18
uptoyou: 2015-06-24 11:03:43

hint : stack is used for the implementation

uptoyou: 2015-06-24 11:00:45

yeah AC in one go after thinking the algorithm about 1 hour haha, anyway, nice problem :)

vasayashwanth: 2015-06-18 03:43:07

i used cin.getline() to read the input and got WA too many times......and then used cin>> and got AC.....also check that array size is atleast 400

mohit: 2015-06-17 18:47:18

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int pop1(char *arr,int k){
int p;
p=k-1;
while((arr[p]!='(')&&(p>=0)){
printf("%c",arr[p]);
p--;
}

return p;
}
int main(){
int t,i=0;
char c,*arr;
scanf("%d",&t);
while(t--){
arr=(char *)malloc(sizeof(char)*400);
fflush(stdin);
c=getchar();
while(c!='\n'){
if(i<0)
i=0;
if(c=='('){
arr[i]=c;
i++;
}
else if(c==')'){

i=pop1(arr,i);
}
else if((c=='+') ||(c=='-') ||(c=='*') ||(c=='^') ||(c=='/') ){
arr[i]=c;
i++;
}
else
printf("%c",c);
c=getchar();
}
printf("\n");
}
return 0;
}
My code showing wrong answer!!

aveshmeena: 2015-06-12 06:56:34

anyone done this is #c

candide: 2015-06-06 12:33:41

RPN is a little cryptic, isn't it? IMO there are many spoj problems giving more fun and less popular so why this question is so popular (rank 6)?
Remark : Wording specifies operators priority hierarchy but this is misleading : input always comes with fully parenthesized expressions.

Last edit: 2015-06-13 11:24:37
theplaymaker: 2015-05-20 09:12:13

You will step up from amateur level after solving this

karthik1997: 2015-05-17 18:04:07

my code went well in ideone.but its not working in this spoj compiler .and i did it in c
so please help me with that .dont mind fr the large code .PS .i m an amateur
https://ideone.com/nfq3XT


Problem's scores 1 vote

Concept difficulty
Concept difficulty 18%
Implementation difficulty
Implementation difficulty 8%
18