BFONP - Transform the Expression (Again!)

Have you solved ONP problem? Especially using brainf**k? This problem will give you extra points if you can solve ONP using brainf**k. Note that this problem has larger constraints.

The task is: "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 ≤ 1000]

expression [length = See: "Other Info" part]

[other expressions]

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

Other Info

Input: I deliberately not tell the input length, constraints, distribution, etc. You can guess it from judge output for my BF program (BF Cell Used) ;-) And of course I generate it randomly (But I can't tell the distribution).

This problem is using a custom judge, so you can see the detail after you get AC/WA.

The judge output format is like this: ("Code Length (Valid Command only)")"Cell Used"("BF Command executed").

Click here to see my submission result for this problem.

I have two solutions for this problem:
1) ID 9658441 (optimized): Judge output for my BF code is: (471)4320(606116310) meaning that my Valid BF commands = 471 commands and My code using 4320 BF cell and 606116310 commands executed.
2) ID 9658572 (golfed): Judge output for my BF code is: (295)4320(888371635) meaning that my Valid BF commands = 295 commands and My code using 4320 BF cell and 888371635 commands executed.

You can click (AC/WA) status for more detail.

My code running time is 0.68s (optimized solution) and 1.47s (golfed solution) and both using 1.6M of memory.

The time limit is ~14× my BF program top speed.


See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-07-15
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF
Resource:This Problem

hide comments
2023-01-10 03:18:27 Mitch Schwartz
@Blue.Mary: I'd guess maybe a C upgrade is preventing the judge from compiling (?). Tjandra's profile page https://www.spoj.com/embed/tjandra:srctjpage lists an email address, you could try contacting him. Or if that doesn't work, we could ask admins to help out. I looked on the forum to see if he shared his judge code, but I only found the BFK_AUTO judge there (https://discuss.spoj.com/t/how-to-add-problem-into-spoj/693/34), and that one apparently didn't break.

Oh and I see that Viplov Jain's AC result from October 2020 doesn't give supplemental data like everyone else's, so judging has likely been (partially) broken since then.

Last edit: 2023-01-10 03:40:06
2023-01-07 17:37:41 [Rampage] Blue.Mary
@cyclops: I think it's necessary to recheck all BF problems with his own custom judge by tjandra.

Last edit: 2023-01-07 17:37:57
2023-01-07 17:35:42 [Rampage] Blue.Mary
@cyclops: The judge of this problem is broken. I can get AC on ONP problem by BF.
2013-11-20 07:43:51 Mitch Schwartz
Increasing the time limit a little would make the problem more golf-friendly. :)

Last edit: 2013-11-20 14:30:11
2013-10-30 00:31:47 Mitch Schwartz
@Mostafa: Thanks for the thought; of course this is high on my list, but I can only work on so many things at a time. :)
2013-10-27 21:25:56 Mostafa 36a2
@Mitch Schwartz : Have some fun here :)
@Tjandra : Nice BF problem .. too much places to Optimizing ..
why not Challenge ?
@Robert : your Last submittion date was my birthday :D

Last edit: 2013-10-27 21:36:35
2013-07-24 23:36:22 Robert Gerbicz
Down to 230 bytes.
2013-07-24 02:31:19 Mitch Schwartz
Are the input expressions always in fully parenthesised form? (If so, stating the precedence of the operators is superfluous.) E.g. is a+b*c valid, or only (a+(b*c)) ? I know you just copied the description from ONP, but it is (more) important for this problem.
Ans: when I try to solve ONP using brainf**k I assumed that [expression] is formated like this:
[alphabet]={'a','b',...,'y','z'}
[operator]={'+','-','*','/','^'}
[expression]='('+{[alphabet],[expression]}+[operator]+{[alphabet],[expression]}+')'
and I got AC on first try using this assumption. So I build test case for this problem using rule above. Because I create this problem in a hurry, I just copied the description from ONP, I'll fix the problem description on August (or you can help me fix it) :-)

(Mitch): Thanks!

Last edit: 2013-07-24 20:53:09
2013-07-17 17:57:47 (Tjandra Satria Gunawan)(曾毅昆)
New golf record: 232B ;-)
Click here to see my newest submission for this problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.