Prefix Notation to Postfix Notation

Question

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

Task

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---

Testcases credits to Dada.

Answer 1

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

Answer 2

Retina, 37 30 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.

Answer 3

Haskell, 62 59 bytes

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).

Answer 4

Haskell, 54 bytes

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.

Answer 5

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).

Answer 6

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

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

Changelog:

• removed linebreaks where possible (-5 bytes)
• lambda instead of a full function (-7 bytes, thanks @Dada)
• 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', '-', '-', '-']

Answer 7

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

Answer 8

Retina, 34 31 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 -.

Answer 9

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"

Answer 10

Perl 6, 45 bytes

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

Try it online!

Answer 11

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)}`))