Convertir una expresión a notación Panfix

19

Estaba navegando por esolangs y encontré este idioma: https://github.com/catseye/Quylthulg .

Una cosa interesante sobre este lenguaje, es que no usa prefijo, postfix o infix, usa los tres , llamándolo notación "panfix".

Aquí hay un ejemplo. Para representar infija normales 1+2en panfix, se convierte en: +1+2+. Observe cómo el operador está antes, en el medio y después de los operandos. Otro ejemplo es (1+2)*3. Esto se convierte *+1+2+*3*. Observe nuevamente cómo *está en los tres lugares con respecto a los operandos +1+2+y 3.

El reto

Como habrás adivinado, tu tarea en este desafío es convertir una expresión de infijo a panfix.

Algunas aclaraciones:

  • Solo tiene que lidiar con las cuatro operaciones básicas: +-*/
  • No tendrá que lidiar con las versiones unarias de esas, solo binarias
  • Tienes que lidiar con paréntesis
  • Asuma las reglas de precedencia normales de */entonces +-y la asociatividad izquierda para todos ellos.
  • Los números serán enteros no negativos
  • Opcionalmente, puede tener espacios tanto en la entrada como en la salida

Casos de prueba

1+2  ->  +1+2+
1+2+3  ->  ++1+2++3+
(1+2)*3  ->  *+1+2+*3*
10/2*5  ->  */10/2/*5*
(5+3)*((9+18)/4-1)  ->  *+5+3+*-/+9+18+/4/-1-*

Este es el código de golf , por lo que gana el código más corto en bytes

code-golf parsing conversion Maltysen
fuente

Respuestas:

3

JavaScript (ES6), 160 bytes

f=(s,t=s.replace(/[*-/]/g,"'$&'"),u=t.replace(/^(.*?)([*-9]+)'([*/])'([*-9]+)|([*-9]+)'([+-])'([*-9]+)|\(([*-9]+)\)/,"$1$3$2$3$4$3$6$5$6$7$6$8"))=>t==u?t:f(s,u)

Funciona citando a todos los operadores (lo que les da códigos de caracteres antes *), luego buscando disponibles '*'u '/'operaciones, '+'u '-'operaciones o ()s, y reemplazando el primero con su notación panfix. Ejemplo:

(5+3)*((9+18)/4-1)
(5'+'3)'*'((9'+'18)'/'4'-'1)
(+5+3+)'*'((9'+'18)'/'4'-'1)
+5+3+'*'((9'+'18)'/'4'-'1)
+5+3+'*'((+9+18+)'/'4'-'1)
+5+3+'*'(+9+18+'/'4'-'1)
+5+3+'*'(/+9+18+/4/'-'1)
+5+3+'*'(-/+9+18+/4/-1-)
+5+3+'*'-/+9+18+/4/-1-
*+5+3+*-/+9+18+/4/-1-*
Neil
fuente
3

JavaScript (ES6), 285 282 281 267 251 243 241 238 234 232 231 bytes

~ 15 bytes gracias a Neil .

f=(I,E=I.match(/\d+|./g),i=0)=>(J=T=>T.map?T.map(J).join``:T)((R=(H,l=(P=_=>(t=E[i++])<")"?R(0):t)(),C,F)=>{for(;(C=P())>")"&&(q=C>"*"&&C<"/")*H-1;)F=q+H?l=[C,l,C,P(),C]:F?l[3]=[C,l[3],C,R(1),C]:l=R(1,l,i--)
i-=C>")"
return l})(0))

En JavaScript, esto es un poco más difícil que en Mathematica. Esto es básicamente un analizador de precedencia de operador sobre-especializado y golf .

Provoca desbordamientos de pila en entradas no válidas.

Manifestación

Mostrar fragmento de código

Sin golf

convert = input => {
  tokens = input.match(/\d+|./g);
  i = 0;
  parse_token = () => (token = tokens[i++]) == "(" ? parse_tree(false) : token;
  parse_tree = (mul_div_mode, left = parse_token()) => {
    while ((oper = parse_token()) != ")" && !((is_plus_minus = oper == "+" || oper == "-") && mul_div_mode)) {
      if (is_plus_minus || mul_div_mode)
        left = [oper, left, oper, parse_token(), oper];
      else if (non_first)
        left[3] = [oper, left[3], oper, parse_tree(true), oper];
      else
        left = parse_tree(true, left, i--);
      non_first = true;
    }
    if (oper != ")")
      i--;
    return left;
  };
  format_tree = tree => tree.map ? tree.map(format_tree).join("") : tree;
  return format_tree(parse_tree(false));
}
PurkkaKoodari
fuente
S.split``debería serlo [...S], aunque en realidad puede ayudar hacer coincidir /\d+|./gpor adelantado y trabajar en eso en su lugar.
Neil
@Neil Gracias. Lo investigaré.
PurkkaKoodari
2

Mathematica 203 195 bytes

Es probable que esto sea menos que eficiente, pero parece hacer el trabajo.

Function[f,ReleaseHold[(Inactivate@f/._[Plus][a_,b_/;b<0]:>a~"-"~-b//Activate@*Hold)//.a_/b_:>a~"/"~b/.{a_Integer:>ToString@a,Plus:>"+",Times:>"*"}]//.a_String~b_~c_String:>b<>a<>b<>c<>b,HoldAll]

Esta es una función anónima que toma una expresión real y devuelve una cadena con notación panfix. Mathematica clasifica la precedencia de los operadores en el momento del análisis, en lugar del tiempo de evaluación, por lo que el anidamiento debe ser automáticamente correcto. Al menos los casos de prueba funcionan como se esperaba.

Explicación: Es bastante fácil interpretar toda la expresión como un árbol, así:

árbol

En esta etapa, los operadores (cada nodo que no es una hoja) ya no son operadores, en realidad se han convertido en cadenas como "+". Los enteros también se convierten en cadenas. Luego, una regla de reemplazo repetida convierte cada nodo que tiene exactamente dos hojas en el panfix parent-leaf1-parent-leaf2-parent. Después de algunas iteraciones, el árbol se reduce a una sola cadena.

La principal pérdida en el recuento de bytes es que Mathematica interpreta

5 - 4 -> 5 + (-4)
9 / 3 -> 9 * (3^(-1))

Y esto sucede también en el momento del análisis.

Golfed un poco hacia abajo, ya que el patrón a_/b_también se interpreta como a_ * (b_)^(-1). También algunas optimizaciones menores en otros lugares.

LLlAMnYP
fuente
1

Prólogo, 87 bytes

x(T)-->{T=..[O,A,B]}->[O],x(A),[O],x(B),[O];[T].
p:-read(T),x(T,L,[]),maplist(write,L).

Esta es una función (principalmente porque escribir un programa completo tiene niveles de pesadilla de repetitivo en Prolog; normalmente, incluso si compila un programa, produce un REPL cuando se ejecuta), llamado p. Toma entrada de stdin y salidas en stdout. Tenga en cuenta que debe agregar un punto a la entrada, lo cual es una desafortunada consecuencia de la forma en que funcionan las rutinas de entrada de Prolog (usan puntos en la entrada de la misma manera que otros idiomas usan líneas nuevas); eso podría o no descalificar la respuesta.

Explicación

Los operadores aritméticos, en Prolog, normalmente se interpretan como constructores de tuplas . Sin embargo, obedecen las mismas reglas de precedencia que los operadores aritméticos reales en los que se basan; se puede formar tuplas con la notación infija, y +y -se unen menos fuertemente que *y /, con preferencia tomada izquierda a derecha dentro de un grupo. Esto es exactamente lo que pide la pregunta; por lo tanto, podemos leer una tupla anidada completa de la entrada, y ya tiene la estructura correcta. Eso es lo que phace.

Luego, necesitamos convertirlo a notación panfix. xconvierte la entrada en una lista panfixed de los constructores y los números enteros, y puede ser leído como una frase Inglés casi directamente: " xde Tes: si Tes una tupla con el constructor Oy los argumentos A, By, a continuación O, xde A, O, xde B, O, de lo contrario T". Finalmente, solo tenemos que imprimir la lista sin separadores (es decir, usar maplistpara llamar writea cada elemento de la lista).

Utilicé SWI-Prolog para probar esto, porque mi versión de GNU Prolog aún no tiene maplist(aparentemente se ha agregado a una versión más nueva), pero generalmente debería ser bastante portátil entre las implementaciones de Prolog.

Comunidad
fuente