Implemente a notação Anyfix!

16

Na notação de prefixo, o operador vem antes dos argumentos, então você pode imaginar que o operador chama next()que é chamado recursivamente. Na notação infix, o operador fica entre os argumentos, para que você possa imaginá-lo simplesmente como uma árvore de análise. Na notação postfix, o operador vem após os argumentos, para que você possa imaginá-lo como baseado em pilha.

Em qualquer notação de correção, o operador pode ir a qualquer lugar * . Se um operador aparecer e não houver argumentos suficientes, o operador aguardará até que haja argumentos suficientes. Para esse desafio, você deve implementar um avaliador anyfix muito básico. (Observe que anyfix é uma linguagem recreativa que eu abandonei e que você pode brincar aqui ou conferir aqui )

Você precisará suportar os seguintes comandos:

(Aridade 1)

  • duplicado
  • negativo

(Aridade 2)

  • Adição
  • multiplicação
  • igualdade: retorna 0ou 1.

Você pode optar por usar quaisquer cinco símbolos que não sejam espaços em branco para esses comandos. Para fins demonstrativos, usarei "como duplicado, ×como multiplicação e +como adição.

Para literais, você precisa apenas suportar números inteiros não negativos, mas seu intérprete deve poder conter todos os números inteiros (dentro do intervalo de números inteiros (razoáveis) do seu idioma).

Vamos dar uma olhada em um exemplo: 10+5. O armazenamento deve se comportar como uma pilha, não como uma fila. Então, primeiro, a pilha começa em []e a lista de operadores em fila começa em []. Em seguida, 10é avaliado o literal que compõe a pilha [10]. Em seguida, o operador +é avaliado, o que requer dois argumentos. No entanto, há apenas um argumento na pilha, portanto, a lista de operadores na fila se torna ['+']. Em seguida, 5é avaliado o literal que compõe a pilha [10, 5]. Nesse ponto, o operador '+'pode ser avaliado como está, criando a pilha [15]e a fila [].

O resultado final deve ser [15]de + 10 5, 10 + 5e 10 5 +.

Vamos dar uma olhada em um exemplo mais difícil: 10+". A pilha e a fila começam como []e []. 10é avaliado primeiro, o que faz a pilha [10]. Em seguida, +é avaliado, o que não altera a pilha (porque não há argumentos suficientes) e faz a fila ['+']. Então, "é avaliado. Isso pode ser executado imediatamente, criando a pilha [10, 10]. +agora pode ser avaliado para que a pilha se torne [20]e a fila []. O resultado final é [20].

E a ordem das operações?

Vamos dar uma olhada ×+"10 10. A pilha e a fila iniciam como []:

  • ×: A pilha permanece inalterada e a fila se torna ['×'].
  • +: A pilha permanece inalterada e a fila se torna ['×', '+'].
  • ": A pilha permanece inalterada e a fila se torna ['×', '+', '"'].
  • 10: A pilha se torna [10]. Mesmo que ×deva ser o primeiro operador a ser avaliado desde que aparece primeiro, "pode ser executado imediatamente e nenhum dos operadores antes, por isso é avaliado. A pilha se torna [10, 10]e a fila ['×', '+']. ×agora pode ser avaliada, o que faz com que a pilha [100]e a fila ['+'].
  • 10: A pilha se torna [100, 10], o que permite +ser avaliado. A pilha se torna [110]e a fila [].

O resultado final é [110].

Os comandos usados ​​nessas demonstrações são consistentes com os da linguagem anyfix; no entanto, o último exemplo não funcionará devido a um erro no meu intérprete. (Isenção de responsabilidade: seus envios não serão usados ​​no intérprete anyfix)

Desafio

Selecione um conjunto de 5 caracteres que não sejam espaços em branco e que não digam dígitos e crie um interpretador anyfix de acordo com as especificações acima. Seu programa pode gerar a matriz singular ou o valor contido nela; é garantido que a pilha de valores contenha apenas um único valor no final da execução e que a fila de operadores fique vazia no final da execução.

Isso é portanto o código mais curto em bytes vence.

Casos de teste

Para esses casos de teste, duplicado é ", negativo é -, adição é +, multiplicação é ×e igualdade é =.

Input -> Output
1+2×3 -> 9
1"+"+ -> 4
2"××" -> 16
3"×+" -> 18
3"+×" -> 36
123"= -> 1 ("= always gives 1)
1+2=3 -> 1
1"=2+ -> 3
1-2-+ -> -3
-1-2+ -> 3 (hehe, the `-1` becomes `+1` at the `-` rather than making the `2` a `-1`)
+×"10 10 -> 200 (after the 10 is duplicated (duplication is delayed), 10 + 10 is performed and then 20 * 10, giving 200)

Regras

  • As brechas padrão se aplicam
  • Você pode pegar o intérprete oficial anyfix e jogar golfe, se desejar. Espere perder terrivelmente.

A entrada será dada como uma sequência e a saída como uma matriz, um único número inteiro, fora da representação da sequência. Você pode assumir que a entrada conterá apenas espaços, dígitos e os 5 caracteres que você escolher.

* na verdade não

HyperNeutrino
fonte
2
Vá para qualquer lugar * ™.
Jonathan Allan
Qual é o resultado do operador de igualdade? 0e 1?
Felix Palmen
1
@JonathanAllan veja acima; Tirei um rasgo de comando
HyperNeutrino
1
@RickHitchcock Claro.
HyperNeutrino
1
Você provavelmente deve incluir ×+"10 10nos casos de teste ou em qualquer outro exemplo que seja 1) usar um espaço em branco e 2) atrasar o uso do operador duplicado (duas coisas que perdi completamente).
Arnauld

Respostas:

5

JavaScript (ES6), 204 203 200 bytes

Retorna um número inteiro.

e=>e.replace(/\d+|\S/g,v=>{for((1/v?s:v>','?u:b)[U='unshift'](v);!!u[0]/s[0]?s[U](u.pop()>'c'?s[0]:-S()):!!b[0]/s[1]?s[U](+eval(S(o=b.pop())+(o<'$'?'==':o)+S())):0;);},s=[],u=[],b=[],S=_=>s.shift())|s

Caracteres utilizados:

  • +: Adição
  • *: multiplicação
  • #: igualdade
  • d: duplicado
  • -: negativo

Casos de teste

Formatado e comentado

e => e.replace(                     // given an expression e, for each value v matching
  /\d+|\S/g, v => {                 // a group of digits or any other non-whitespace char.
    for(                            //   this loop processes as many operators as possible
      (                             //   insert v at the beginning of the relevant stack:
        1 / v ? s : v > ',' ? u : b //     either value, unary operator or binary operator
      )[U = 'unshift'](v);          //     (s[], u[] or b[] respectively)
      !!u[0] / s[0] ?               //   if there's at least 1 value and 1 unary operator:
        s[U](                       //     unshift into s[]:
          u.pop() > 'c' ?           //       for the duplicate operator:
            s[0]                    //         a copy of the last value
          :                         //       else, for the negative operator:
            -S()                    //         the opposite of the last value
        ) :                         //     end of unshift()
      !!b[0] / s[1] ?               //   if there's at least 2 values and 1 binary operator:
        s[U](                       //     unshift into s[]:
          +eval(                    //       the result of the following expression:
            S(o = b.pop()) +        //         the last value, followed by the
            (o < '$' ? '==' : o) +  //         binary operator o with '#' replaced by '=='
            S()                     //         followed by the penultimate value
          )                         //       end of eval()
        ) : 0;                      //     end of unshift()
    );                              //   end of for()
  },                                // end of replace() callback
  s = [],                           // initialize the value stack s[]
  u = [],                           // initialize the unary operator stack u[]
  b = [],                           // initialize the binary operator stack b[]
  S = _ => s.shift()                // S = helper function to shift from s[]
) | s                               // return the final result
Arnauld
fonte
Não pense que isso funciona -1+-2. Retorna 3 em vez de -3.
9119 Ricky Hitchcock #
1
@ RickHitchcock Meu entendimento é que o segundo -deve ser aplicado -1imediatamente.
Arnauld
Eu acho que o segundo -iria com o, 2uma vez que vem após outro operador. Talvez @HyperNeutrino possa esclarecer. O operador negativo pode ser ambíguo em algumas situações.
9307 Rick
3

JavaScript (ES6), 162 152 143 150 bytes

(s,N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').match(/(- ?)*?\d+|R/g))=>+eval(`R=${N[0]>'9'?N[1]:N[0]},${s.match(/[+*=]/g).map((o,i)=>'R=R'+o+'='+N[i+1])}`)

Ligeiramente não destruído:

(s,
 N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').      //change postfix negatives to prefix,
                                             //and change "--" to "- - "
     match(/(- ?)*?\d+|R/g)                  //grab numbers and duplicates
)=>+eval(`R=${N[0] > '9' ?  N[1] : N[0]},    //handle a delayed duplicate
          ${s.match(/[+*=]/g).               //grab the operators
              map((o,i)=>'R=R'+o+'='+N[i+1]) //create a comma-separated list of assignments
           }
         `)

Explicação

Estou usando *para multiplicação e Rduplicado. Os outros operadores são os mesmos da pergunta.

N torna-se a matriz dos números (incluindo as duplicatas).

Ele replacelida com o caso em que o sinal negativo vem após o número. Por exemplo, ele mudará 1-para - 1e -1-para - -1.

Dentro do eval, s.matchcria a matriz de operadores binários. Observe que isso sempre terá menos um elemento que N.

O resultado da função é evalo mapeamento dos números e operadores.

Aqui está o que é evaled para cada um dos casos de teste:

0+2*3        R=0,R=R+=2,R=R*=3        = 6 
1+2*3        R=1,R=R+=2,R=R*=3        = 9 
1R+R+        R=1,R=R+=R,R=R+=R        = 4 
2R**R        R=2,R=R*=R,R=R*=R        = 16 
3R*+R        R=3,R=R*=R,R=R+=R        = 18 
3R+*R        R=3,R=R+=R,R=R*=R        = 36 
123R=        R=123,R=R==R             = 1 
1+2=3        R=1,R=R+=2,R=R==3        = 1 
1R=2+        R=1,R=R==R,R=R+=2        = 3 
1-2-+        R=- 1,R=R+=- 2           = -3 
-1-2+        R=1,R=R+=2               = 3 
*+R10 10     R=10,R=R*=10,R=R+=10     = 110 
+*R10 10     R=10,R=R+=10,R=R*=10     = 200 
-1+--2       R=-1,R=R+=- -2           = 1 
-1+-2        R=-1,R=R+=-2             = -3 

O operador de vírgula em uma expressão JavaScript retorna o resultado de sua última expressão; portanto, mapretorna automaticamente uma expressão utilizável.

O +sinal é necessário antes da evalalteração truepara 1e falsepara 0.

O uso Rda variável e do operador duplicado simplifica bastante as mapsubexpressões da.

Casos de teste:

Rick Hitchcock
fonte
2
Eu não acho que replacefunciona como pretendido. Isso retorna 3para -1+--2e acho 1que estaria correto (as 1alterações são assinadas três vezes antes de haver um segundo argumento para o +disponível, resultando em -1 + 2).
Felix Palmen
Boa captura, @FelixPalmen. Agora consertado.
Rick Hitchcock
2

JavaScript, 321 311 bytes

_="f=a=>(a.replace(/\\d+|./g,mq!~(b='+*=\"- '.indexOf(a))|b>2j3j4j5&&o+aw1/y?(y*=-1wcz:1/y?oywcz:hz,rql.map(z=>m(lki,1)[0],i)),hq1/s[1]?sk0,2,+eval(`y${a=='='?a+a:a}s[1]`)):cz,cqlki,0,a),s=[],l=[],e='splice'),s)z(a,i)ys[0]w)^r``:q=z=>os.unshift(k[e](j?b-";for(i of"jkoqwyz")with(_.split(i))_=join(pop());eval(_)

Experimente online!

Os cinco caracteres são os mesmos da pergunta, exceto *para multiplicação.
O script é compactado usando o RegPack . O script original é armazenado na variável _após a avaliação.


fonte
Não pense que isso funciona -1+-2. Retorna 3 em vez de -3.
Rick Hitchcock
@RickHitchcock. Por que você acredita que deveria retornar em -3vez de 3?
Eu posso estar entendendo mal o operador negativo. Geralmente, -1 + -2é -3, mas deve ser analisado como alternativa --1 + 2?
21717 Ricky Hitchcock #
1
@RickHitchcock. Tenho certeza que o resultado é 3. Antes 2mesmo de chegar à pilha, o segundo -é avaliado e, portanto, temos o 1 2 +que é de fato 3. Ah, e provavelmente você também deve editar sua resposta.
Você provavelmente está certo. Você e Arnauld obtêm a mesma resposta e pedi esclarecimentos ao OP. Você votaria novamente se eu pudesse.
9119 Ricky Hitchcock #
1

Haskell , 251 bytes

(#([],[]))
(x:r)#(o,n)|x>'9'=r#h(o++[x],n)|[(a,t)]<-lex$x:r=t#h(o,read a:n)
_#(o,n:_)=n
h=e.e
e(o:s,n:m:r)|o>'N'=e(s,g[o]n m:r)
e(o:s,n:r)|o=='D'=e(s,n:n:r)|o=='N'=e(s,-n:r)
e(o:s,n)|(p,m)<-e(s,n)=(o:p,m)
e t=t
g"a"=(+)
g"m"=(*)
g"q"=(((0^).abs).).(-)

Experimente online! Usa os seguintes caracteres: apara adição, mmultiplicação, qigualdade, Dduplicação e Nnegação. (Eu queria usar ea igualdade, mas me deparei com o problema que lexanalisa 2e3como um número.) Exemplo de uso: (#([],[])) "2a3 4m"rendimentos 20.

Laikoni
fonte
1

6502 código de máquina (C64), 697 bytes

00 C0 A2 00 86 29 86 26 86 27 86 28 86 4B 86 4C 86 CC 20 E4 FF F0 FB C9 0D F0
10 C9 20 30 F3 A6 27 9D B7 C2 20 D2 FF E6 27 D0 E7 C6 CC A9 20 20 1C EA A9 0D
20 D2 FF 20 95 C0 20 09 C1 20 95 C0 A6 26 E4 27 F0 4E BD B7 C2 E6 26 C9 20 F0
E8 C9 2D D0 09 A6 4C A9 01 9D B7 C3 D0 32 C9 22 D0 09 A6 4C A9 02 9D B7 C3 D0
25 C9 2B D0 09 A6 4C A9 81 9D B7 C3 D0 18 C9 2A D0 09 A6 4C A9 82 9D B7 C3 D0
0B C9 3D D0 0D A6 4C A9 83 9D B7 C3 E6 28 E6 4C D0 A3 4C 8A C2 A6 29 F0 6F A4
28 F0 6B CA F0 4B C6 28 A6 4B E6 4B BD B7 C3 F0 F5 30 14 AA CA D0 0B 20 7B C2
20 E1 C1 20 4D C2 D0 D9 20 5C C2 D0 D4 29 0F AA CA D0 0B 20 6D C2 20 08 C2 20
4D C2 D0 C3 CA D0 0B 20 6D C2 20 16 C2 20 4D C2 D0 B5 20 6D C2 20 F4 C1 20 4D
C2 D0 AA A4 4B B9 B7 C3 F0 02 10 AC C8 C4 4C F0 0F B9 B7 C3 F0 F6 30 F4 AA A9
00 99 B7 C3 F0 A6 60 A0 00 A6 26 E4 27 F0 15 BD B7 C2 C9 30 30 0E C9 3A 10 0A
E6 26 99 37 C4 C8 C0 05 D0 E5 C0 00 F0 08 A9 00 99 37 C4 20 39 C2 60 A2 FF E8
BD 37 C4 D0 FA A0 06 88 CA 30 0A BD 37 C4 29 0F 99 37 C4 10 F2 A9 00 99 37 C4
88 10 F8 A9 00 8D 3D C4 8D 3E C4 A2 10 A0 7B 18 B9 BD C3 90 02 09 10 4A 99 BD
C3 C8 10 F2 6E 3E C4 6E 3D C4 CA D0 01 60 A0 04 B9 38 C4 C9 08 30 05 E9 03 99
38 C4 88 10 F1 30 D2 A2 06 A9 00 9D 36 C4 CA D0 FA A2 10 A0 04 B9 38 C4 C9 05
30 05 69 02 99 38 C4 88 10 F1 A0 04 0E 3D C4 2E 3E C4 B9 38 C4 2A C9 10 29 0F
99 38 C4 88 10 F2 CA D0 D6 C0 05 F0 06 C8 B9 37 C4 F0 F6 09 30 9D 37 C4 E8 C8
C0 06 F0 05 B9 37 C4 90 F0 A9 00 9D 37 C4 60 A9 FF 45 FC 85 9F A9 FF 45 FB 85
9E E6 9E D0 02 E6 9F 60 A2 00 86 9F A5 FB C5 FD D0 07 A5 FC C5 FE D0 01 E8 86
9E 60 A5 FB 18 65 FD 85 9E A5 FC 65 FE 85 9F 60 A9 00 85 9E 85 9F A2 10 46 FC
66 FB 90 0D A5 FD 18 65 9E 85 9E A5 FE 65 9F 85 9F 06 FD 26 FE CA 10 E6 60 20
33 C1 A6 29 AD 3D C4 9D 3F C4 AD 3E C4 9D 3F C5 E6 29 60 A6 29 A5 9E 9D 3F C4
A5 9F 9D 3F C5 E6 29 60 A6 29 BD 3E C4 9D 3F C4 BD 3E C5 9D 3F C5 E6 29 60 C6
29 A6 29 BD 3F C4 85 FD BD 3F C5 85 FE C6 29 A6 29 BD 3F C4 85 FB BD 3F C5 85
FC 60 A6 29 BD 3E C5 10 13 20 7B C2 20 E1 C1 20 4D C2 A9 2D 20 D2 FF A6 29 BD
3E C5 8D 3E C4 BD 3E C4 8D 3D C4 20 8B C1 A9 37 A0 C4 4C 1E AB

Demonstração online

Uso sys49152 , digite a expressão anyfix e pressione Enter.

  • quase sem verificação de erros, espere resultados engraçados em expressões inválidas.
  • o símbolo para multiplicação é *, todos os outros, conforme sugerido.
  • o comprimento máximo de entrada é de 256 caracteres, não pode haver mais de 127 operadores na fila.
  • A rotina de entrada não manipula caracteres de controle; portanto, não digite errado;)
  • números inteiros são assinados em 16 bits, o estouro será contornado silenciosamente.
  • contagem de bytes é um pouco grande, porque este CPU ainda não sabe multiplicação e o C64 OS / ROM não lhe dá nenhum arithmetics inteiros ou conversões de / para cordas decimais.

Aqui está o código-fonte do assembler legível no estilo ca65 .

Felix Palmen
fonte
1

VB.NET (.NET 4.5) 615 576 bytes

-39 bytes graças a Felix Palmen, alterando \r\npara\n

Requer Imports System.Collections.Generic(incluído na contagem de bytes)

Dim s=New Stack(Of Long),q=New List(Of String),i=Nothing,t=0,c=0
Function A(n)
For Each c In n
If Long.TryParse(c,t)Then
i=i &"0"+t
Else
If c<>" "Then q.Add(c)
If i<>A Then s.Push(i)
i=A
End If
If i=A Then E
Next
If i<>A Then s.Push(i)
E
A=s
End Function
Sub E()
c=s.Count
If c=0Then Exit Sub
For Each op In q
If op="-"Or op="d"Or c>1Then
Select Case op
Case"*"
s.Push(s.Pop*s.Pop)
Case"+"
s.Push(s.Pop+s.Pop)
Case"="
s.Push(-(s.Pop=s.Pop))
Case"-"
s.Push(-s.Pop)
Case"d"
s.Push(s.Peek)
End Select
q.Remove(op)
E
Exit Sub
End If
Next
End Sub

O ponto de entrada é Function A, que recebe uma string como entrada e retorna a Stack(Of Long).

Símbolos:

  • Adição - +
  • Multiplicação - *
  • Igualdade - =
  • Negação - -
  • Duplicação - d

Visão geral:

A função Apega a entrada e a simboliza. Ele usa a Long?para fazer um total de execução para números inteiros de vários dígitos, o que Nothingsignifica que não estamos lendo um número inteiro no momento.

A sub E- rotina pega a pilha de números inteiros e a fila de operadores e avalia a notação anyfix. Ele se chama recursivamente até que não haja mais ações.

Declaro parâmetros globais de uma só vez para salvar bytes na declaração e na passagem de parâmetros.

O valor de retorno de Aé definido atribuindo um valor à variável correspondente A.

VB Trueé equivalente a -1, para que a operação precise negar o resultado para obter o valor correto.

Experimente online!

Brian J
fonte
sugerir para adicionar Experimente online!
Felix Palmen
btw, com o Imports, recebo apenas uma contagem de bytes 576- você poderia ter errado?
Felix Palmen
@FelixPalmen com quem contei em \r\nvez de \n, então é aí que está a discrepância.
Brian J
@FelixPalmen Adicionado TIO, obrigado por me lembrar! :) (Oh, eu não sabia que você fez isso para este post já)
Brian J