18
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – TND Oct 17 '15 at 17:55
  • \$\begingroup\$ If a valid variable is /[a-z]+/, that means multiplication by juxtaposition like ab is disallowed? \$\endgroup\$ – Joe Z. Oct 17 '15 at 18:01
  • 1
    \$\begingroup\$ You do want 2+(3+4) to be changed to 2+3+4, right? This does change the parse tree. \$\endgroup\$ – feersum Oct 17 '15 at 18:26
  • 2
    \$\begingroup\$ I 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. \$\endgroup\$ – Conor O'Brien Oct 17 '15 at 18:50
  • 1
    \$\begingroup\$ Aww man, I was going to submit Prompt X:expr(X) in TI-BASIC but you can't simplify :( \$\endgroup\$ – DankMemes Oct 17 '15 at 23:49
1
\$\begingroup\$

C#, 523 519 504 bytes

Check the in-code comments to see how it works!


Golfed

using System;using System.Collections.Generic;namespace n{class p{static void Main(string[]a){foreach(String s in a){String r=s.Replace(" ","");List<int>l=new List<int>();for(int i=0;i<r.Length;i++){if(r[i]=='('){l.Add(i);continue;}if(r[i]==')'){switch(r[Math.Max(l[l.Count-1]-1,0)]){case'+':case'(':switch(r[Math.Min(i+1,r.Length-1)]){case'+':case'-':case')':r=r.Remove(Math.Max(l[l.Count-1],0),1);r=r.Remove(Math.Min(i,r.Length)-1,1);i-=2;break;}break;}l.RemoveAt(l.Count-1);}}Console.WriteLine(r);}}}}

Ungolfed

using System;
using System.Collections.Generic;

namespace n {
    class p {
        static void Main( string[] a ) {
            // Loop every String given for the program
            foreach (String s in a) {
                // Get rid of the spaces
                String r = s.Replace( " ", "" );

                // A little helper that will have the indexes of the '('
                List<int> l = new List<int>();

                // Begin the optimizatio process
                for (int i = 0; i < r.Length; i++) {
                    // If char is an '(', add the index to the helper list and continue
                    if (r[ i ] == '(') {
                        l.Add( i );
                        continue;
                    }

                    // If the char is an ')', validate the group
                    if (r[ i ] == ')') {
                        // If the char before the last '(' is an '+' or '(' ...
                        switch (r[ Math.Max( l[ l.Count - 1 ] - 1, 0 ) ]) {
                            case '+':
                            case '(':
                                // ... and the char after the ')' we're checking now is an '+', '-' or ')' ...
                                switch (r[ Math.Min( i + 1, r.Length - 1 ) ]) {
                                    case '+':
                                    case '-':
                                    case ')':
                                        // Remove the '()' since they're most likely desnecessary.
                                        r = r.Remove( Math.Max( l[ l.Count - 1 ], 0 ), 1 );
                                        r = r.Remove( Math.Min( i, r.Length ) - 1, 1 );

                                        // Go two steps back in the loop since we removed 2 chars from the String,
                                        //   otherwise we would miss some invalid inputs
                                        i -= 2;
                                        break;
                                }

                                break;
                        }

                        // Remove the last inserted index of '(' from the list,
                        //   since we matched an ')' for it.
                        l.RemoveAt( l.Count - 1 );
                    }
                }

                // Print the result
                Console.WriteLine( r );
            }
        }
    }
}

Side notes

  1. Fixed some typos and renamed some vars.
  2. Nested an switch to get rid of an unnecessary variable. Also, fixed a bug that would render some solutions invalid, reported by Anders Kaseorg.

P.S.: If you have a tip or found a bug, please let me know in the comments and I'll try to fix it ( I'll then add a note about the bug fix with your name ;) )

\$\endgroup\$
  • \$\begingroup\$ Nice answer! :D substantial answers here are generally better recieved if you include an explanation :P \$\endgroup\$ – cat Apr 15 '16 at 14:04
  • \$\begingroup\$ Can I do it in the form of code comments? \$\endgroup\$ – auhmaan Apr 15 '16 at 14:24
  • \$\begingroup\$ Sure, whatever works c: \$\endgroup\$ – cat Apr 15 '16 at 14:25
  • \$\begingroup\$ Then I'll do that! I'll also try to add a summary somewhere. \$\endgroup\$ – auhmaan Apr 15 '16 at 14:28
  • \$\begingroup\$ Welcome to Programming Puzzles and Code Golf, by the way! (even though it's not your first answer) \$\endgroup\$ – cat Apr 15 '16 at 14:30
0
\$\begingroup\$

C++, 284 bytes

Golfed

#include<iostream>
#include<algorithm>
int main(){std::string e;std::getline(std::cin,e);e.erase(std::remove_if(e.begin(),e.end(),isspace),e.end());for(int x=0;x<e.length();x++){if(e[x]=='('&&e[x+1]=='('){e.erase(x,1);}if(e[x]==')'&&e[x+1]==')'){e.erase(x,1);}}std::cout<<e;return 0;}

Ungolfed

#include<iostream>
#include<algorithm>

int main()
{
    std::string e;
    std::getline(std::cin, e);
    e.erase(std::remove_if(e.begin(), e.end(), isspace), e.end());
    for(int x = 0; x < e.length(); x++) {
        if (e[x] == '(' && e[x+1] == '('){
            e.erase(x, 1);
        }
        if (e[x] == ')' && e[x+1] == ')'){
            e.erase(x, 1);
        }
    }
    std::cout<<e;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ This doesn’t have any precedence logic and fails many of the given test cases. \$\endgroup\$ – Anders Kaseorg Apr 15 '16 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.