Panfix to parenthesized infix Quylthulg is a language by Chris Pressey that attempts to solve the problem of infix notation using what it calls panfix:


  like postfix, panfix does not require the deployment of arcane contrivances such as parentheses to override a default operator precedence. At the same time, panfix allows terms to be specified in the same order and manner as infix, an unquestionably natural and intuitive notation to those who have become accustomed to it.




How do you get the convenience of infix notation along with the unambiguity of prefix or postfix? Use all three, of course!

=y=+*3*x*+1+=


More formally, let + be an operator, and a and b be expressions. Then (a+b) is a valid (parenthesized) infix expression, the panfix representation of that expression is +a+b+, where juxtaposition represents concatenation.

Your goal is to take a panfix string and convert it to fully parenthesized infix:

(y=((3*x)+1))


For simplicity, we'll make the following changes:


Operators can only consist of two unique characters (you can choose any, but here I'll use * and +).
There is only one literal, which consists of another distinct character (you can choose any, but here I'll use _).
The input will be a well-formed panfix expression.


For complexity, we'll make the following change:


Operators can consist of any positive number of characters, not just one.


This makes the challenge more tricky because you can't necessarily determine how a given substring of operator characters is partitioned without looking at the rest of the string.

Here is a reference implementation for the challenge, courtesy of @user202729.

Test Cases

format: input -&gt; output
+*+_*+_*+++_+*+_*+_*+++ -&gt; ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -&gt; ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -&gt; ((_**_)*_)
+_+_+ -&gt; (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -&gt; (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -&gt; (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -&gt; (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -&gt; (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -&gt; (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -&gt; ((_*(_*(_*_)))*_)


I used this program to generate infix strings for this challenge (converting to panfix was trivial, but reversing is not).
Prolog (SWI), 194 163 bytes

Saved a whopping 31 bytes using this tip from 0 '!

[C|T]/O/R:-C\=x,(T/P/R,concat(C,P,O);O=C,R=T).
[x|R]-x-R.
L-X-R:-L/O/A,A-Y-B,B/O/C,C-Z-D,D/O/R,atomics_to_string(['(',Y,O,Z,')'],X).
X^P:-string_chars(X,L),L-P-[].


The operator ^ takes for its left argument a string containing a panfix expression and sets its right argument to a string containing the corresponding parenthesized infix expression. It uses x as the literal in place of _.

Try it online!

Explanation

Since Prolog is a declarative language, we just have to describe the relation between a panfix and a parenthesized expression.

The explanation uses this slightly ungolfed version:

oper([C|T],O,R) :- C\=x, oper(T,P,R), concat(C,P,O).
oper([C|T],C,T).

expr([x|R],x,R).
expr(L,X,R) :- oper(L,O,A), expr(A,Y,B), oper(B,O,C), expr(C,Z,D), oper(D,O,R),
               atomics_to_string(['(',Y,O,Z,')'],X).

parenthesize(X,P) :- string_chars(X,L), expr(L,P,[]).


Our main production is parenthesize, which takes in a panfix expression X as a string and sends out the corresponding parenthesized infix expression P as a string. It uses string_chars to convert the input string into a list of characters and then simply passes it on to expr.

expr takes in a list of characters L, parses the first panfix expression it finds in L, and sends out the parenthesized equivalent X and the remainder of the list of characters R. There are two possible kinds of expressions:


If the first character of L is x, then the expression is x and the remainder is everything after the x.
Otherwise, parse an operator O (see oper below); parse an expression Y; parse O again; parse another expression Z; and parse O a third time. The remainder is everything after the third instance of O. The expression is the result of joining Y, O, and Z, surrounded by parentheses, into a string.


oper takes in a list of characters, where the first character is C and the rest are T; it parses an operator (i.e. a run of one or more operator characters) and sends out the operator O and the remainder of the list of characters R. To form an operator, the character C must be something other than x; also, either


an operator P must be parseable from T, with remainder R; in this case, O is the concatenation of C and P; or,
O is the single character C; in this case, R is just T.


A worked example

Let's take the input +*+x+x++*x+* for an example.


We want to parse an expression from +*+x+x++*x+*. This doesn't start with x, so we parse an operator from the beginning.
oper will parse as big of an operator as possible, so we try +*+.


Next we parse an expression from x+x++*x+*. This has to be x.
Now we try to parse the same operator, +*+, from +x++*x+*. However, this fails.

So we backtrack and try parsing the operator +* instead.


We parse an expression from +x+x++*x+*. This doesn't start with x, so we need to parse an operator.
The only possibility is +.
Now parse a subexpression from x+x++*x+*. This has to be x.
Now parse + again from +x++*x+*.
Now parse another subexpression from x++*x+*. This has to be x.
Finally, parse + again from ++*x+*.
The expression has been successfully parsed. We return the string (x+x).

Back at the previous recursion level, we parse the operator +* again from +*x+*.
Now parse another subexpression from x+*. This has to be x.
Finally, parse +* again from +*.
The expression has been successfully parsed. We return the string ((x+x)+*x).


Since there are no more characters left, we have successfully translated the expression.