Este é um modelo de um analisador de HTML que perdoa. Em vez de analisar o HTML e extrair atributos, nesse código golf, o analisador de tags será simples.
Escreva uma função que analise uma estrutura de tags e retorne seu formulário entre parênteses. Uma tag de abertura consiste em uma letra minúscula e uma tag de fechamento consiste em uma letra maiúscula. Por exemplo, aAbaAB
analisa em (a)(b(a))
, ou em HTML <a></a><b><a></a></b>
,. Obviamente, as tags podem estar em justaposição e aninhadas.
As tags fechadas "prematuramente" devem ser manipuladas. Por exemplo, em abcA
, o A
fecha o mais externo a
, por isso é analisado (a(b(c)))
.
Tags de fechamento extras são simplesmente ignoradas: aAB
analisa (a)
.
Tags sobrepostas NÃO são tratadas. Por exemplo, abAB
analisa (a(b))
, não (a(b))(b)
, pela regra anterior de tags de fechamento extras ( abAB
-> abA
( (a(b))
) + B
(extra)).
Supondo que não haja espaços em branco e outros caracteres ilegais na entrada.
Você não tem permissão para usar nenhuma biblioteca.
Aqui está uma implementação de referência e uma lista de casos de teste:
#!/usr/bin/python
def pars(inpu):
outp = ""
stac = []
i = 0
for x in inpu:
lowr = x.lower()
if x == lowr:
stac.append(x)
outp += "(" + x
i = i + 1
else:
while len(stac) > 1 and stac[len(stac) - 1] != lowr:
outp += ")"
stac.pop()
i = i - 1
if len(stac) > 0:
outp += ")"
stac.pop()
i = i - 1
outp += ")" * i
return outp
tests = [
("aAaAbB", "(a)(a)(b)"),
("abBcdDCA", "(a(b)(c(d)))"),
("bisSsIB", "(b(i(s)(s)))"),
("aAabc", "(a)(a(b(c)))"),
("abcdDA", "(a(b(c(d))))"),
("abcAaA", "(a(b(c)))(a)"),
("acAC", "(a(c))"),
("ABCDEFG", ""),
("AbcBCabA", "(b(c))(a(b))")
]
for case, expe in tests:
actu = pars(case)
print "%s: C: [%s] E: [%s] A: [%s]" % (["FAIL", "PASS"][expe == actu], case, expe, actu)
O menor código vence.
AbcBCabA
(deve analisar como(b(c))(a(b))
meu código poderia ter sido mais curto, exceto para este caso..Respostas:
Golfscript, 54 caracteres
Testes
fonte
Haskell, 111 caracteres
Esse aqui é bonito para Haskell. Funcionalidade divertida: A pilha e a saída acumulada são mantidas na mesma sequência!
Casos de teste:
@
padrão sugerido por FUZxxlfonte
Código da máquina Z80 para TI-83 +, 41 bytes
Esta é uma implementação em código de máquina hexadecimal para uma CPU z80 em execução na TI-83 +.
11XXXX131AFE61380F6FE53E28CD9DB47DCD9DB4188EE1BDC03E29CD9DB4189BEF4504E5214CE1C9
O XXXX (3-6 inclusive) é o endereço de 16 bits da string que você está analisando, menos 1 byte.
Codificado em Z80-ASCII:
¹XX≤¯•⟙8𝑭o↥>(ˣïÑ}ˣïÑ≠á↑γ∊>)ˣïÑ≠Ì⬆︎E𝑤↥!₄L↑Φ
(Aproximado, porque as calculadoras de TI têm seu próprio conjunto de caracteres.)
OBSERVAÇÃO DE
AsmPrgm
QUE NÃO ESTÁ INCLUÍDO ACIMAfonte
Windows PowerShell, 142
146147152156169Algumas coisas a serem observadas: este é apenas um bloco de script. Pode ser atribuído a uma variável ou receber um nome de função, se necessário. Você também pode executá-lo colocando
.
ou&
na frente dele e dos argumentos no final. Usa um espaço final para finalizar tags não fechadas.Passa em todos os testes. Script de teste:
fonte
Python -
114113153192 192174159 caracteresAbusa do analisador de indentação do python para usar um espaço para uma guia completa, cinco para duas guias.
Editar 1 - salvou um espaço desnecessário na função range ()
Edição 2 - corrigida para lidar com gramáticas de análise impróprias, tags não terminadas.
Editar 3 - corrigido um bug no qual as análises "incorretas" podiam ser geradas por ambiguidade na árvore de tags. Implementou uma estratégia baseada em pilha, em vez de um contador.
Edite 4 - renomeado s.find para o para evitar salvar os caracteres usados para chamá-lo repetidamente. fez o mesmo para f.lower.
Editar 5 - adicionado o hack espaço / guia, salvando três caracteres.
Edit 6 - abandonou o loop em favor de ")" * d.
fonte
ord(f)...
você pode usar'@'<f<'\\'
Se você não precisa verificar para'\\'
que você pode usar']'
em vezif ...:s+=")";c-=1
Eelse:s+="("+f;c+=1
for i in range(d):s+=")"
pode ser reescrito comos+=")"*d
. E você tem 174 caracteres.