Converter uma expressão em notação Panfix

19

Eu estava navegando em esolangs e me deparei com este idioma: https://github.com/catseye/Quylthulg .

Uma coisa interessante sobre essa linguagem é que ela não usa prefixo, postfix ou infix, usa as três , chamando-a de notação "panfix".

Aqui está um exemplo. Para representar infix normais 1+2em panfix, torna-se: +1+2+. Observe como o operador está antes, no meio e depois dos operandos. Outro exemplo é (1+2)*3. Isso se torna *+1+2+*3*. Observe novamente como *está em todos os três lugares em relação aos operandos +1+2+e 3.

O desafio

Como você deve ter adivinhado, sua tarefa neste desafio é converter uma expressão de infix em panfix.

Alguns esclarecimentos:

  • Você só precisa lidar com as quatro operações básicas: +-*/
  • Você não terá que lidar com as versões unárias daquelas, apenas binárias
  • Você tem que lidar com parênteses
  • Suponha as regras de precedência normais da */época +-e associe à esquerda para todas elas.
  • Os números serão números inteiros não negativos
  • Opcionalmente, você pode ter espaços na entrada e na saída

Casos de teste

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-*

Isso é código-golfe , então o código mais curto em bytes vence!

code-golf parsing conversion Maltysen
fonte

Respostas:

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)

Obras de citar todos os operadores (o que lhes dá códigos de caracteres antes *), em seguida, procurando disponível '*'ou '/'operações, '+'ou '-'operações ou ()s, e substituindo o primeiro com a sua notação panfix. Exemplo:

(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
fonte
3

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

~ 15 bytes graças 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))

No JavaScript, isso é um pouco mais difícil do que no Mathematica. Este é basicamente um analisador de precedência de operador especializado e com excesso de golfe .

Causa estouros de pilha em entradas inválidas.

Demo

Mostrar snippet de código

Ungolfed

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
fonte
S.split``deve ser [...S], embora possa realmente ajudar a combinar /\d+|./gantecipadamente e trabalhar com isso.
Neil
@ Neil Obrigado. Eu vou investigar isso.
PurkkaKoodari
2

Mathematica, 203 195 bytes

Provavelmente isso é menos que eficiente, mas parece fazer o trabalho.

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 é uma função anônima que pega uma expressão real e retorna uma string com notação panfix. O Mathematica classifica a precedência dos operadores no momento da análise, em vez do tempo da avaliação, portanto, o aninhamento deve ser automagicamente correto. Pelo menos os casos de teste funcionam como esperado.

Explicação: É fácil interpretar toda a expressão como uma árvore, assim:

árvore

Nesse estágio, os operadores (todos os nós que não são uma folha) não são mais operadores, eles foram realmente convertidos em strings como "+". Os números inteiros também são convertidos em cadeias. Em seguida, uma regra de substituição repetida converte todos os nós que possuem exatamente duas folhas no panfix parent-leaf1-parent-leaf2-parent. Após algumas iterações, a árvore reduz para uma única sequência.

A principal perda na contagem de bytes é que o Mathematica interpreta

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

E isso acontece também no momento da análise.

Golpeou um pouco, já que o padrão a_/b_também é interpretado como a_ * (b_)^(-1). Também algumas pequenas otimizações em outros lugares.

LLlAMnYP
fonte
1

Prolog, 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).

Essa é uma função (principalmente porque a gravação de um programa completo possui níveis de pesadelo no Prolog; normalmente, mesmo se você compilar um programa, ele produz um REPL quando executado), chamado p. Ele recebe as entradas do stdin e as saídas no stdout. Observe que você precisa anexar um período à entrada, o que é uma conseqüência infeliz da maneira como as rotinas de entrada do Prolog funcionam (elas usam períodos na entrada da mesma maneira que outros idiomas usam novas linhas); que pode ou não desqualificar a resposta.

Explicação

Operadores aritméticos, no Prolog, são normalmente interpretados como construtores de tuplas . No entanto, eles obedecem às mesmas regras de precedência que os operadores aritméticos reais nos quais eles se baseiam; você pode formar tuplas com notação infix +e -vincular com menos força que *e /, com precedência da esquerda para a direita dentro de um grupo. É exatamente isso que a pergunta pede; portanto, podemos ler uma tupla aninhada inteira da entrada e ela já possui a estrutura correta. Isso é o que pfaz.

Em seguida, precisamos convertê-lo em notação panfix. xconverte a entrada em uma lista panfixed de construtores e inteiros, e pode ser lido como uma frase Inglês quase diretamente: " xde Té: se Té uma tupla com construtor Oe argumentos A, Be, em seguida O, xdo A, O, xde B, O, else T". Finalmente, precisamos apenas imprimir a lista sem separadores (ou seja, usar maplistpara chamar writecada elemento da lista).

Eu usei o SWI-Prolog para testar isso, porque minha versão do GNU Prolog ainda não o maplistfoi (aparentemente foi adicionada a uma versão mais recente), mas geralmente deve ser bastante portátil entre as implementações do Prolog.

Comunidade
fonte