Usuń niepotrzebne nawiasy


32

Otrzymujesz ciąg złożony ze znaków 0123456789+*(). Możesz założyć, że ciąg jest zawsze prawidłowym wyrażeniem matematycznym.

Twoim zadaniem jest usunięcie niepotrzebnych nawiasów, zakładając, że mnożenie ma wyższy priorytet niż dodawanie.

Nawiasy należy usuwać tylko wtedy, gdy nie są potrzebne strukturalnie :

  • z powodu zwielokrotnienia wyższy priorytet: 3+(4*5)=>3+4*5
  • z powodu asocjacji mnożenia lub dodawania: 3*(4*5)=>3*4*5
  • gdy są zbędne wokół wyrażenia: 3*((4+5))=>3*(4+5)

Nawiasy należy przechowywać, gdy można je uprościć ze względu na określone wartości liczbowe:

  • 1*(2+3) nie należy tego upraszczać 1*2+3
  • 0*(1+0) nie należy tego upraszczać 0*1+0

Przykłady:

(4*12)+11         ==>    4*12+11
(1+2)*3           ==>    (1+2)*3
3*(4*5)           ==>    3*4*5
((((523))))       ==>    523
(1+1)             ==>    1+1
1*(2*(3+4)*5)*6   ==>    1*2*(3+4)*5*6
1*(2+3)           ==>    1*(2+3)
0*(1+0)           ==>    0*(1+0)


(((2+92+82)*46*70*(24*62)+(94+25))+6)    ==>    (2+92+82)*46*70*24*62+94+25+6

1
Poproszę więcej przypadków testowych?
Leaky Nun

2
1*(2*(3+4)*5)*6powinien być ciekawym testem (dla którego moje rozwiązanie obecnie zawodzi).
Leaky Nun

8
Czy „niepotrzebne” jest zdefiniowane strukturalnie lub w odniesieniu do poszczególnych przypadków? Innymi słowy, czy nawiasy nie są tutaj potrzebne? (2+2)*1
Luis Mendo,

2
@LuisMendo Myślę, że sprawiedliwie jest interpretować to w
jakikolwiek

2
@anatolyg Nie sądzę, aby było to uczciwe, ponieważ podejścia do tych dwóch byłyby bardzo różne. Byłoby dobrze, gdybyśmy mieli jakieś wyjaśnienie.
Sp3000

Odpowiedzi:


15

Mathematica, 105 97 91 bajtów

-6 bajtów dzięki Romanowi !

a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}&

Zastępuje +oraz *z ~~( StringExpression) i **( NonCommutativeMultiply), odpowiednio, ocenia je, stringifies ją i zastępuje operatorów powrotem.


Co? Mathematica nie ma wbudowanego?
Erik the Outgolfer,

@EriktheGolfer Zasadniczo robi; Staram się, aby nie oceniała operatorów.
LegionMammal978,

Właśnie dlatego Mathematica jest tak reklamowana i tak droga ... ze względu na wbudowane, jak sądzę. Ale Mathematica nie zmieniła się w stosunku do innych języków, jeśli łamigłówka jest wystarczająco trudna, a jednak „inne języki” tutaj nie konkurują.
Erik the Outgolfer,

91 bajtów przy użyciu StringExpressionzamiast Doti usuwaniu " "->""klauzuli:a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}&
Roman

@Roman Thanks! Wygląda na to, że znalazłeś innego dobrego, nieprzemiennego, nieocenionego operatora, który nie łączy się z liczbami.
LegionMammal978

7

JavaScript (ES6) 163 178

Edytuj 15 bajtów zapisanych dzięki @ IsmaelMiguel

a=>eval(`s=[]${_=';for(b=0;a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')?-s.push(b[p-1]=='*'|z=='*'?x:y):y))b=a;${_}-\\d+/,x=>s[~x]))b=a`)

Mniej golfa

a=>{
  for(s=[],b='';
      a!=b;
      a=b.replace(/\(([^()]*)\)(?=(.?))/,(x,y,z,p)=>y.indexOf('+')<0?y:-s.push(b[p-1]=='*'|z=='*'?x:y)))
    b=a;
  for(b=0;
      a!=b;
      a=b.replace(/-\d+/,x=>s[~x]))
    b=a;
  return a
}

Test

f=a=>eval(`s=[]${_=';for(b=0;a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')
?-s.push(b[p-1]=='*'|z=='*'?x:y)
:y))b=a;${_}-\\d+/,x=>s[~x]))b=a`)

console.log=x=>O.textContent+=x+'\n'

test=`(4*12)+11         ==>    4*12+11
(1+2)*3           ==>    (1+2)*3
3*(4*5)           ==>    3*4*5
((((523))))       ==>    523
(1+1)             ==>    1+1
1*(2*(3+4)*5)*6   ==>    1*2*(3+4)*5*6
1*(2+3)           ==>    1*(2+3)
0*(1+0)           ==>    0*(1+0)
(((2+92+82)*46*70*(24*62)+(94+25))+6)    ==>    (2+92+82)*46*70*24*62+94+25+6`

test.split`\n`.forEach(r=>{
  var t,k,x
  [t,,k]=r.match(/\S+/g)
  x=f(t)
  console.log((x==k?'OK ':'KO ')+t+' -> '+x+(x==k?'':' expected '+k))
})
<pre id=O></pre>


Dlaczego napisałeś y.indexOf('+')zamiast y.indexOf`+`[...]? ([...] dodane, aby uniknąć potknięcia się o formatowanie)
Ismael Miguel

1
Proszę bardzo, 170 bajtów:a=>eval(`for(b=s=[]${_=';a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')<0?-s.push(b[p-1]=='*'|z=='*'?x:y):y))b=a;for(b=0${_}-\\d+/,x=>s[~x]))b=a`)
Ismael Miguel

@IsmaelMiguel to naprawdę sprytne, dzięki!
Wyciągnięta

Cieszę się, że spodobało Ci się moje proste rozwiązanie w celu zmniejszenia kodu. Chciałabym coś zrobić for(b=, =='*'i innych powtarzających się bitów. Czy to nie ~y.indexOf('+')<0to samo, co ~y.indexOf('+')? Ponieważ jedyną indexOf()zwracaną wartością, która zwraca wartość fałszowania -1, <0wydaje się zbędna. Lub, jeśli źle to zrozumiem, możesz to zrobićy.indexOf('+')>1
Ismael Miguel

@ IsmaelMiguel 1: tak, <0to bzdura pozostała z wersji bez golfa i powinna zostać usunięta. 2: myśląc jeszcze raz, formożna je zmienić, aby uwzględnić je w powtarzanej części.
Jeszcze

5

Implementacja Python3 + PEG w Pythonie , 271 bajtów

import peg
e=lambda o,m=0:o.choice and str(o)or(m and o[1][1]and"("+e(o[1])+")"or e(o[1]))if hasattr(o,"choice")else o[1]and e(o[0],1)+"".join(str(x[0])+e(x[1],1)for x in o[1])or e(o[0])
print(e(peg.compile_grammar('e=f("+"f)*f=p("*"p)*p="("e")"/[0-9]+').parse(input())))

Jakiś czas temu zrobiłem implementację PEG w Pythonie . Chyba mogę tego tutaj użyć.

Przetwarza wyrażenie na drzewo i zachowuje nawiasy tylko wtedy, gdy dziecko jest dodawaniem, a rodzic jest mnożeniem.


4

Perl, 132 bajty

Źródło 129 bajtów + 3 dla -pflagi:

#!perl -p
0while s!\(([^\(\)]+)\)!$f{++$i}=$1,"_$i"!e;s!_$i!($v=$f{$i})=~/[+]/&&($l.$r)=~/[*]/?"($v)":$v!e
while($l,$i,$r)=/(.?)_(\d+)(.?)/

Za pomocą:

echo "1*(2*(3+4)*5)*6" | perl script.pl

4

Rubinowy, 140 130 bajtów

Źródło 127 bajtów + 3 dla -pflagi:

t={}
r=?%
0while$_.gsub!(/\(([^()]+)\)/){t[r+=r]=$1;r}
0while$_.gsub!(/%+/){|m|(s=t[m])[?+]&&($'[0]==?*||$`[/\*$/])??(+s+?):s}

I bez golfa:

tokens = Hash.new
key = '%'

# convert tokens to token keys in the original string, innermost first
0 while $_.gsub!(/\(([^()]+)\)/) { # find the innermost parenthetical
  key += key # make a unique key for this token
  tokens[key] = $1
  key # replace the parenthetical with the token key in the original string
}

# uncomment to see what's going on here
# require 'pp'
# pp $_
# pp tokens

# convert token keys back to tokens, outermost first
0 while $_.gsub!(/%+/) {|key|
  str = tokens[key]
  if str['+'] and ($'[0]=='*' or $`[/\*$/]) # test if token needs parens
    '(' + str + ')'
  else
    str
  end
}
# -p flag implicity prints $_

bardzo ładna odpowiedź. co się dzieje ze 0 whileskładnią?
Jonasz

1
@Jonah In Ruby, expr while condjest równoważne z while cond; expr; end. Tutaj chcę tylko występować condwielokrotnie i tak naprawdę nie mam pętli. Zwykle pisze się to jako while cond; endlub być może, loop{ break unless cond }ale 0 while condma mniej bajtów. 0Nic nie robi; jest tam tylko dlatego, że krótka forma pętli while wymaga ciała.
ezrast

2

Siatkówka, 155 bajtów

{`\(((\d+|\((((\()|(?<-5>\))|[^()])*(?(5)^))\))(\*(\d+|\((((\()|(?<-10>\))|[^()])*(?(10)^))\)))*)\)
$1
(?<!\*)\((((\()|(?<-3>\))|[^()])*(?(3)^))\)(?!\*)
$1

Wypróbuj online!

Zweryfikuj wszystkie przypadki testowe jednocześnie.

Wyjaśnienie

Najważniejsze jest ten kod:

(((\()|(?<-3>\))|[^()])*(?(3)^)

Ten regex może pasować do dowolnego łańcucha, w którym nawiasy są zrównoważone, np . 1+(2+(3))+4Lub 2+3.

Dla ułatwienia wyjaśnienia niech to wyrażenie regularne będzie B.

Użyjmy <i >zamiast tego w nawiasach, a także pi mdla \+i \*.

Kod staje się:

{`<((\d+|<B>)(m(\d+|<B>))*)>
$1
(?<!m)<B>(?!m)
$1

Pierwsze dwie linie pasują do nawiasów, które składają się tylko z mnożenia, np. (1*2*3)Lub nawet (1*(2+3)*4). Są one zastępowane przez ich zawartość w środku.

Ostatnie dwa wiersze pasują do nawiasów, które nie są poprzedzone i po których nie następuje mnożenie. Są one zastępowane przez ich zawartość w środku.

Początkowy {`oznacza „zamień aż do idempotent”, co oznacza, że ​​zamiany są wykonywane, dopóki nie będą już pasować lub zostaną zastąpione przez siebie.

W takim przypadku zamiany są wykonywane, dopóki nie będą już pasować.


Nie działa na 1*(2*(3+4)*5)*6.
orlp

@orlp Dzięki, naprawiono.
Leaky Nun

Nie (1*(2+3)+4)*5
działa

@ Sp3000 Dzięki, naprawiono.
Leaky Nun

2

Python 3, 274 269 359 337 336 bajtów

Ta metoda zasadniczo usuwa każdą możliwą parę nawiasów i sprawdza, czy nadal ocenia to samo.

from re import *
def f(x):
    *n,=sub('\D','',x);x=sub('\d','9',x);v,i,r,l=eval(x),0,lambda d,a,s:d.replace(s,"?",a).replace(s,"",1).replace("?",s),lambda:len(findall('\(',x))
    while i<l():
        j=0
        while j<l():
            h=r(r(x,i,"("),j,")")
            try:
                if eval(h)==v:i=j=-1;x=h;break
            except:0
            j+=1
        i+=1
    return sub('9','%s',x)%tuple(n)

Uprząż testowa

print(f("(4*12)+11")=="4*12+11")
print(f("(1+2)*3") =="(1+2)*3")
print(f("3*(4*5)")=="3*4*5")
print(f("((((523))))")=="523")
print(f("(1+1)")=="1+1")
print(f("1*(2*(3+4)*5)*6")=="1*2*(3+4)*5*6")
print(f("(((2+92+82)*46*70*(24*62)+(94+25))+6)")=="(2+92+82)*46*70*24*62+94+25+6")
print(f("1*(2+3)")=="1*(2+3)")
print(f("0*(1+0)")=="0*(1+0)")

Aktualizacje

  • -1 [16-10-04] Usunięto dodatkowe miejsce
  • -22 [16-05-07] Wykorzystał relib
  • +90 [16-05-07] Zaktualizowano, aby obsługiwał nowe przypadki testowe
  • -5 [16-05-07] Usunięto parametr z llambda length ( )

1
Nie udaje się to w przypadku testowym 1*(2+3), ponieważ OP powiedział, aby nie upraszczać dla przypadków specjalnych. Dobra odpowiedź; to moje zdanie.
HyperNeutrino,

1
@AlexL. Dzięki za złapanie tego! Nie zaktualizowałem moich przypadków testowych D: Ale teraz jest to naprawione.
NielinioweOwoc

1

PHP, 358 bajtów

function a($a){static$c=[];$d=count($c);while($g=strpos($a,')',$g)){$f=$a;$e=0;for($j=$g;$j;--$j){switch($a[$j]){case')':++$e;break;case'(':--$e;if(!$e)break 2;}}$f[$g++]=$f[$j]=' ';if(eval("return $f;")==eval("return $a;"))$c[str_replace(' ', '', $f)]=1;}if(count($c)>$d){foreach($c as$k=>$v){a($k);}}return$c;}$t=a($argv[1]);krsort($t);echo key($t);

Nie imponująca długość, to właśnie otrzymuję za przyjęcie mniej niż optymalnego podejścia (i użycie mniej niż optymalnego języka).

Usuwa parę nawiasów, a następnie analizuje wynikowe wyrażenie. Jeśli wynik jest taki sam jak oryginał, dodaje go do mapy prawidłowych wyrażeń i powtarza się, dopóki nie można znaleźć nowych wyrażeń. Następnie drukuje najkrótsze prawidłowe wyrażenie.

Łamie się, gdy wynik wyrażenia staje się duży i wyświetla się rzut notacji podwójnej / wykładniczej.


1

Prolog (SWI) , 122 118 bajtów

T+S:-term_string(T,S).
I/O:-X+I,X-Y,Y+O.
E-O:-E=A+(B+C),A+B+C-O;E=A*(B*C),A*B*C-O;E=..[P,A,B],A-X,B-Y,O=..[P,X,Y];E=O.

Wypróbuj online!

Definiuje predykat, //2który usuwa nawiasy z wartości ciągu pierwszego argumentu i wysyła ciąg znaków przez drugi argument. Gdyby dane wejściowe mogły być wyrażone w kategoriach Prolog, byłoby to tylko 81 77 bajtów definiujących +/2bez konieczności zajmowania się gadatliwością term_string/2, ale wiele niepotrzebnych nawiasów po prostu nie istniałoby od tego momentu, więc byłoby to bardzo bliskie oszustwa, ponieważ wszystko, co +/2robi, to radzenie sobie ze stowarzyszeniem.

Próbowałem użyć tego =../2wszystkiego, ale wyszło ono znacznie dłużej, ponieważ trzy bajtowy operator, który działa z listami, nie jest zbyt zwięzły:

Prolog (SWI) , 124 bajty

T+S:-term_string(T,S).
I/O:-X+I,X-Y,Y+O.
X-Y:-X=..[O,A,B],(B=..[O,C,D],E=..[O,A,C],F=..[O,E,D],F-Y;A-C,B-D,Y=..[O,C,D]);X=Y.

Wypróbuj online!

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.