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

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

Simes: 2022-01-13 14:24:00

@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
lazorzor: 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
ophysto: 2022-01-01 05:10:39

If you are really stuck search in google "shuting yard algorithm" there are an implementation in pseudocode.

iamrick: 2021-12-31 17:08:03

idea: Transform to postfix expression

a_cool_name: 2021-11-16 15:34:40

Learnt the concept of stack through this question.

avinshsingh: 2021-10-29 06:57:38

easy to solve

sunny77: 2021-08-21 11:04:16

Browse wikipedia for RPN. You'll get an idea!

vikasss_7663: 2021-07-29 16:06:40

using stack


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%
265 7