Quylthulg é uma linguagem de Chris Pressey que tenta resolver o problema da notação infix usando o que chama de panfix :
como o postfix, o panfix não exige a implantação de artifícios arcanos, como parênteses, para substituir uma precedência padrão do operador. Ao mesmo tempo, o panfix permite que os termos sejam especificados na mesma ordem e maneira que o infixo, uma notação inquestionavelmente natural e intuitiva para aqueles que se acostumaram a ele.
Como você obtém a conveniência da notação infix, juntamente com a ambiguidade de prefixo ou postfix? Use todos os três, é claro!
=y=+*3*x*+1+=
Mais formalmente, vamos +
ser um operador e a
e b
ser expressões. Então (a+b)
é uma expressão de infixo válida (entre parênteses), a representação panfix dessa expressão é +a+b+
, onde a justaposição representa concatenação.
Seu objetivo é pegar uma string panfix e convertê-la em infix totalmente entre parênteses:
(y=((3*x)+1))
Para simplificar, faremos as seguintes alterações:
- Os operadores podem consistir apenas em dois caracteres únicos (você pode escolher qualquer um, mas aqui vou usar
*
e+
). - Existe apenas um literal, que consiste em outro caractere distinto (você pode escolher qualquer, mas aqui vou usar
_
). - A entrada será uma expressão panfix bem formada.
Por complexidade , faremos as seguintes alterações:
- Os operadores podem consistir em qualquer número positivo de caracteres, não apenas um.
Isso torna o desafio mais complicado, porque você não pode determinar necessariamente como uma determinada substring de caracteres do operador é particionada sem observar o restante da string.
Aqui está uma implementação de referência para o desafio, cortesia de @ user202729.
Casos de teste
format: input -> output
+*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -> ((_**_)*_)
+_+_+ -> (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -> ((_*(_*(_*_)))*_)
Eu usei esse programa para gerar strings infix para esse desafio (a conversão para panfix era trivial, mas a reversão não é).
**_**_**_*_****_*
. As respostas que eu testei falharam nesta.(_ + _)
?Respostas:
Prolog (SWI) ,
194163 bytesEconomizou 31 bytes usando esta dica de 0 ' !
O operador
^
pega como argumento esquerdo uma string contendo uma expressão panfix e define seu argumento direito como uma string contendo a expressão infix entre parênteses correspondente. Ele usax
como literal no lugar de_
.Experimente online!
Explicação
Como o Prolog é uma linguagem declarativa, basta descrever a relação entre uma panfix e uma expressão entre parênteses.
A explicação usa esta versão um pouco não destruída:
Nossa principal produção é
parenthesize
, que recebe uma expressão panfixX
como uma string e envia a expressão infix entre parênteses correspondenteP
como uma string. Ele usastring_chars
para converter a string de entrada em uma lista de caracteres e simplesmente a passa paraexpr
.expr
recebe uma lista de caracteresL
, analisa a primeira expressão panfix encontradaL
e envia o equivalente entre parêntesesX
e o restante da lista de caracteresR
. Existem dois tipos possíveis de expressões:L
éx
, então a expressão éx
e o restante é tudo após ox
.O
(vejaoper
abaixo); analisar uma expressãoY
; analisarO
novamente; analisar outra expressãoZ
; e analiseO
uma terceira vez. O restante é tudo após a terceira instância deO
. A expressão é o resultado da junçãoY
,O
eZ
, entre parênteses, em uma sequência.oper
leva em uma lista de caracteres, onde está o primeiro caractereC
e o restanteT
; ele analisa um operador (ou seja, uma execução de um ou mais caracteres do operador) e envia o operadorO
e o restante da lista de caracteresR
. Para formar um operador, o personagemC
deve ser algo diferente dex
; tambémP
deve ser analisável deT
, com o restanteR
; nesse caso,O
é a concatenação deC
eP
; ou,O
é o caractere únicoC
; neste caso,R
é justoT
.Um exemplo trabalhado
Vamos dar a entrada
+*+x+x++*x+*
para um exemplo.+*+x+x++*x+*
. Como não começax
, analisamos um operador desde o início.oper
analisará o maior operador possível, por isso tentamos+*+
.x+x++*x+*
. Isso tem que serx
.+*+
de+x++*x+*
. No entanto, isso falha .+*
.+x+x++*x+*
. Como não começax
, precisamos analisar um operador.+
.x+x++*x+*
. Isso tem que serx
.+
novamente a partir de+x++*x+*
.x++*x+*
. Isso tem que serx
.+
novamente a partir de++*x+*
.(x+x)
.+*
novamente a partir de+*x+*
.x+*
. Isso tem que serx
.+*
novamente a partir de+*
.((x+x)+*x)
.Como não restam mais caracteres, traduzimos a expressão com sucesso.
fonte
Perl,
7860585750 bytesInclui
+1
parap
Usa
1
para+
e2
para*
(ou de fato qualquer dígito funciona para qualquer operador)Para testes convenientes versus os exemplos fornecidos, você pode usar isso, que faz as traduções e a remoção de espaço para você:
fonte
Limpo ,
200192189 bytesExperimente online!
Define a função
f
, recebendoString
e retornando um singleton[String]
com o resultado dentro.Algumas coisas legais:
_
fonte
Retina 0.8.2 , 138 bytes
Experimente online! O link inclui os casos de teste mais rápidos. Explicação: O mecanismo regex usa backtracking para dividir a sequência em tokens que são então pressionados ou ativados no
i
grupo de balanceamento. Sempre há uma execução de pelo menos um operador pressionado no início antes da primeira variável. Após uma variável, pelo menos um operador é acionado; nesse ponto, um operador pressionado ou outra variável é legal. Os operadores são empurrados para o grupo em duplicado, para que possam ser exibidos corretamente. Exemplo:Infelizmente, isso não nos ajuda a capturar os resultados para agrupá-los, portanto o operador externo é correspondido manualmente. Os colchetes são adicionados de fora para dentro; portanto, o primeiro estágio agrupa toda a expressão entre colchetes e o último estágio os remove agora que eles se propagaram para as variáveis.
fonte
**_**_**_*_****_*
.Haskell ,
167166 bytesExperimente online! Exemplo de uso:
head.e "**_**_**_*_****_*"
rendimentos((_*(_*(_*_)))*_)
. Todos os caracteres, exceto_
são interpretados como operadores,_
indicam um identificador.fonte
Python 3, 226 bytes
Define uma função anônima chamada
R
.Experimente Online!
fonte
_*+
; esses foram exatamente o que foram usados no exemplo. Você pode usar isso para jogar golfe em suas regexes (por exemplo, usando em\d
vez de[*+]
).