Nawiasuj wyrażenie

20

Ostatnio piszę nowy język , aby uniknąć konieczności porządkowania operacji , po prostu odpowiednio nawiasuję każde wyrażenie, aby całkowicie tego uniknąć.

Ponieważ nawiasy znajdują się w kodach znaków 40-41, kod będzie musiał być jak najkrótszy.


Przykłady

1+2*3
(1+(2*3))

2*(3+4)
(2*(3+4))

2*3/4+3
(((2*3)/4)+3)

342*32/8
((342*32)/8)

Zasady

Jedyne operacje, które musisz obsłużyć to: *(mnożenie), /(dzielenie), +(dodawanie) i -(odejmowanie).

  • Kolejność operacji jest:
    • Nawias
    • Mnożenie, dzielenie
    • Dodawanie, odejmowanie
  • Powinieneś iść w lewo-prawo
  • Liczby wejściowe zawsze będą dodatnimi liczbami całkowitymi (patrz bonusy)

Bonusy

-20%, jeśli poradzisz sobie z negacją:

3+-5
(3+(-5))

-5%, jeśli pozwalasz na umieszczenie spacji w danych wejściowych:

3  + 4
(3+4)

-10%, jeśli potrafisz obsłużyć ułamki dziesiętne w danych wejściowych:

1+.12
(1+.12)
1+0.21/3
(1+(0.21/3))

500 nagród: jeśli uda ci się napisać odpowiedź w Unnamed / Blocks

Downgoat
źródło
25
„Ponieważ w nawiasach znajdują się kody znaków 40–41, kod musi być możliwie jak najkrótszy”. OK, teraz jesteś po prostu śmieszny. ; P
ETHproductions
3
A to jest łatwiejsze niż notacja przedrostkowa (polska), ponieważ?
wizzwizz4
3
Możliwy duplikat .
flawr
8
@ flawr Widziałem to, ale jest zupełnie inaczej w tym, że to pytanie wyprowadziło wszystkie sposoby nawiasowania wyrażenia. Tutaj musisz wziąć pod uwagę kolejność operacji, co moim zdaniem jest znaczącą różnicą, ponieważ nie można w prosty sposób zmodyfikować kodu dla tego wyzwania
Downgoat
3
Ważny przypadek testowy: 1+2+3+4(które niektóre rozwiązania mogą być w nawiasach jako ((1+2)+(3+4)))
Martin Ender

Odpowiedzi:

2

Python, 153 * 0,9 = 137,7 bajtów

def p(e):
 for o in"+-*/":
    for i,c in enumerate(e):
        if(c==o)*(0==sum([(d=="(")-(d==")")for d in e[:i]])):return"("+p(e[:i])+o+p(e[i+1:])+")"
 return e

Ten program obsługuje wprowadzanie dziesiętne.

Druga linia zaczyna się spacją, druga zaczyna się od tabulacji, trzecia od dwóch tabulatorów, a trzecia spacją. To oszczędzało jeden bajt. Oto zrzut heksadecymalny ( xxdpp):

0000000: 6465 6620 7028 6529 3a0a 2066 6f72 206f  def p(e):. for o
0000010: 2069 6e22 2b2d 2a2f 223a 0a09 666f 7220   in"+-*/":..for 
0000020: 692c 6320 696e 2065 6e75 6d65 7261 7465  i,c in enumerate
0000030: 2865 293a 0a09 0969 6628 633d 3d6f 292a  (e):...if(c==o)*
0000040: 2830 3d3d 7375 6d28 5b28 643d 3d22 2822  (0==sum([(d=="("
0000050: 292d 2864 3d3d 2229 2229 666f 7220 6420  )-(d==")")for d 
0000060: 696e 2065 5b3a 695d 5d29 293a 7265 7475  in e[:i]])):retu
0000070: 726e 2228 222b 7028 655b 3a69 5d29 2b6f  rn"("+p(e[:i])+o
0000080: 2b70 2865 5b69 2b31 3a5d 292b 2229 220a  +p(e[i+1:])+")".
0000090: 2072 6574 7572 6e20 650a                  return e.

Oto program, którego użyłem do testowania: (Zapisz program powyżej jako paren.py)

import paren

cases = {
        "2+3*4": "(2+(3*4))", 
        "(2+3)*4": "((2+3)*4)", 
        "1+2+3+4": "(1+(2+(3+4)))", 
        "3/2+5": "((3/2)+5)", 
        "1+2-3": "(1+(2-3))", 
        "2-1+2": "((2-1)+2)",
        "3+-5": "(3+(-5))",
        "1+.12": "(1+.12)",
        "1+0.21/3": "(1+(0.21/3))",
}


for num, case in enumerate(cases):
    print "\n\n\033[1m\033[38;5;14mCase #%d: %s" % (num + 1, case)
    result = paren.p(case)
    print "\033[38;5;4mParenthesize returned: %s" % (result)
    solution = cases[case]
    if result == solution:
        print "\033[38;5;76mCorrect!"
    else:
        print "\033[38;5;9mNot correct!"

Upewnij się, że twój terminal używa \033[38;5;<COL>mkodu ucieczki dla kolorów.

Loovjo
źródło
* czwarty ze spacją?
Element118
1
Ten program nie prefer to go left-right. Wypróbuj przypadek testowy 3 w OP, twój wynik jest nieprawidłowy. Może to być prawdziwy problem na przykład z arytmetyką liczb całkowitych ((2*(3/4))+3)(((2*3)/4)+3)
:!
1
@ user12365 Nieużywanie arytmetyki liczb całkowitych (na przykład w C lub C ++) 3/4 == 0, więc ((2 * (3/4)) + 3) wynosi 3, podczas gdy (((2 * 3) / 4) + 3) jest 4
edc65
3

JavaScript (ES6) 179 (263-20% -5% -10%)

(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]

Ponieważ pozostałe dwie odpowiedzi są obecnie błędne, opublikuję moje. Jest to odmiana parsera wyrażeń, którego użyłem tu i tu i gdzie indziej. Poszukaj bardziej szczegółowych wyjaśnień algorytmu.

Jest dość nieporęczny, ale powinien działać.

Testowy fragment kodu

f=(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]

// More readable
x=(x,W=[],Q=['('],z=1,w=v='',
  h=p=>'*/+-))('.indexOf(p)|1,
  C=n=>{
    for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;
    z&&Q.push(q,n)
  }
)=>(
  (x+')')
  .replace(/[\d.]+|\S/g,t=> 
       t>'('    
       ?t>')'
       ?~h(t)
       ?z
       ?(w+='('+t,v+=')')
       :C(t,z=1)
       :W=[w+t+v,...W,z=w=v=''] // overfill W to save 2 chars ()
       :C(t,z=0)
       :z=Q.push(t)
  ),
  W[0]
)

console.log=(...x)=>O.textContent+=x.join` `+'\n'

// TEST
;[
  ['1+2*3','(1+(2*3))'],['2*(3+4)','(2*(3+4))'],['2*3/4+3','(((2*3)/4)+3)'],['342*32/8','((342*32)/8)'],
  ['3+-5','(3+(-5))'],['-3+-4*7','((-3)+((-4)*7))'], // bonus 20%
  ['3  + 4','(3+4)'], // bonus 5%
  ['1+.12','(1+.12)'],['1+0.21/3','(1+(0.21/3))'] // bonus 10%
].forEach(t=>{var k=t[1],i=t[0],r=f(i); console.log(i+' : '+r+(r==k? ' OK':' Fail expecting '+k))})
<pre id=O></pre>

edc65
źródło
1

Python, 241 * 0,8 * 0,95 * 0,9 = 164,84 znaków

Korzystam z biblioteki ast (Abstract Syntax Trees) i dyktora zastępującego ciąg znaków homebrew. Wymiana łańcucha kosztuje dużo, ale premia pomaga utrzymać wynik na nieco niskim poziomie. Może (część zamienna) można dalej grać w golfa.

Zauważ, że to rozwiązanie dodaje dodatkowy zestaw nawiasów wokół każdej liczby, ale myślę, że jest to zgodne z duchem pytania

import ast;def p(e):
 r,s={"Module([":"",")])":"","Expr(":"","BinOp":"","Num":"",", Add(), ":"+",", Sub(), ":"-",", Div(), ":"/",", Mult(), ":"*"},ast.dump(ast.parse(e),annotate_fields=False)
 for f,t in r.iteritems():s=s.replace(f,t)
 return s

Zestaw testowy:

cases = {
    "2+3*4", 
    "(2+3)*4", 
    "1+2+3+4", 
    "3/2+5", 
    "1+2-3", 
    "2-1+2",
    "3+-5",
    "1+.12",
    "1+0.21/3"
}

for num,case in enumerate(cases):
    result = p(case)
    print "Case {}: {:<16} evaluates to: {}".format(num+1,case,result)

Dane wyjściowe zestawu testowego:

Case 1: 3+-5             evaluates to: ((3)+(-5))
Case 2: 3/2+5            evaluates to: (((3)/(2))+(5))
Case 3: 2+3*4            evaluates to: ((2)+((3)*(4)))
Case 4: 1+2+3+4          evaluates to: ((((1)+(2))+(3))+(4))
Case 5: 1+0.21/3         evaluates to: ((1)+((0.21)/(3)))
Case 6: (2+3)*4          evaluates to: (((2)+(3))*(4))
Case 7: 2-1+2            evaluates to: (((2)-(1))+(2))
Case 8: 1+.12            evaluates to: ((1)+(0.12))
Case 9: 1+2-3            evaluates to: (((1)+(2))-(3))
agtoever
źródło
Brakuje import asttwojego kodu
edc65
I to nie jest właściwy sposób, aby przeliczyć procent premii. Jeśli otrzymasz rabat w wysokości 50%, a dodatkowo w wysokości 50%, nie płacisz 0. Twój wynik powinien wynosić 157,32 (coś więcej po dodaniu linii importu). To dobry wynik - głosuję za poprawieniem
edc65
Słuszna uwaga. Dodano import. 241 znaków teraz. Nie wiesz jednak, jak obliczyć premię. Jeśli dobrze rozumiem twój komentarz, kolejność odejmowania premii ma znaczenie ...
2015
Bonus nie jest odejmowany (jest to mnożenie), a kolejność nie ma znaczenia. 241 * (1-20%) * (1-5%) * (1-10%) => 241 * 0,8 * 0,95 * 0,9 => 164,84
edc65
@ edc65 Ah. Dobrze. Nie myślałem prosto. Dzięki.
agtoever