BRACKETS - Fully Parenthesized Expression

Clyde has written a program that can evaluate arithmetic expressions. There is just one problem - the expressions must be fully parenthesized!

Help Clyde by making sure all of his expressions are fully parenthesized - he's willing to reward you.


The first line of input contains a single integer n (1 ≤ n ≤ 1000) that indicates the amount of test cases.
On the next n lines will be a string s representing the expression. S will always contain a valid expression and will be strictly less than 256 characters in length.

The operators used in s are */% of high precedence and +- of low precedence. All operators are binary. All input strings will consist of only characters in the set "0123456789+-*/%()" (no whitespace).


Your program should output n lines, each containing the fully parenthesized expression s.

A fully parenthesized expression is one where each operator is one where all operands are surrounded by either one parenthesis and one operator, or two parentheses. There should not be any extra parentheses.

The outputted expression does not need to be a solvable expression.

Fully Parenthesized Not Fully Parenthesized
(42) 42
(1+(2*3)) 1+(2*3)
(1+((61%(3+6))*7)) 1+61%(3+6)*7





Your score is the length of your source code.

Added by:Jargon
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6 SCM qobi
Resource:Own problem

hide comments
2012-04-10 20:36:20 Jander
@Jargon - can you tell me why submission 6824116 fails ?

Edit: Ah, found it :-) I've also found some more missing tests in hunting out the failing test.

Last edit: 2012-04-11 18:37:25
2012-04-02 01:47:42 Piotr KÄ…kol
Jargon, can't You go here:
and in section "Rejudge submission range" tick option "Refresh cached info about test sequence" and click "Start rejudge"?

Last edit: 2012-04-02 01:50:52
2012-03-31 17:08:28 Jargon
Test cases have now been updated per Jander's suggestions, though I can't rejudge submissions to this contest. (On the main judge, AC's dropped from 77 to 54; thank you for catching that!)

Edit: d'oh. I've rejudged; AC have dropped from 86 to 57.

Last edit: 2012-04-06 05:08:01
2012-03-11 19:17:54 Jander
Jargon - I'd suggest you add tests similar to "1*2+3*4", "1*(2+3)*4*5" and "(0)" and then rejudge. My previous top spot codes failed on these inputs, but got AC.

Last edit: 2012-03-15 18:53:24
2011-02-19 18:22:08 Piotr KÄ…kol
Thank You for being wakeful. :-)
2011-02-13 17:26:18 Jargon
Yes I did; I've unticked that option since evidently you'd like to keep your previous solution? =P.
2011-02-11 20:48:29 Piotr KÄ…kol
It seems that author ticked option "Merge all languages in ranklist" in the task editboard.
2011-02-11 15:56:16 HWK
Oh, my solution in Python is gone after I've published a shorter one in Perl.
What's wrong with the list of best solutions?
2010-06-11 02:20:00 Jargon
numerix, I don't get points from them anyway.

Edit: nevermind, I do. The first day this was put up, I didn't. (That could be the delay in update of points, though.)

I've made all of my submissions private, removing them from the rankings and forfeiting the points. Sorry about that.

Last edit: 2010-06-11 02:24:33
2010-06-07 16:18:10 numerix
Jargon, do you think it's okay that you submit solutions as problemsetter of this problem, AFTER you have seen others solutions that are shorter than your initial submission?
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.