Panfix to parenthesized infix
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.