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.
hide comments
|
Mitch Schwartz:
2023-01-10 03:18:27
@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.
|
|
[Rampage] Blue.Mary:
2023-01-07 17:37:41
@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 |
|
|
[Rampage] Blue.Mary:
2023-01-07 17:35:42
@cyclops: The judge of this problem is broken. I can get AC on ONP problem by BF. |
|
|
Mitch Schwartz:
2013-11-20 07:43:51
Increasing the time limit a little would make the problem more golf-friendly. :) Last edit: 2013-11-20 14:30:11 |
|
|
Mitch Schwartz:
2013-10-30 00:31:47
@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. :) |
|
Mostafa 36a2:
2013-10-27 21:25:56
@Mitch Schwartz : Have some fun here :)
|
|
Robert Gerbicz:
2013-07-24 23:36:22
Down to 230 bytes. |
|
|
Mitch Schwartz:
2013-07-24 02:31:19
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.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-07-17 17:57:47
New golf record: 232B ;-)
|
| 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 |
RSS