18
1
The Challenge
You are the owner of an amazing service called Coyote Beta, which magically answers math questions its users send to it over the internet.
But it turns out, bandwidth is expensive. You have two choices, either create a "Coyote Beta Pro" or find some way to solve this. Just recently, someone queried (x + 2)
. Couldn't the client send x+2
, and the user would see no difference?
The Task
Your task is to "minify" math expressions. Given an input expression, you must get rid of whitespace and parentheses until it gives a minimal representation of the same input. The parentheses around associative operations need not be preserved.
The only operators given here are +
, -
, *
, /
, and ^
(exponentiation), with standard mathematical associativity and precedence. The only whitespace given in the input will be actual space characters.
Sample Input/Output
Input | Output
------------|--------------
(2+x) + 3 | 2+x+3
((4+5))*x | (4+5)*x
z^(x+42) | z^(x+42)
x - ((y)+2) | x-(y+2)
(z - y) - x | z-y-x
x^(y^2) | x^y^2
x^2 / z | x^2/z
- (x + 5)+3 | -(x+5)+3
Scoring
Input/output can use any preferred method. The smallest program in bytes wins.
Exact bits
Exponentiation is right associative and also follows standard math precedence (being the highest). A valid numeric literal is /[0-9]+/
, and a valid variable literal is /[a-z]+/
. A single variable literal represents a single value even when its character length is longer than 1.
What is meant by "the parentheses around associative operations need not be preserved" is that the output should consist of an expression that results in an identical parse tree, with the exception that associative operations can be rearranged.
The idea is to create a minimal equivalent statement that results in the same parse tree. This is so that Coyote Beta can display it visually when the user makes a query. – TND – 2015-10-17T17:55:59.447
If a valid variable is
/[a-z]+/
, that means multiplication by juxtaposition likeab
is disallowed? – Joe Z. – 2015-10-17T18:01:41.713Yeah,
ab
means the single valueab
, nota*b
. This is so people can focus on the core problem instead of implementing a bunch of features in their parser. – TND – 2015-10-17T18:03:15.643Need unary plus be supported? – feersum – 2015-10-17T18:05:47.477
Or unary minus? – lirtosiast – 2015-10-17T18:09:07.083
No, that's not necessary. Unary minus is, however. – TND – 2015-10-17T18:09:13.397
1You do want
2+(3+4)
to be changed to2+3+4
, right? This does change the parse tree. – feersum – 2015-10-17T18:26:14.850Yeah, what I said in the first comment wasn't specific enough. I should say it results in an "equivalent" parse tree, where "equivalent" means "the same parse tree, plus any rearrangements to associative operations". – TND – 2015-10-17T18:30:02.490
Why not Rhenium Beta? – cole – 2015-10-17T18:31:46.643
2I take issue with the claim that
x^(y/2)=x^y/2
; exponentiation has a higher order precedence, ergo,x^y/2=(x^y)/2
. – Conor O'Brien – 2015-10-17T18:50:14.973As far as I'm aware,
x^(y/2)=x^y/2
is never stated in the problem. If it is, it's an error an should be fixed, but I can't find it. – TND – 2015-10-17T18:55:06.930Oh, was Conor's statement in response to a deleted comment? – TND – 2015-10-17T18:56:03.147
Are we permitted to simplify? – Addison Crump – 2015-10-17T20:07:40.143
What is the correct output for
a+(-b+c)
? Is ita-b+c
ora+(-b)+c
? – Egor Skriptunoff – 2015-10-17T20:23:26.573You're not permitted to simplify beyond associative operator rearrangement. – TND – 2015-10-17T20:53:20.620
The correct output for
a+(-b+c)
is eithera+(-b)+c
ora+(-b+c)
. It's interesting that that input has two minimal solutions. Anyway,a-b+c
can't be the correct answer because instead of using the unary-
, it's using the binary-
. – TND – 2015-10-17T20:56:09.233@TND -
a+(-b+c)
cannot be the correct output as the parentheses around associative operations must be removed. – Egor Skriptunoff – 2015-10-17T21:22:28.430Yes, why wouldn't the answer be
a+-b+c
? – feersum – 2015-10-17T22:22:27.450Yeah, it makes more sense to do it that way. I was worried if I said a string with two operators consecutively like that was a possible input, it would throw off the parsers of anyone who was already solving it. – TND – 2015-10-17T22:33:40.023
1Aww man, I was going to submit
Prompt X:expr(X)
in TI-BASIC but you can't simplify :( – DankMemes – 2015-10-17T23:49:33.620