Avertissement: Non, ce n'est pas un défi de plaisanterie pour inverser une chaîne.

Tâche

Il n'y a qu'une seule opération à prendre en charge: soustraction ( -).

Vous n'avez également que deux atomes à prendre en charge: zéro ( 0) et un ( 1).

Ici, la notation préfixe -ABest équivalente à la notation postfixe AB-, où Aet Bsont des expressions.

Votre tâche consiste à convertir (récursivement) une expression en notation préfixe en son équivalent en notation postfixée.

Définitions

Une expression en notation de préfixe est générée par la grammaire suivante:

S > -SS
S > 0
S > 1

Une expression en notation postfixée est générée par la grammaire suivante:

S > SS-
S > 0
S > 1

Exemple

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

Règles et liberté

• Vous pouvez renommer l'opération et les atomes en n'importe quel caractère, tant qu'il est cohérent.
• Le format d'entrée doit être cohérent avec le format de sortie (à part le fait que l'entrée est en notation préfixe et la sortie est en notation postfixe).

Cas de test

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

Testcases crédits à Dada .

brainfuck , 32 octets

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

Essayez-le en ligne!

J'ai utilisé @comme opération, car son point de code (64) est pratique. Uest également possible avec le même nombre d'octets, en utilisant 3 * 85 + 1 = 256 = 0.

Explication

La bande est utilisée comme une pile. À chaque itération de la boucle principale, le pointeur de données démarre deux cellules à droite du haut de la pile.

,[                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.
]

Rétine , 37 30 29 octets

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

Essayez-le en ligne! Sauvegardé 7 octets en réalisant que les termes commencent toujours par un chiffre, donc je n'ai plus à limiter la correspondance au dernier -(auparavant c'était le seul garanti à être suivi de deux termes). Sauvegardé 1 octet en ne mettant pas -s sur leur propre ligne. Par exemple, -01devient -0¶1qui est ensuite remplacé par 01-. Maintenant, si je dois --010dire--0¶1¶0 Je veux changer l'intérieur -0¶1pour 01-que je puisse remplacer le -01-¶0par 01-0-, mais peu importe lequel des deux -je supprime, je supprime donc celui au début de la ligne, comme c'est plus facile à tester.

Haskell , 62 59 octets

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

Essayez-le en ligne! Utilisation: fst.f $ "--01-0-01". 0et 1peuvent être des caractères arbitraires plus grands que le caractère -.

Edit: -3 octets grâce à Zgarb!

La fonction fanalyse récursivement une expression et retourne un tuple de cette expression en notation postfixe et la chaîne restante, en suivant la grammaire simple à partir de laquelle des expressions de préfixe valides peuvent être construites:

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

Si le premier caractère ade la chaîne d'entrée est plus grand que -, nous sommes à une expression atomique et retournons un tuple d'une chaîne avec du caractère aet le reste de la chaîne d'entrée.

Si nous trouvons a -, deux expressions doivent être analysées. Cela peut être réalisé en obtenant (a,x)<-f rla première expression a, puis en analysant à xnouveau la chaîne de repos (b,c)<-f xpour obtenir la deuxième expression bet la chaîne de repos finale c. (a,(b,c))<-f<$>f rfait exactement cela parce que <$>sur les tuples mappe une fonction deux le deuxième élément d'un tuple tout en étant trois octets plus court que (a,x)<-f r,(b,c)<-f x. Après avoir obtenu les deux expressions et la chaîne de repos, les expressions sont concaténés et « - » est ajouté: (a++b++"-",c).

Haskell, 54 octets

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

La fonction vprend une chaîne et une fonction, réorganise la sous-expression initiale, puis applique la fonction au reste de la chaîne jusqu'à ce que tout soit réorganisé. La pile d'appels et l'argument de fonction conservent ensemble l'expression qui est analysée. La fonction hrépond au défi et est simplement vappelée avec elle-même comme premier argument factice.

Perl 5 , 57 octets

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

J'utilise xcomme opérateur au lieu de -(voir le lien TryItOnline ci-dessous).

Essayez-le en ligne!

Explications:
/x((?0)|.)((?0)|.)/ correspond récursivement à une expression complète: a xau début, puis une expression (?0)(c'est un appel récursif) ou un atome ( .), suivi d'une autre expression-ou-atome.
Ensuite, je dois enregistrer la deuxième expression / atom ( my$n=$2;) car sinon les appels récursifs la remplaceront.
La fonction est ensuite appelée récursivement sur la première expression ( f($1)), puis sur la seconde f($n), et la xest ajoutée à la fin ( .x).

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

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

Journal des modifications:

• suppression des sauts de ligne si possible (-5 octets)
• lambda au lieu d'une fonction complète (-7 octets, merci @Dada)
• pas d'autre (-5 octets, merci @Leaky Nun)
• annuler le golf trop zélé (-2 octets, merci @Leaky Nun)
• travailler sur une liste globale à la place (-22 octets)
• en fait, travaillons plutôt sur les itérateurs (-14 octets)
• changer !=en >(-1 octet, copié à partir de la suggestion de @ovs)
• ruse d'évaluation paresseuse (-2 octets, merci @ovs)

Utilisez-le comme ceci:

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

Pyth, 20 octets

L+&-hbTsyM.-Btbytbhb

Cela crée une fonction yqui attend une chaîne comme paramètre.

Essayez-le en ligne: démonstration ou suite de tests

Explication:

La fonction yanalysera et convertira la première expression de préfixe en une expression de suffixe. Donc, si elle est appelée comme y"10"elle ne reviendra que 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

Rétine , 34 31 29 octets

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

Essayez-le en ligne!

;sont utilisés pour indiquer les nœuds, qui sont initialement composés d'un seul numéro, puis deviennent tout ce qui a déjà été analysé. -sont transformés en nouvelles lignes afin que .+nous puissions saisir tout ce qui n'est pas un non analysé -.

Perl 6 , 45 octets

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

Essayez-le en ligne!