Uwaga: Nie, nie jest żartem wyzwanie odwrócenia łańcucha.

Zadanie

Obsługiwana jest tylko jedna operacja: odejmowanie ( -).

Do obsługi są również dwa atomy: zero ( 0) i jeden ( 1).

Tutaj notacja przedrostkowa -ABjest równoważna notacji postfiksowej AB-, gdzie Ai Bsą wyrażeniami.

Twoim zadaniem jest (rekurencyjnie) konwersja wyrażenia w notacji przedrostkowej na jego odpowiednik w notacji postfiksowej.

Definicje

Wyrażenie w notacji przedrostkowej jest generowane przez następującą gramatykę:

S > -SS
S > 0
S > 1

Wyrażenie w notacji postfiksowej jest generowane przez następującą gramatykę:

S > SS-
S > 0
S > 1

Przykład

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

Zasady i wolność

• Możesz zmienić nazwę operacji i atomów na dowolny znak, o ile jest on spójny.
• Format wejściowy musi być zgodny z formatem wyjściowym (poza tym, że dane wejściowe są w notacji prefiksowej, a dane wyjściowe w notacji postfiksowej).

Testcase

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

Testuje kredyty dla Dady .

pieprzenie mózgu , 32 bajty

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

Wypróbuj online!

Użyłem @jako operacji, ponieważ jego punkt kodowy (64) jest wygodny. Ujest również możliwe przy tej samej liczbie bajtów, przy użyciu 3 * 85 + 1 = 256 = 0.

Wyjaśnienie

Taśma służy jako stos. W każdej iteracji głównej pętli wskaźnik danych rozpoczyna dwie komórki po prawej stronie stosu.

,[                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 bajtów

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

Wypróbuj online! Zaoszczędziłem 7 bajtów, zdając sobie sprawę, że warunki zawsze zaczynają się od cyfry, więc nie muszę już ograniczać dopasowania do ostatniego -(wcześniej był to jedyny gwarantowany, że po nim następują dwa terminy). Zaoszczędzono 1 bajt, nie umieszczając -s we własnej linii. Na przykład -01staje się, -0¶1który jest następnie zastępowany przez 01-. Teraz, gdy mam --010IE --0¶1¶0następnie chcę zmienić wewnętrzna -0¶1do 01-tak, że mogę wymienić -01-¶0z 01-0-, ale faktycznie nie sprawa, która z dwóch -s usunąć, więc mogę usunąć jeden na początku wiersza, jak łatwiej to przetestować.

Haskell , 62 59 bajtów

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

Wypróbuj online! Zastosowanie: fst.f $ "--01-0-01". 0i 1mogą być dowolnymi znakami, które są większe niż znak -.

Edycja: -3 bajty dzięki Zgarb!

Funkcja frekurencyjnie analizuje jedno wyrażenie i zwraca krotkę tego wyrażenia w notacji pofiksowej i pozostałym ciągu, zgodnie z prostą gramatyką, z której można zbudować prawidłowe wyrażenia przedrostkowe:

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

Jeśli pierwszy znak aciągu wejściowego jest większy niż -, mamy wyrażenie atomowe i zwracamy krotkę ciągu ze znakiem ai resztę ciągu wejściowego.

Jeśli znajdziemy -, należy przeanalizować dwa wyrażenia. Można to osiągnąć przez (a,x)<-f ruzyskanie pierwszego wyrażenia, aa następnie xponowne przeanalizowanie łańcucha reszt, (b,c)<-f xaby uzyskać drugie wyrażenie bi ostatni łańcuch reszt c. (a,(b,c))<-f<$>f rrobi to dokładnie, ponieważ <$>na mapach krotek funkcja dwa drugi element krotki jest krótsza o trzy bajty (a,x)<-f r,(b,c)<-f x. Po uzyskaniu zarówno wyrażenia i łańcuch spoczynkowego, wyrażenia są łączone, a „-” oznacza przyłączoną: (a++b++"-",c).

Haskell, 54 bajty

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

Funkcja vprzyjmuje ciąg znaków i funkcję, porządkuje początkowe podwyrażenie, a następnie stosuje funkcję do pozostałej części ciągu, dopóki wszystko nie zostanie ponownie uporządkowane. Stos wywołań i argument funkcji razem śledzą, jakie wyrażenie jest analizowane. Funkcja hodpowiada na wyzwanie i jest po prostu vwywoływana jako pierwszy fałszywy argument.

Perl 5 , 57 bajtów

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

Używam xjako operatora zamiast -(patrz poniższy link TryItOnline).

Wypróbuj online!

Objaśnienia:
/x((?0)|.)((?0)|.)/ rekurencyjnie dopasowuje pełne wyrażenie: a xna początku, a następnie wyrażenie (?0)(jest to wywołanie rekurencyjne) lub atom ( .), a następnie kolejne wyrażenie-lub-atom.
Następnie muszę zapisać drugie wyrażenie / atom ( my$n=$2;), ponieważ w przeciwnym razie wywołania rekurencyjne zastąpią je.
Funkcja jest następnie rekurencyjnie wywoływana w pierwszym wyrażeniu ( f($1)), a następnie w drugim f($n), a xznak jest dołączany na końcu ( .x).

Python 3, 117 112 105 100 98 76 62 61 59 bajtów

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

Dziennik zmian:

• usunięto łamanie linii tam, gdzie to możliwe (-5 bajtów)
• lambda zamiast pełnej funkcji (-7 bajtów, dzięki @Dada)
• nie więcej (-5 bajtów, dzięki @Leaky Nun)
• cofnij nadgorliwą grę w golfa (-2 bajty, dzięki @Leaky Nun)
• zamiast tego pracuj na liście globalnej (-22 bajty)
• właściwie, zamiast tego popracujmy nad iteratorami (-14 bajtów)
• zmień !=na >(-1 bajt, skopiowany z sugestii @ovs)
• leniwe oszustwo w ocenie (-2 bajty, dzięki @ovs)

Użyj tego w ten sposób:

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

Pyth, 20 bajtów

L+&-hbTsyM.-Btbytbhb

Tworzy to funkcję, yktóra oczekuje łańcucha jako parametru.

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

Funkcja yprzeanalizuje i skonwertuje pierwsze wyrażenie przedrostkowe na wyrażenie postfiksowe. Więc jeśli zostanie nazwany tak y"10", jak zwróci tylko 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 bajtów

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

Wypróbuj online!

;są używane do wskazywania węzłów, które początkowo składają się z jednej liczby, a następnie rozwijają się do wszystkiego, co już zostało przeanalizowane. -są przekształcane w nowe linie, dzięki czemu .+możemy pobrać wszystko, co nie jest nierozdzielne -.

Perl 6 , 45 bajtów

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

Wypróbuj online!