# 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? Commented May 9, 2017 at 12:10
• @Shaggy what kind of testcases would you like? Commented May 9, 2017 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? Commented May 9, 2017 at 13:29
• @L3viathan I suppose so... Commented May 9, 2017 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
Commented May 9, 2017 at 18:24
• @Leo Doesn't work in general, e.g. -0-0-00 should become 0000---.
– Neil
Commented May 9, 2017 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
Commented May 9, 2017 at 18:45
• @Leo I've now found my something...
– Neil
Commented May 9, 2017 at 21:48
• @Leo With my latest golf we're tied!
– Neil
Commented May 9, 2017 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) Commented May 10, 2017 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. Commented May 10, 2017 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. Commented May 11, 2017 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. Commented May 11, 2017 at 1:19
• Actually the first line never gets called on valid input, so you can just delete it. Commented May 11, 2017 at 1:31
• Splitting into guards seems to beat the last trick by one byte. Commented May 11, 2017 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 Commented May 9, 2017 at 12:57
• lambda x:p(x)[0] could probably replace your f function.
Commented May 9, 2017 at 12:59
• You don't need else, methinks. Commented May 9, 2017 at 13:01
• Does having d="-" really save bytes? Commented May 9, 2017 at 13:03
• def p(s):x=next(s);yield from[x]*(x>"-")or[*p(s),*p(s),"-"]for 59 bytes
– ovs
Commented May 10, 2017 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 -.

# Unix TMG, 49 bytes

This translation-oriented language from 1972 makes this task trivial:

p:parse(b);b:<->b b={2 1<->}|<0>={<0>}|<1>={<1>};


I believe, this is the first solution in this language on this website, so I will explain a bit:

p: parse(b);                # parse() builtin: execute parsing rule b and output its translation
b: <-> b b = { 2 1 <-> }    # encountering "-" do recursion; translation rule is in braces
| <0> = { <0> }            # otherwise: encountering "0" - translate as "0"
| <1> = { <1> };           # otherwise: encountering "1" - translate as "1"


# Perl 6, 45 bytes

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


Try it online!

# Javascript (ES10), 118 bytes

e=>[...e.matchAll(/(-*)(\d+)/g)].reduce((a,[_,m,[c,...s]])=>(o+=m.slice(l=s.length),a+c+s.join(d='-')+(l?d:s)),o='')+o

Runnable Snippet (TIO doesn't have ES10's String.matchAll yet)

f = e =>
[...e.matchAll(/(-*)(\d+)/g)].reduce((a, [_, m, [c,...s]]) =>
(o += m.slice(l=s.length),
a+c+s.join(d='-')+(l?d:s)), o='')+o;

['1', '0', '-01', '-10', '--01-0-01'].map(v =>
console.log(f('${v}') ->${f(v)}))`