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

hide comments
surya_55: 2018-12-04 10:43:11

solved by using just stack in one go...!

Ritwik: 2018-12-04 08:18:08

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"

nishantingle5: 2018-11-14 18:29:20

The Great Dijkstra's Shunting Yard Algorithm

pranjulpal18: 2018-11-08 12:12:12

.

boosandi: 2018-11-02 12:52:36

I checked out the Shunting yard problem and implemented it. It was such a beautiful algo.

ianc1339: 2018-10-28 08:57:50

Tbh, I had to search up what RPN was...

s307177205: 2018-10-27 11:01:38

well, the test cases don't contain data like a-b*c, whose priority needs to be considered.

artistic_15: 2018-09-20 20:00:21

easy just use of one stack and one queue.

Last edit: 2018-09-21 08:30:31
marcobw1: 2018-09-11 12:30:22

Last edit: 2018-09-11 12:30:43
probeta: 2018-08-28 18:59:59

Just implement properly !


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
Concept difficulty 23%
Implementation difficulty
Implementation difficulty 24%
160 4