Заключите выражение в скобки

20

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

Поскольку круглые скобки находятся в кодировках 40-41, ваш код должен быть максимально коротким.


Примеры

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)

правила

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

  • Порядок операций является:
    • круглая скобка
    • Умножение, деление
    • Сложение, вычитание
  • Вы должны предпочесть идти влево-вправо
  • Входные числа всегда будут положительными целыми числами (см. Бонусы)

Бонусы

-20%, если вы справляетесь с отрицанием:

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

-5%, если вы разрешаете размещать пробелы внутри ввода:

3  + 4
(3+4)

-10%, если вы можете обрабатывать десятичные дроби во входных данных:

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

500 вознаграждений: если вам удастся написать ответ в Безымянный / Блоки

Downgoat
источник
25
«Поскольку круглые скобки находятся в кодах символов 40–41, ваш код должен быть максимально коротким». Хорошо, теперь ты просто смешон. ; P
ETHпродукция 24.12.15
3
И это проще, чем префикс (польское) обозначение, потому что?
wizzwizz4
3
Возможно дублирование .
flawr
8
@flawr Я видел это, но он сильно отличается от того факта, что этот вопрос заставляет вас выводить все выражения в скобках. Здесь вы должны принять во внимание порядок операций, который, я думаю, является существенным отличием, поскольку код не может быть тривиально изменен для этой задачи
Downgoat
3
Важный контрольный пример: 1+2+3+4(какие решения могут быть заключены в скобки ((1+2)+(3+4)))
Мартин Эндер,

Ответы:

2

Python, 153 * 0,9 = 137,7 байта

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

Эта программа обрабатывает десятичный ввод.

Вторая строка начинается с пробела, вторая начинается с табуляции, третья - с двумя табуляциями, а третья - с пробелом. Это спасло один байт. Вот hexdump ( 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.

Вот программа, которую я использовал для тестирования: (Сохраните программу выше как 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!"

Убедитесь, что ваш терминал использует \033[38;5;<COL>mescape-код для цветов.

Loovjo
источник
* четвертый с пробелом?
Element118 28.12.15
1
Эта программа не делает prefer to go left-right. Попробуйте контрольный пример 3 в ОП, ваш результат не верен. Это может быть реальной проблемой, например, с целочисленной арифметикой ((2*(3/4))+3):! =(((2*3)/4)+3)
edc65
1
@ user12365 Не используется целочисленная арифметика (например, в C или C ++) 3/4 == 0, поэтому ((2 * (3/4)) + 3) равно 3, а (((2 * 3) / 4) + 3) 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]

Поскольку два других ответа в настоящее время неверны, я опубликую свой. Это изменение выражения синтаксического анализа , который я использовал здесь и здесь , а где - то в другом месте. Ищите там более подробные объяснения алгоритма.

Это довольно громоздко, но это должно работать.

Тестовый фрагмент

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
источник
1

Python, 241 * 0,8 * 0,95 * 0,9 = 164,84 символов

Я использую библиотеку ast (Абстрактные Синтаксические Деревья) и диктант замены доморощенной строки. Замена струны стоит дорого, но бонус помогает удерживать счет несколько низким. Возможно (часть замены последовательности) может быть гольфом далее.

Обратите внимание, что это решение добавляет дополнительные скобки вокруг каждого числа, но я думаю, что это в духе вопроса

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

Тестирование:

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)

Вывод набора тестов:

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
источник
Отсутствует import astв вашем коде
edc65
И это не правильный способ рассчитать процентный бонус. Если вы получаете скидку 50%, а в дополнение к этому еще 50%, вы не платите 0. Ваша оценка должна быть 157,32 (что-то большее после добавления строки импорта). Это хороший результат - я буду поддерживать, если вы исправите
ситуацию
Хорошая точка зрения. Добавлен импорт. 241 символов сейчас. Не уверен, как рассчитать бонус, хотя. Если я правильно понял ваш комментарий правильно, порядок , в котором бонусная вычитают вопросы ...
agtoever
Бонус не вычитается (это умножение) и порядок не имеет значения. 241 * (1-20%) * (1-5%) * (1-10%) => 241 * 0,8 * 0,95 * 0,9 => 164,84
edc65
@ edc65 Ах. Правильно. Не думал прямо. Благодарю.
agtoever