# Convert an Expression to Panfix Notation

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 , so shortest code in bytes wins!

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

# 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));
}
• S.split should be [...S], although it may actually help to match on /\d+|./g up-front and work on that instead.
– Neil
Jul 2, 2016 at 0:27
• @Neil Thanks. I'll look into that. Jul 4, 2016 at 9:33

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

# Prolog, 87 bytes

x(T)-->{T=..[O,A,B]}->[O],x(A),[O],x(B),[O];[T].