Prefix Notation to Postfix Notation

Disclaimer: No, this is not a joke challenge to reverse a string.

There is only one operation to support: subtraction (-).

You also only have two atoms to support: zero (0) and one (1).

Here, the prefix notation -AB is equivalent to the postfix notation AB-, where A and B are expressions.

Your task is to (recursively) convert an expression in prefix notation to its equivalent in postfix notation.

Definitions

An expression in prefix notation is generated by the following grammar:

S > -SS
S > 0
S > 1


An expression in postfix notation is generated by the following grammar:

S > SS-
S > 0
S > 1


Example

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


Rules and freedom

• You may rename the operation and the atoms to whichever character, as long as it is consistent.
• The input format must be consistent with the output format (apart from the fact that the input is in prefix notation and the output is in postfix notation).

Testcase

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


• Can you add a few more test cases, please? – Shaggy May 9 '17 at 12:10
• @Shaggy what kind of testcases would you like? – Leaky Nun May 9 '17 at 12:12
• @LeakyNun Is it fine to take the input and output as iterators, as I've done in the latest version of my answer? – L3viathan May 9 '17 at 13:29
• @L3viathan I suppose so... – Leaky Nun May 9 '17 at 14:37

brainfuck, 32 bytes

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


Try it online!

I used @ as the operation, because its code point (64) is convenient. U is also possible with the same byte count, using 3*85+1=256=0.

Explanation

The tape is used as a stack. In each iteration of the main loop, the data pointer starts two cells right of the top of the stack.

,[                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, 3730 29 bytes

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


Try it online! Saved 7 bytes by realising that terms always begin with a digit, so I don't have to limit the match to the last - any more (previously it was the only one guaranteed to be followed by two terms). Saved 1 byte by not putting -s on their own line. For example, -01 becomes -0¶1 which is then replaced with 01-. Now, if I have --010 i.e. --0¶1¶0 then I want to change the inner -0¶1 to 01- so that I can replace the -01-¶0 with 01-0-, but it doesn't actually matter which of the two -s I remove, so I remove the one at the beginning of the line, as that's easier to test for.

• I think this is your something :) – Leo May 9 '17 at 18:24
• @Leo Doesn't work in general, e.g. -0-0-00 should become 0000---. – Neil May 9 '17 at 18:29
• You're right, sorry. I have another idea, but it's substantially different, so I'll post it as a new answer – Leo May 9 '17 at 18:45
• @Leo I've now found my something... – Neil May 9 '17 at 21:48
• @Leo With my latest golf we're tied! – Neil May 9 '17 at 22:03

f(x:r)|x>'-'=([x],r)|(a,(b,c))<-f<$>f r=(a++b++"-",c) fst.f  Try it online! Usage: fst.f$ "--01-0-01". 0 and 1 can be arbitrary characters that are larger than the character -.

Edit: -3 bytes thanks to Zgarb!

The function f recursively parses one expression and returns a tuple of this expression in postfix notation and the rest string, following the simple grammar from which valid prefix-expressions can be build:

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


If the first character a of the input string is larger than -, we are at an atomic expression and return a tuple of a string with character a and the rest of the input string.

If we find a -, two expressions need to be parsed. This can be achieved by (a,x)<-f r to get the first expression a and then parse the rest string x again (b,c)<-f x to get the second expression b and the final rest string c. (a,(b,c))<-f<$>f r does exactly this because <$> on tuples maps a function two the second element of a tuple while being three bytes shorter than (a,x)<-f r,(b,c)<-f x. After obtaining both expressions and the rest string, the expressions are concatenated and a "-" is appended: (a++b++"-",c).

• You can save 3 bytes by combining the cases: f(x:r)|x>'-'=([x],r)|(a,(b,c))<-f<$>f r=(a++b++"-",c) – Zgarb May 10 '17 at 7:07 • @Zgarb Thanks! For some reason I only considered f(x:r)|x<'0',(a,(b,c))<-f<$>f r=(a++b++"-",c)|1<3=([x],r) when I looked for a version with both cases combined, which is byte longer. – Laikoni May 10 '17 at 21:42

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


The function v takes a string and a function, rearranges the initial sub-expression, then applies the function to the remainder of the string until everything has been rearranged. The call stack and function argument together keep track of what expression is being parsed. The function h answers the challenge, and is just v called with itself as a dummy first argument.

• Wow! (1) That's just 53, you don't need to count the final newline. (2) The first line can be shortened to v f l=l if you move it second. – Ørjan Johansen May 11 '17 at 1:06
• I don't think you need to parse more than one whole expression, so you can save a byte by using the anonymous function v id. – Ørjan Johansen May 11 '17 at 1:19
• Actually the first line never gets called on valid input, so you can just delete it. – Ørjan Johansen May 11 '17 at 1:31
• Splitting into guards seems to beat the last trick by one byte. – Ørjan Johansen May 11 '17 at 2:03

Perl 5, 57 bytes

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


I use x as operator instead of - (see the TryItOnline link bellow).

Try it online!

Explanations:
/x((?0)|.)((?0)|.)/ matches recursively a full expression: a x at the begining, then an expression (?0) (it's a recursive call) or an atom (.), followed by another expression-or-atom.
Then I need to save the second expression/atom (my$n=$2;) because otherwise the recursive calls will override it.
The function is then recursively called on the first expression (f($1)), then on the second f($n), and the x is appended at the end (.x).

Python 3, 11711210510098766261 59 bytes

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


Changelog:

• removed linebreaks where possible (-5 bytes)
• no else (-5 bytes, thanks @Leaky Nun)
• undo overzealous golfing (-2 bytes, thanks @Leaky Nun)
• work on a global list instead (-22 bytes)
• actually, let's work on iterators instead (-14 bytes)
• change != to > (-1 byte, copied from @ovs' suggestion)
• lazy evaluation trickery (-2 bytes, thanks @ovs)

Use it like this:

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

• Doesn't work because you forgot return – Leaky Nun May 9 '17 at 12:57
• lambda x:p(x)[0] could probably replace your f function. – Dada May 9 '17 at 12:59
• You don't need else, methinks. – Leaky Nun May 9 '17 at 13:01
• Does having d="-" really save bytes? – Leaky Nun May 9 '17 at 13:03
• def p(s):x=next(s);yield from[x]*(x>"-")or[*p(s),*p(s),"-"]for 59 bytes – ovs May 10 '17 at 13:22

Pyth, 20 bytes

L+&-hbTsyM.-Btbytbhb


This creates a function y that expects a string as parameter.

Try it online: Demonstration or Test Suite

Explanation:

The function y will parse and convert the first prefix expression to a postfix expression. So if it is called like y"10" it will return only 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, 3431 29 bytes


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



Try it online!

; are used to indicate nodes, which are initially composed by a single number and then grow to anything that has already been parsed. - are turned into newlines so that with .+ we can grab anything that isn't an unparsed -.

Perl 6, 45 bytes

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

Try it online!