SPOJ.com - Problem ONP

ONP - Transform the Expression

#stack

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+^*

Submit solution!

hide comments

< Previous 16 17 18 19 20 21 22 23 24 25 26 Next >

	Piotr Findeisen: 2013-02-13 15:04:40 Need better test: my accepted solution works incorrectly for: 1 a*b+c
	Giovanni Botta: 2013-01-09 18:19:12 A question about performance: Using Java, I was able to get a time of 0.37. However many people are able to get much faster times. I'm wrapping an InputStreamReader around System.in and a PrintStream wrapped around a BufferedOutputStream wrapped around System.out. I think I found this solution on the forum. I believe my algorithm is optimal and optimized (I use a primitive array as a stack). Do you have suggestions to tune the performance? Thanks!
	Krzysztof Boduch: 2012-09-10 03:00:48 Why there is no objC?
	Hossam El-Deen Goodname: 2012-08-18 16:29:35 @KenCheung As I solved it and got AC, I didn't priority into consideration at all. There're always brackets
	xufei: 2012-06-26 05:51:06 does "Two-argument operators: +, -, , /, ^ (priority from the lowest to the highest)" mean that priority of "-" is higher than that of "+"? Last edit: 2012-06-26 05:51:30*
	:D: 2012-05-08 09:29:58 Try to run it on ideone.com
	Ashish Raj: 2012-05-04 07:15:17 hey...i am writing my code in java...it is working fine in my netbeans..but when i submit here..it is giving me NZEC runtime error..what to do? EDIT, advice: What NZEC means is 'Non-zero exit code'. For java programs, this mean that your program threw an exception. This then translates to, there is some input in the test file for which your program causes an exception to be thrown. Usually check for division by 0, null pointer exceptions, etc. Last edit: 2012-05-12 21:29:08
	H. Gilles: 2012-04-22 22:00:54 Klaus, that's probably because of the language you're using. Or you're just using an incredibly inefficient algorithm. "Coding style" usually refers to the variable naming conventions you use and whatnot, which usually won't affect performance.
	Swati Narang: 2012-01-30 08:00:56 @ Ravi Kumar: For submitting any solution on this site, you should have only one public class in your file(as per Java rules) and the name of this public class should be "Main"(for spoj) :)
	Ravi Kumar: 2012-01-24 12:57:01 Hi i am newbie here i am writing solution in java. my code working fine at my system but when i submit the solution is shows some compilation error. The error is the name of the class is PostFix and it is saying that Class PostFix is public and should be in a file named PostFix.java. Is there any naming convention to follow for the class? Any sugession please.... EDIT, advice: So, here, it isn't obvious at all, but there is a tutorial section on the left. It explains how you are supposed to input your solutions. But for java, this means that you either shouldn't make your class public, or you should change the name to Main. Last edit: 2012-05-12 21:30:35

Submit solution!

Added by:	mima
Date:	2004-05-01
Time limit:	5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6 VB.NET
Resource:	-

Problem's scores 1 vote

Concept difficulty

23%

Implementation difficulty

24%

265 7