Disclaimer: Não, este não é um desafio de piada para reverter uma string.

Tarefa

Há apenas uma operação para suportar: subtração ( -).

Você também tem apenas dois átomos para suportar: zero ( 0) e um ( 1).

Aqui, a notação de prefixo -ABé equivalente à notação de postfix AB-, onde Ae Bsão expressões.

Sua tarefa é (recursivamente) converter uma expressão na notação de prefixo em seu equivalente na notação postfix.

Definições

Uma expressão na notação de prefixo é gerada pela seguinte gramática:

S > -SS
S > 0
S > 1

Uma expressão na notação postfix é gerada pela seguinte gramática:

S > SS-
S > 0
S > 1

Exemplo

Prefix notation:  --01-0-01
Parentheses:      -(-01)(-0(-01))
Convert:          (01-)(0(01-)-)-
Postfix notation: 01-001---

Regras e liberdade

• Você pode renomear a operação e os átomos para qualquer caractere, desde que seja consistente.
• O formato de entrada deve ser consistente com o formato de saída (além do fato de que a entrada está na notação de prefixo e a saída está na notação de postfix).

Caso de teste

Input       Output
1           1
0           0
-01         01-
-10         10-
--01-0-01   01-001---

Testcas fornece créditos ao Dada .

brainfuck , 32 bytes

,[[->++++<<+>]>[[-]<<[.[-]<]]>,]

Experimente online!

Eu usei @como operação, porque seu ponto de código (64) é conveniente. Utambém é possível com a mesma contagem de bytes, usando 3 * 85 + 1 = 256 = 0.

Explicação

A fita é usada como uma pilha. Em cada iteração do loop principal, o ponteiro de dados inicia duas células à direita da parte superior da pilha.

,[                Take input and start main loop
  [->++++<<+>]    Push input, and compute 4*input
  >[              If 4*input is nonzero (and thus input is not @):
    [-]<<           Zero out this cell and move to top of stack
    [.[-]<]         Pop from stack and output until \0 is reached
  ]
  >,              Move pointer into the correct position.  If input was @, the earlier > pushed \0 onto the stack.
]

Retina , 37 30 29 bytes

M!`-*.
+m`^-(.*)¶(\d.*)
$1$2-

Experimente online! Economizei 7 bytes ao perceber que os termos sempre começam com um dígito, para que eu não precise mais limitar a correspondência aos últimos -(anteriormente era o único garantido a ser seguido por dois termos). Economizou 1 byte não colocando -s em sua própria linha. Por exemplo, -01torna-se -0¶1qual é então substituído por 01-. Agora, se eu tiver, --010ou seja --0¶1¶0, quero mudar o interior -0¶1para 01-para poder substituir o -01-¶0com 01-0-, mas na verdade não importa qual dos dois -s removo, removo o que está no início da linha, como isso é mais fácil de testar.

Haskell , 62 59 bytes

f(x:r)|x>'-'=([x],r)|(a,(b,c))<-f<$>f r=(a++b++"-",c)
fst.f

Experimente online! Uso: fst.f $ "--01-0-01". 0e 1podem ser caracteres arbitrários que são maiores que o caractere -.

Edit: -3 bytes graças ao Zgarb!

A função fanalisa recursivamente uma expressão e retorna uma tupla dessa expressão na notação postfix e na string restante, seguindo a gramática simples a partir da qual expressões de prefixo válidas podem ser construídas:

<exp> ::= - <exp> <exp> | 0 | 1

Se o primeiro caractere ada string de entrada for maior que -, estaremos em uma expressão atômica e retornaremos uma tupla de uma string com o caractere ae o restante da string de entrada.

Se encontrarmos a -, duas expressões precisam ser analisadas. Isso pode ser obtido (a,x)<-f rpara obter a primeira expressão ae, em seguida, analisar xnovamente (b,c)<-f xa sequência restante para obter a segunda expressão be a sequência final restante c. (a,(b,c))<-f<$>f rfaz exatamente isso porque <$>nas tuplas mapeia uma função dois, o segundo elemento de uma tupla, sendo três bytes menor que (a,x)<-f r,(b,c)<-f x. Depois de obter as duas expressões e a corda resto, as expressões são concatenados e um "-" é acrescentado: (a++b++"-",c).

Haskell, 54 bytes

v f""=""
v f(a:s)=last(v.v:[id|a>'-'])((a:).f)s
h=v h

A função vpega uma string e uma função, reorganiza a subexpressão inicial e aplica a função ao restante da string até que tudo tenha sido reorganizado. A pilha de chamadas e o argumento da função juntos acompanham qual expressão está sendo analisada. A função hresponde ao desafio e é vchamada de si mesma como um primeiro argumento fictício.

Perl 5 , 57 bytes

sub f{"@_"=~s/x((?0)|.)((?0)|.)/my$n=$2;f($1).f($n).x/re}

Eu uso xcomo operador em vez de -(veja o link TryItOnline abaixo).

Experimente online!

Explicações:
/x((?0)|.)((?0)|.)/ corresponde recursivamente a uma expressão completa: a xno início, depois uma expressão (?0)(é uma chamada recursiva) ou um átomo ( .), seguido por outra expressão-ou-átomo.
Então, preciso salvar a segunda expressão / atom ( my$n=$2;), porque, caso contrário, as chamadas recursivas a substituirão.
A função é chamada recursivamente na primeira expressão ( f($1)), depois na segunda f($n)e nox é anexada no final ( .x).

Python 3, 117 112 105 100 98 76 62 61 59 bytes

def p(s):x=next(s);yield from[x]*(x>"-")or[*p(s),*p(s),"-"]

Changelog:

• quebras de linha removidas sempre que possível (-5 bytes)
• lambda em vez de uma função completa (-7 bytes, obrigado @Dada)
• mais nada (-5 bytes, obrigado @Leaky Nun)
• desfazer golfe excessivamente zeloso (-2 bytes, obrigado @Leaky Nun)
• trabalhe em uma lista global (-22 bytes)
• na verdade, vamos trabalhar em iteradores (-14 bytes)
• mude !=para> (-1 byte, copiado da sugestão de @ovs)
• truques de avaliação preguiçosos (-2 bytes, obrigado @ovs)

Use-o assim:

>>> list(p(iter("--01-0-01")))
['0', '1', '-', '0', '0', '1', '-', '-', '-']

Pitão, 20 bytes

L+&-hbTsyM.-Btbytbhb

Isso cria uma função y que espera uma string como parâmetro.

Experimente on-line: Demonstration or Test Suite

Explicação:

A função yanalisará e converterá a primeira expressão de prefixo em uma expressão de postfix. Portanto, se for chamado assim, y"10"ele retornará apenas 1.

L+&-hbTsyM.-Btbytbhb
L                      define a function y(b), that returns:
   -hbT                   remove the chars "10" from the first char b
                          (T=10, and - will convert a number to a string)
  &                       if this gives the empty string (a falsy value)
 +                hb         then append b[0] to it and return it
                             (so this will parse a digit 0 or 1 from the string)
  &                       otherwise (the first char is a -)
               ytb           parse the first prefix expression from b[1:]
                             (recursive call)
          .-Btb              remove this parsed expression bifurcated from b[1:]
                             this gives a tuple [b[1:], b[1:] without first expr]
        yM                   parse and convert an expression from each one
       s                     join the results
 +                hb         and append the b[0] (the minus) to it and return

Retina , 34 31 29 bytes

;
-;
¶
+`¶(.+);(.+)
$1$2-
;

Experimente online!

;são usados ​​para indicar nós, que são compostos inicialmente por um único número e aumentam para qualquer coisa que já tenha sido analisada. -são transformadas em novas linhas, para que .+possamos pegar qualquer coisa que não seja analisada -.

Perl 6 , 45 bytes

my&f={S[x(<~~>)**2|)>.]=$0&&$0>>.&f.join~'x'}

Experimente online!