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!
More formally, let
+ be an operator, 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:
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
- 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.
format: input -> output +*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_))) **++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_))) ***_**_***_* -> ((_**_)*_) +_+_+ -> (_+_) *+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_) *++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_) +**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_))) +**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_))) +*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_))) **_**_**_*_****_* -> ((_*(_*(_*_)))*_)
I used this program to generate infix strings for this challenge (converting to panfix was trivial, but reversing is not).