Panfix to parenthesized infix

Question

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 -> output
+*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -> ((_**_)*_)
+_+_+ -> (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -> ((_*(_*(_*_)))*_)

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

Answer 1

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.

Answer 2

Perl, 78 60 58 57 50 bytes

Includes +1 for p

Uses 1 for + and 2 for * (or in fact any digit works for any operator)

perl -pe 's/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo' <<< 22_22_22_2_2222_2

For convenient testing versus the given examples you can use this which does the translations and space removal for you:

perl -pe 'y/+*/12/;s/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo;y/ //d;y/12/+*/' <<< "**_**_**_*_****_*"

Answer 3

Clean, 200 192 189 bytes

import StdEnv,Text
f"_"=["_"]
f l=["("+a+p+b+")"\\p<-[l%(0,i)\\i<-[0..indexOf"_"l]|endsWith(l%(0,i))l],t<-[tl(init(split p l))],n<-indexList t,a<-f(join p(take n t))&b<-f(join p(drop n t))]

Try it online!

Defines the function f, taking String, and returning a singleton [String] with the result inside.

Some neat stuff:

• Doesn't use regex
• Works with any character for operators except _

Answer 4

Retina 0.8.2, 138 134 bytes

.+
($&)
+`\((\d+)(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)$.))\1(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)$.))\1\)
(($2)$1($4))
\(_\)
_

Try it online! Link includes the faster test cases. Explanation: The regex engine uses backtracking to split the string up into tokens which are then pushed on or popped from the i balancing group. There is a run of always at least one operator pushed at the start before the first variable. After a variable, at least one operator is popped, at which point either a pushed operator run or another variable is legal. Operators get pushed to the group in duplicate so that they can be popped correctly. Example:

Input           Stack
Push *          * *
Push *++*+***   * * *++*+*** *++*+***
Push +          * * *++*+*** *++*+*** + +
Push +          * * *++*+*** *++*+*** + + + +
Variable _
Pop +           * * *++*+*** *++*+*** + + +
Variable _
Pop +           * * *++*+*** *++*+*** + +
Pop +           * * *++*+*** *++*+*** +
Variable _
Pop +           * * *++*+*** *++*+***
Pop *++*+***    * * *++*+***
Variable _
Pop *++*+***    * *
Pop *           *
Push *          * * *
Variable _
Pop *           * *
Push *          * * * *
Variable _
Pop *           * * *
Variable _
Pop *           * *
Pop *           *
Pop *

Unfortunately this doesn't help us capture the results in order to bracket them, so the outer operator is matched manually. The brackets are added outside-in, so the first stage wraps the entire expression in brackets and the last stage removes them now that they have propagated down to the variables.

Answer 5

Haskell, 167 166 bytes

head.e
e('_':r)=["_",r]
e(x:r)=[x]%r
e _=[]
o%t@(c:r)|[x,u]<-e t,n<-length o,[y,v]<-e$drop n u,all((==o).take n)[u,v]=['(':x++o++y++")",drop n v]|p<-o++[c]=p%r
o%_=[]

Try it online! Example usage: head.e "**_**_**_*_****_*" yields ((_*(_*(_*_)))*_). All characters except _ are interpreted as operators, _ itself denotes an identifier.

Answer 6

Python 3, 226 bytes

from re import*
P=r'([*+]+)'+r'(\(.+?\)|_)\1'*2;R=lambda i,J=lambda i,o:i[:o]+sub(P,lambda o:'('+o[2]+o[1]+o[3]+')',i[o:],1),s=search:s(P,i)and R([J(i,o)for o in range(len(i))if s(P,J(i,o))or J(i,o)[0]+J(i,o)[-1]=='()'][0])or i

Defines an anonymous function named R.

Try it Online!