Paréntesis de una expresión

20

Recientemente he estado escribiendo un nuevo lenguaje , para evitar la necesidad de manejar el orden de las operaciones , simplemente paréntesis cada expresión correctamente para evitar esto por completo.

Debido a que los paréntesis se encuentran en los códigos de caracteres 40-41, su código deberá ser lo más breve posible.


Ejemplos

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)

Reglas

Las únicas operaciones que necesitará manejar son: *(multiplicación), /(división), +(suma) y -(resta).

  • El orden de las operaciones es:
    • Paréntesis
    • Multiplicación, División
    • Adición, resta
  • Debes preferir ir de izquierda a derecha
  • Los números de entrada siempre serán enteros positivos (ver bonificaciones)

Bonos

-20% si manejas la negación:

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

-5% si permite que se coloquen espacios dentro de la entrada:

3  + 4
(3+4)

-10% si puede manejar decimales en la entrada:

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

Recompensa 500: si logras escribir una respuesta en Sin nombre / Bloques

Downgoat
fuente
25
"Debido a que los paréntesis están en los códigos de caracteres 40-41, su código deberá ser lo más breve posible". Bien, ahora solo estás siendo ridícula. ; P
ETHproductions
3
Y esto es más fácil que la notación de prefijo (polaco) porque?
wizzwizz4
3
Posible duplicado .
flawr
8
@flawr Lo vi, pero es muy diferente en el hecho de que esa pregunta te hace salir de todas las formas entre paréntesis de una expresión. Aquí debe tener en cuenta el orden de las operaciones, lo que creo que es una diferencia significativa, ya que el código no puede modificarse trivialmente para este desafío
Downgoat
3
Caso de prueba importante: 1+2+3+4(qué ciertas soluciones podrían estar entre paréntesis ((1+2)+(3+4)))
Martin Ender

Respuestas:

2

Python, 153 * 0.9 = 137.7 bytes

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

Este programa maneja la entrada decimal.

La segunda línea comienza con un espacio, la segunda comienza con una pestaña, la tercera con dos pestañas y la tercera con un espacio. Esto salvó un byte. Aquí hay un 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.

Aquí hay un programa que usé para probar: (Guarde el programa anterior como 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!"

Asegúrese de que su terminal use el \033[38;5;<COL>mcódigo de escape para los colores.

Loovjo
fuente
* cuarto con un espacio?
Element118
1
Este programa no lo hace prefer to go left-right. Pruebe el caso de prueba 3 en el OP, su resultado no es correcto. Esto puede ser un problema real , por ejemplo, con la aritmética de enteros ((2*(3/4))+3)(((2*3)/4)+3)
:!
1
@ user12365 Sin usar aritmética de enteros (en C o C ++ por ejemplo) 3/4 == 0, entonces ((2 * (3/4)) + 3) es 3, mientras que (((2 * 3) / 4) + 3) es 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]

Como las otras dos respuestas son actualmente incorrectas, publicaré la mía. Es una variación del analizador de expresiones que utilicé aquí y aquí y en otro lugar. Mire allí para obtener explicaciones de algoritmos más detalladas.

Es bastante voluminoso pero debería funcionar.

Fragmento de prueba

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
fuente
1

Python, 241 * 0.8 * 0.95 * 0.9 = 164.84 caracteres

Estoy usando la biblioteca ast (Árboles de sintaxis abstracta) y un dict de reemplazo de cadena homebrew. El reemplazo de la cuerda cuesta mucho, pero la bonificación ayuda a mantener el puntaje algo bajo. Tal vez (la parte de reemplazo de la cuerda) se pueda jugar más.

Tenga en cuenta que esta solución agrega un conjunto adicional de paréntesis alrededor de cada número, pero creo que eso está dentro del espíritu de la pregunta

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

Banco de pruebas:

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)

Salida del conjunto de pruebas:

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))
en cualquier lugar
fuente
Falta import asten su código
edc65
Y esa no es la forma correcta de acumular un porcentaje de bonificación. Si obtiene un descuento del 50% y, además, otro del 50%, no está pagando 0. Su puntaje debe ser 157.32 (algo más después de agregar la línea de importación). Ese es un buen puntaje. Voy a votar si haces el arreglo
Edc65
Buen punto. Se agregó la importación. 241 caracteres ahora. Sin embargo, no estoy seguro de cómo calcular el bono. Si entiendo tu comentario correctamente, el orden en que el bono se resta asuntos ...
agtoever
La bonificación no se resta (es una multiplicación) y el orden no importa. 241 * (1-20%) * (1-5%) * (1-10%) => 241 * 0.8 * 0.95 * 0.9 => 164.84
edc65
@ edc65 Ah. Correcto. No estaba pensando con claridad. Gracias.
agtoever