Convert an Expression to Panfix Notation

Question

I was browsing esolangs, and chanced upon this language: https://github.com/catseye/Quylthulg.

One interesting thing about this language, is that it doesn't use prefix, postfix, or infix, it uses all three of them, calling it "panfix" notation.

Here is an example. To represent normal infix 1+2 in panfix, it becomes: +1+2+. Notice how the operator is both before, in between, and after the operands. Another example is (1+2)*3. This becomes *+1+2+*3*. Notice again how * is in all three places with respect to the operands +1+2+ and 3.

The Challenge

As you may have guessed, your task in this challenge is to convert an expression from infix to panfix.

A few clarifications:

• You only have to deal with the four basic operations: +-*/
• You won't have to deal with the unary versions of those, only binary
• You have to deal with parenthesis
• Assume the normal precedence rules of */ then +- and left associativity for all of them.
• The numbers will be nonnegative integers
• You can optionally have a spaces in both the input and output

Test Cases

1+2  ->  +1+2+
1+2+3  ->  ++1+2++3+
(1+2)*3  ->  *+1+2+*3*
10/2*5  ->  */10/2/*5*
(5+3)*((9+18)/4-1)  ->  *+5+3+*-/+9+18+/4/-1-*

This is code-golf, so shortest code in bytes wins!

Answer 1

JavaScript (ES6), ^{_{285 282 281 267 251 243 241 238 234 232}} 231 bytes

~15 bytes thanks to Neil.

f=(I,E=I.match(/\d+|./g),i=0)=>(J=T=>T.map?T.map(J).join``:T)((R=(H,l=(P=_=>(t=E[i++])<")"?R(0):t)(),C,F)=>{for(;(C=P())>")"&&(q=C>"*"&&C<"/")*H-1;)F=q+H?l=[C,l,C,P(),C]:F?l[3]=[C,l[3],C,R(1),C]:l=R(1,l,i--)
i-=C>")"
return l})(0))

In JavaScript this is a bit harder than in Mathematica. This is basically an over-specialized and golfed operator-precedence parser.

Causes stack overflows on invalid inputs.

Demo

f=(I,E=I.match(/\d+|./g),i=0)=>(J=T=>T.map?T.map(J).join``:T)((R=(H,l=(P=_=>(t=E[i++])<")"?R(0):t)(),C,F)=>{for(;(C=P())>")"&&(q=C>"*"&&C<"/")*H-1;)F=q+H?l=[C,l,C,P(),C]:F?l[3]=[C,l[3],C,R(1),C]:l=R(1,l,i--)
i-=C>")"
return l})(0))

<input id="input" value="(5+3)*((9+18)/4-1)"/><button onclick="console.log(f(document.querySelector('#input').value))">Convert</button>

Ungolfed

convert = input => {
  tokens = input.match(/\d+|./g);
  i = 0;
  parse_token = () => (token = tokens[i++]) == "(" ? parse_tree(false) : token;
  parse_tree = (mul_div_mode, left = parse_token()) => {
    while ((oper = parse_token()) != ")" && !((is_plus_minus = oper == "+" || oper == "-") && mul_div_mode)) {
      if (is_plus_minus || mul_div_mode)
        left = [oper, left, oper, parse_token(), oper];
      else if (non_first)
        left[3] = [oper, left[3], oper, parse_tree(true), oper];
      else
        left = parse_tree(true, left, i--);
      non_first = true;
    }
    if (oper != ")")
      i--;
    return left;
  };
  format_tree = tree => tree.map ? tree.map(format_tree).join("") : tree;
  return format_tree(parse_tree(false));
}

Answer 2

JavaScript (ES6), 160 bytes

f=(s,t=s.replace(/[*-/]/g,"'$&'"),u=t.replace(/^(.*?)([*-9]+)'([*/])'([*-9]+)|([*-9]+)'([+-])'([*-9]+)|\(([*-9]+)\)/,"$1$3$2$3$4$3$6$5$6$7$6$8"))=>t==u?t:f(s,u)

Works by quoting all the operators (which gives them character codes before *), then looking for available '*' or '/' operations, '+' or '-' operations or ()s, and replacing the first with its panfix notation. Example:

(5+3)*((9+18)/4-1)
(5'+'3)'*'((9'+'18)'/'4'-'1)
(+5+3+)'*'((9'+'18)'/'4'-'1)
+5+3+'*'((9'+'18)'/'4'-'1)
+5+3+'*'((+9+18+)'/'4'-'1)
+5+3+'*'(+9+18+'/'4'-'1)
+5+3+'*'(/+9+18+/4/'-'1)
+5+3+'*'(-/+9+18+/4/-1-)
+5+3+'*'-/+9+18+/4/-1-
*+5+3+*-/+9+18+/4/-1-*

Answer 3

Mathematica, 203 195 bytes

This is likely less than efficient, but seems to do the job.

Function[f,ReleaseHold[(Inactivate@f/._[Plus][a_,b_/;b<0]:>a~"-"~-b//Activate@*Hold)//.a_/b_:>a~"/"~b/.{a_Integer:>ToString@a,Plus:>"+",Times:>"*"}]//.a_String~b_~c_String:>b<>a<>b<>c<>b,HoldAll]

This is an anonymous function that takes an actual expression and returns a string with panfix notation. Mathematica sorts out the precedence of operators at parsing time, rather than evaluation time, so the nesting should be automagically correct. At least the test cases work as expected.

Explanation: It's easy enough to interpret the entire expression as a tree, like so:

At this stage the operators (every node that isn't a leaf) aren't operators any more, they've actually been converted to strings such as "+". The integers are also cast to strings. Then a repeated replacement rule converts every node that has exactly two leafs to the panfix parent-leaf1-parent-leaf2-parent. After some iterations the tree reduces to a single string.

The main loss in the byte count is that Mathematica interprets

5 - 4 -> 5 + (-4)
9 / 3 -> 9 * (3^(-1))

And this happens also at parsing time.

Golfed down a bit, since the pattern a_/b_ is also interpreted as a_ * (b_)^(-1). Also some minor optimizations elsewhere.

Answer 4

Prolog, 87 bytes

x(T)-->{T=..[O,A,B]}->[O],x(A),[O],x(B),[O];[T].
p:-read(T),x(T,L,[]),maplist(write,L).

This is a function (mostly because writing a full program has nightmarish levels of boilerplate in Prolog; normally, even if you compile a program, it produces a REPL when run), called p. It takes input from stdin and outputs on stdout. Note that you need to append a period to the input, which is an unfortunate consequence of the way that Prolog's input routines work (they use periods in the input in much the same way that other languages use newlines); that might or might not disqualify the answer.

Explanation

Arithmetic operators, in Prolog, are normally interpreted as tuple constructors. However, they obey the same precedence rules as the actual arithmetic operators they're based on; you can form tuples with infix notation, and + and - bind less tightly than * and /, with precedence taken left to right within a group. This is exactly what the question asks for; thus, we can read an entire nested tuple from the input, and it already has the right structure. That's what p does.

Next, we need to convert it to panfix notation. x converts the input into a panfixed list of constructors and integers, and can be read as an English sentence almost directly: "x of T is: if T is a tuple with constructor O and arguments A,B, then O, x of A, O, x of B, O, else T". Finally, we just have to print the list without any separators (i.e. using maplist to call write on each element of the list).

I used SWI-Prolog for testing this, because my version of GNU Prolog doesn't have maplist yet (apparently it's been added to a newer version), but it should generally be fairly portable between Prolog implementations.