Сокращение математических утверждений

18

Соревнование

Вы являетесь владельцем удивительного сервиса Coyote Beta , который волшебным образом отвечает на математические вопросы, которые пользователи посылают ему через Интернет.

Но, оказывается, пропускная способность стоит дорого. У вас есть два варианта: создать Coyote Beta Pro или найти способ решить эту проблему. Совсем недавно кто-то спросил (x + 2). Не может клиент отправить x+2, и пользователь не увидит никакой разницы?

Задание

Ваша задача - «минимизировать» математические выражения. Учитывая входное выражение, вы должны избавиться от пробелов и скобок, пока оно не даст минимальное представление того же ввода. Скобки вокруг ассоциативных операций не должны быть сохранены.

Единственные операторы , приведенные здесь +, -, *, /, и ^(возведение в степень), со стандартным математическим ассоциативности и приоритете. Единственный пробел, указанный во входных данных, будет действительным пробелом.

Пример ввода / вывода

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

счет

Ввод / вывод может использовать любой предпочтительный метод. Победит самая маленькая программа в байтах.

Точные биты

Возведение в степень является правом ассоциативным и также следует стандартному математическому приоритету (будучи самым высоким). Допустимый числовой литерал есть /[0-9]+/, а допустимый переменный литерал есть /[a-z]+/. Один переменный литерал представляет одно значение, даже если длина его символа больше 1.

Что подразумевается под «круглыми скобками вокруг ассоциативных операций, которые не должны быть сохранены», так это то, что выходные данные должны состоять из выражения, которое приводит к идентичному дереву разбора, за исключением того, что ассоциативные операции могут быть переставлены.

TND
источник
Идея состоит в том, чтобы создать минимальное эквивалентное утверждение, которое приведет к тому же самому дереву разбора. Это сделано для того, чтобы Coyote Beta могла отображать его визуально, когда пользователь делает запрос.
TND
Если допустимая переменная есть /[a-z]+/, это означает, что умножение на сопоставление как abзапрещено?
Джо З.
1
Вы хотите 2+(3+4)быть изменены 2+3+4, верно? Это меняет дерево разбора.
feersum
2
Я не согласен с утверждением, что x^(y/2)=x^y/2; экспоненцирование имеет более высокий приоритет порядка, следовательно, x^y/2=(x^y)/2.
Конор О'Брайен
1
Ой человек, я собирался представить Prompt X:expr(X)в TI-BASIC, но вы не можете упростить :(
DankMemes

Ответы:

1

C #, 523 519 504 байта

Проверьте комментарии в коде, чтобы увидеть, как это работает!


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 );
            }
        }
    }
}

Примечания стороны

  1. Исправлены некоторые опечатки и переименованы некоторые переменные.
  2. Вложенный переключатель, чтобы избавиться от ненужной переменной. Также исправлена ​​ошибка, из-за которой некоторые решения становились недействительными, сообщает Anders Kaseorg .

PS: Если у вас есть подсказка или вы нашли ошибку, пожалуйста, дайте мне знать в комментариях, и я постараюсь ее исправить (я добавлю заметку об исправлении ошибки с вашим именем;))

auhmaan
источник
Хороший ответ! : D содержательные ответы здесь, как правило, лучше получить, если вы включите объяснение: P
кошка
Могу ли я сделать это в виде комментариев кода?
августа
Конечно, все, что работает c:
кошка
Тогда я сделаю это! Я также постараюсь добавить резюме где-нибудь.
августа
Кстати, добро пожаловать в программирование головоломок и Code Golf! (хотя это не ваш первый ответ)
кот
0

C ++, 284 байта

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;
}
Мишельфрансис Бустильос
источник
Это не имеет никакой логики приоритета и не проходит многие из приведенных тестов.
Андерс Касеорг