Отказ от ответственности: Нет, это не шутка, чтобы перевернуть строку.

задача

Поддерживается только одна операция: вычитание ( -).

У вас также есть только два атома для поддержки: ноль ( 0) и один ( 1).

Здесь префиксная нотация -ABэквивалентна постфиксной нотации AB-, где Aи Bявляются выражениями.

Ваша задача (рекурсивно) преобразовать выражение в префиксной нотации в его эквивалент в постфиксной нотации.

Определения

Выражение в префиксной записи генерируется следующей грамматикой:

S > -SS
S > 0
S > 1

Выражение в постфиксной нотации генерируется следующей грамматикой:

S > SS-
S > 0
S > 1

пример

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

Правила и свобода

• Вы можете переименовать операцию и атомы в любой символ, если это не противоречит.
• Формат ввода должен соответствовать формату вывода (кроме того факта, что ввод в префиксной записи, а вывод в постфиксной записи).

Прецедент

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

Тесты по кредитам Дада .

брейкфук , 32 байта

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

Попробуйте онлайн!

Я использовал @в качестве операции, потому что его кодовая точка (64) удобна. Uтакже возможно с тем же количеством байтов, используя 3 * 85 + 1 = 256 = 0.

объяснение

Лента используется в качестве стека. На каждой итерации основного цикла указатель данных начинается с двух ячеек справа от вершины стека.

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

Сетчатка , 37 30 29 байт

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

Попробуйте онлайн! Сэкономили 7 байтов, поняв, что термины всегда начинаются с цифры, поэтому мне больше не нужно ограничивать совпадение последним -(ранее это был единственный, за которым следовали два условия). Сохранено 1 байт, не помещая -s в отдельной строке. Например, -01становится, -0¶1который затем заменяется на 01-. Теперь, если у меня есть --010ИЭ , --0¶1¶0то я хочу , чтобы изменить внутреннее , -0¶1чтобы 01-так , что я могу заменить -01-¶0с 01-0-, но это на самом деле не важно , какой из этих двух -сек я удалю, поэтому я удалить один в начале строки, а это проще для проверки.

Haskell , 62 59 байт

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

Попробуйте онлайн! Использование: fst.f $ "--01-0-01". 0и 1могут быть произвольными символами, которые больше, чем символ -.

Редактировать: -3 байта благодаря Zgarb!

Функция fрекурсивно анализирует одно выражение и возвращает кортеж этого выражения в постфиксной нотации и оставшуюся строку, следуя простой грамматике, из которой можно построить допустимые выражения префикса:

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

Если первый символ aвходной строки больше чем -, мы находимся в атомарном выражении и возвращаем кортеж строки с символом aи оставшуюся часть входной строки.

Если мы найдем -, два выражения должны быть проанализированы. Это может быть достигнуто , (a,x)<-f rчтобы получить первое выражение , aа затем разобрать часть строки xснова , (b,c)<-f xчтобы получить второе выражение bи окончательную часть строки c. (a,(b,c))<-f<$>f rделает именно это, потому что <$>на кортежах функция отображает функцию два, второй элемент кортежа, будучи на три байта короче, чем (a,x)<-f r,(b,c)<-f x. После получения обоих выражений и часть строки, выражения сцепляются и «-» добавляется: (a++b++"-",c).

Haskell, 54 байта

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

Функция vпринимает строку и функцию, переставляет начальное подвыражение, затем применяет функцию к оставшейся части строки, пока все не будет переставлено. Стек вызовов и аргумент функции вместе отслеживают, какое выражение анализируется. Функция hотвечает на вызов и просто вызывается vс самим собой как фиктивный первый аргумент.

Perl 5 , 57 байт

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

Я использую в xкачестве оператора вместо -(см. Ссылку TryItOnline ниже).

Попробуйте онлайн!

Пояснения:
/x((?0)|.)((?0)|.)/ рекурсивно соответствует полному выражению: a xв начале, затем выражение (?0)(это рекурсивный вызов) или atom ( .), за которым следует другое выражение-или-атом.
Затем мне нужно сохранить второе выражение / atom ( my$n=$2;), потому что в противном случае рекурсивные вызовы переопределят его.
Затем функция вызывается рекурсивно в первом выражении ( f($1)), затем во втором f($n)и xдобавляется в конце ( .x).

Python 3, 117 112 105 100 98 76 62 61 59 байт

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

Changelog:

• по возможности удалены разрывы строк (-5 байт)
• лямбда вместо полноценной функции (-7 байт, спасибо @Dada)
• нет больше (-5 байт, спасибо @Leaky Nun)
• отменить чрезмерное усердие в гольфе (-2 байта, спасибо @Leaky Nun)
• вместо этого работать с глобальным списком (-22 байта)
• на самом деле, давайте работать вместо итераторов (-14 байт)
• изменить !=на >(-1 байт, скопировано из предложения @ovs)
• ленивый трюк с оценкой (-2 байта, спасибо @ovs)

Используйте это так:

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

Pyth, 20 байт

L+&-hbTsyM.-Btbytbhb

Это создает функцию, yкоторая ожидает строку в качестве параметра.

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

Функция yпроанализирует и преобразует первое префиксное выражение в постфиксное выражение. Так что, если он называется как y"10"он вернется только 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

Сетчатка , 34 31 29 байт

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

Попробуйте онлайн!

;используются для указания узлов, которые изначально составлены из одного числа, а затем увеличиваются до всего, что уже было проанализировано. -превращаются в новые строки, так что с помощью .+мы можем захватить все, что не разобрано -.

Perl 6 , 45 байт

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

Попробуйте онлайн!