ONP - Transform the Expression

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: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:-

hide comments
2018-12-19 12:21:17
Got it
2018-12-04 10:43:11
solved by using just stack in one go...!
2018-12-04 08:18:08 Ritwik
There is a problem in test cases. My solution is AC in first attempt but later I found out it gives wrong output in those testcases which are without brackets. For example: "a*b+c"
2018-11-14 18:29:20
The Great Dijkstra's Shunting Yard Algorithm
2018-11-02 12:52:36
I checked out the Shunting yard problem and implemented it. It was such a beautiful algo.
2018-10-28 08:57:50
Tbh, I had to search up what RPN was...
2018-10-27 11:01:38
well, the test cases don't contain data like a-b*c, whose priority needs to be considered.
2018-09-20 20:00:21
easy just use of one stack and one queue.

Last edit: 2018-09-21 08:30:31
2018-08-28 18:59:59
Just implement properly !
2018-08-18 17:30:55
AC in one go! :) Used trees though not very fast...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.