SPOJ Problem Set (classical)

4. Transform the Expression

Problem code: ONP

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
Languages:	All except: TECS
Resource:	-

hide comments


2010-02-11 06:16:28 Gene Campbell One other question, I take it the ()'s are optional. My solution works locally, but failed to pass, so I'm guessing I need to assume no ()'s
2010-02-11 04:02:41 Gene Campbell Can recursion and regular expressions be use with Python to do this problem?
2009-09-16 04:14:31 Dan Chrostowski Does the judge allow import statements in Java???? It keeps throwing a compilation error at me when it reads the import statement
2009-08-31 01:12:53 Gabriel Peixoto I forgot to empty my operand stack after reading the expression and got AC! Input: a+b My program answer: ab (without the +)
2009-08-13 12:27:56 Ashish I havnt used any concept of priority , n stil my program got accepted
2009-06-08 08:57:55 Ahmed Chisty just use...infix to postfix algorithm
2009-05-26 21:16:02 Pedro Geraldes yes, that's the problem...your input string is wrong
2009-05-02 08:54:00 Varun Sharma Input String: - 3+42/(1−5)^2^3 My output - 34215-2^3^/+ Correct Answer:- 34215-23^^/+ How come I got Accepted then ? Or does it has something to do with (Assume that there is only one RPN form (no expressions like abc)) ? Last edit: 2009-05-02 08:54:21*