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
2023-04-20 11:20:58
As an alternative to shunting yard, you can parse the input to abstract syntax tree, then convert it to reverse polish notation by doing a postorder traversal on the tree.
2022-05-30 16:45:50
if don't know stacks you can use vector but stack makes your life easier. But while using any data structure be aware of the string and char difference and make it a point.
Best of luck
2022-01-13 14:24:00 Simes
@lazorzor. There are multiple test cases. You need to read the number of testcases, and process each one.

Also, check expressions like a+b.


Last edit: 2022-01-13 14:28:07
2022-01-13 12:30:08
PLEASE any help will be immensely appreciated. Please look at the code below.
<snip>

[NG]: Read the footer.

Last edit: 2022-01-15 00:26:39
2022-01-01 05:10:39
If you are really stuck search in google "shuting yard algorithm" there are an implementation in pseudocode.
2021-12-31 17:08:03
idea: Transform to postfix expression
2021-11-16 15:34:40
Learnt the concept of stack through this question.
2021-10-29 06:57:38
easy to solve
2021-08-21 11:04:16
Browse wikipedia for RPN. You'll get an idea!
2021-07-29 16:06:40
using stack
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.