# Parse a Scala expression

Scala isn't a very commonly used language around here. Most of those who know it like it[citation needed], but some go :\ when they encounter its user-defined operators, saying they're too complicated.

However, they're governed by a very simple set of rules, outlined here. Their precedence depends on the first character. Here's the list for that (highest to lowest precedence):

* / %
+ -
:
= !
< >
&
^
|
(all letters)


So this

a + b ^? c less a ==> b | c


would be the same as this

((a + b) ^? c) less ((a ==> b) | c)


Your task is to turn such an expression (only infix applications) into a tree-like structure or a string with all the sub-expressions in parentheses.

## Input

A string or multiple characters given as an argument to a function, read from STDIN, given as command-line arguments, or using one of the other default input methods. This string is the expression to be parsed.

## Output

You could do one of the following, printed to STDOUT, returned from a function, or one of the other default output methods:

• The same string but with parentheses outside each sub-expression (the outermost expression may or may not be parenthesized). E.g., expr op expr2 op2 expr3 -> (expr op expr2) op2 expr3. If you wish, you may also parenthesize the atoms ((((expr) op (expr2)) op2 (expr3)))
• A multidimensional list, where each expression would broken up into the left argument, the operator/method, and the right argument. E.g., expr op expr2 op2 expr3 -> [['expr','op','expr2'],'op2','expr3']
• Some tree-like structure equivalent to the above 2 representations. You get the idea.

## Rules

• All operators used are binary, infix, and left-associative.
• Parsing goes from left to right.
• There will always be one or more spaces between arguments and operators.
• Operators may consist of any of the symbols mentioned above (*/%+-:=!<>&^|) and uppercase or lowercase letters([A-Za-z]). They will be one or more characters.
• Arguments to methods may be other expressions or alphabetical identifiers ([A-Za-z]).
• This is , so shortest code wins!

## Test cases

More coming soon

Input                             -> Output
a -- blah /\ foo                  -> a -- (blah /\ foo)
same ** fst *^ chr *& operators   -> ((same ** fst) *^ chr) *& operators
Lots   Of     SpAceS // here      -> Lots Of (SpAceS // here)
Not : confusing * At / ALL iS it  -> (Not : ((confusing * At) / ALL)) iS it
This *isnot* valid ** Scala       -> (This *isnot* valid) ** Scala

• Sandbox – user Oct 4 '20 at 0:20
• You use ? in your first example but it isn't listed in the precedence table above. Is that because it belongs to (characters not shown below)? Either way it's confusing, Perhaps adding ? as an example of (characters not shown below) would be clearer. Or something else if that's not the case. And then letters pop up at the end? Are they not characrters not shown below? Maybe regexs explicitly stating them all would be better. – Noodle9 Oct 4 '20 at 8:30
• Hmm, can Scala compile a string which is scala and somehow output it's own internal parse tree? – Kjetil S. Oct 4 '20 at 14:44
• I guess I only can distinguish word-like operators from operands by the fact that operands and operators alternate in the expression, because we only have binary operators? I.e. this would not work for real Scala, which also has unary operators, right? – Paŭlo Ebermann Oct 4 '20 at 23:36
• I had to use a less golfier algorithm to do that, which for posterity I've kept along with my golfier version that only handles the specific characters requested. – Neil Oct 5 '20 at 9:53

# Jelly, 59 bytes

Ḳ¹ƇµḊm2ZḢeⱮ€ØẠṭ“*/%“+-“:“=!“<>“&“^“|”¤i€1ỤḢḤ+-,2œṖ⁸W€2¦ẎµÐL


A monadic Link accepting a list of characters which yields a list containing the bracketed expression as nested lists of [expr, op, expr] where expr and op are lists of characters.

Try it online!

### How?

Ḳ¹Ƈµ...µÐL - Link: list of characters, E
Ḳ          - split at spaces
Ƈ        - keep those which are truthy under:
¹         -   identity (falsey for empty lists)

Ḋm2ZḢeⱮ€ØẠṭ“...”¤i€1ỤḢ - link, wrap three at highest precedence operator: list
Ḋ                      - deueue
m2                    - mod-2 slice -> gets operators
Z                   - transpose
Ḣ                  - head -> first characters of operators
ØẠ             -   letters "A..Za..z"
“...”       -   ["*/%","+-",":","=!","<>","&","^","|"]
ṭ            -   tack -> ["*/%","+-",":","=!","<>","&","^","|","A..Za..z"]
€               - for each (1st character):
Ɱ                -   map accross (the lists of characters) with:
e                 -     exists in?
i€1   - first (1-based) index of 1 in each (0 if no 1 found)
Ụ  - grade-up (list of 1-based indices sorted by value)
- continued below...

Ḥ+-,2œṖ⁸W€2¦Ẏ          - ...continued
Ḥ                      - double -> index, I, of operator in original list
-,2                  - [-1,2]
+                     - add -> [I-1, I+2]
⁸               - chain's left argument, the list
œṖ                - partition (the list) at indices ([I-1, I+2])
€2¦           - apply to the secod element (the [expr, op, expr])
W              - wrap in a list
Ẏ          - tighten


# JavaScript (ES6),  180 ... 155  152 bytes

Returns a multidimensional list. The outermost expression is parenthesized, and so are the atoms.

f=(i,a=i.split(/ +/))=>"w | ^ & <> =! : +- */%".split .some(p=>a.map((s,j)=>i=!!s.match(^[\${p}])&j?j:i)|i)?[f(i=a.splice(i),a),i.shift(),f(a,i)]:a  Try it online! ### How? This is a recursive algorithm. At each iteration, we look for the last operator with the lowest precedence, split the expression at this position and process recursive calls on both resulting parts. We stop the recursion when we reach an atom. In order to split the expression and isolate the operator, we use a combination of splice() and shift() as shown in the following example, where integers are used instead of operators and operands. a = [ 0, 1, 2, 3, 4, 5, 6 ]; i = 3; i = a.splice(i); // --> a[] = [ 0, 1, 2 ] (left expression) // i[] = [ 3, 4, 5, 6 ] (operator + right expression) i.shift(); // --> operator = 3 // i[] = [ 4, 5, 6 ] (right expression)  ### Commented f = ( // f is a recursive function taking: i, // i = input string on the 1st iteration, // and then some non-empty array a = i.split(/ +/) // a[] = input string split on spaces ) => // NB: operators are expected at odd positions "w | ^ & <> =! : +- */%" // this string describes the groups of operators, // from lowest to highest precedence .split  // split it .some(p => // for each pattern p: a.map((s, j) => // for each string s at position j in a[]: i = // update i: !!s.match( // see if s matches p; the '\' is required for ^[\${p}]      //       'w' and '^', and harmless for the other ones
) & j ?            //       if there's a match and j is odd:
j                //         update i to j
:                  //       else:
i                //         leave i unchanged
)                      //   end of map()
| i                    //   make some() succeed if i is a number
) ?                      // end of some(); if successful:
[                      //   build a new array consisting of:
f(                   //     the result of a recursive call ...
i = a.splice(i), a //     ... with the left expression
),                   //
i.shift(),           //     followed by the operator
f(                   //     followed by the result of a recursive call ...
a, i               //     ... with the right expression
)                    //
]                      //   end of new array
:                        // else:
a                      //   just return a[]


# Retina, 111 bytes

,2,\S+
{$&} ~(K*/%¶-+¶:¶!=¶<>¶&¶\^¶|¶\w )L$.+
+0{([^{}]+)}( +[$&][^ {}]$* +){([^{}]+)}¶{($$1)$$2($$3)} {|}  Try it online! Link includes test cases and a parenthesis-removing footer. Explanation: ,2,\S+ {&}  Wrap only the variables in braces. ~( )  Evaluate the enclosed stages and execute the result as a script on the wrapped input. K*/%¶-+¶:¶!=¶<>¶&¶\^¶|¶\w  Temporarily replace the input with a list of character classes. Note that -+ in particular is in that order because of the way character classes work. The character classes are listed in descending order of priority. L.+  Loop over each character class in the list. +0{([^{}]+)}( +[&][^ {}]* +){([^{}]+)}¶{($$1)$$2($$3)}


Find the first operator beginning with that class, wrap its parameters in parentheses, and wrap the subexpression in braces.

{|}



Remove the now enclosing braces.

The actual generated code looks like this:

+0{([^{}]+)}( +[\w][^ {}]* +){([^{}]+)}


Match a braced term, then the operator, then another braced term.

{($1)$4($5)}  Wrap the terms on both sides of the operator in parentheses, and wrap the subexpression in braces. Previous 126-byte version accepted any character not one of space, parentheses or previously defined operator character as an operator of the highest precedence: .+ ($&)
~(Ka-z¶|¶\^¶&¶<>¶!=¶:¶-+¶*/%¶^ ()
L$.+ +0i$$((([^ ()]+ +){2})*[^ ()]+)( +[&][^ ()]* +)([^()]+)$$¶(($$1)$$4($$5))  Try it online! Link includes test cases and a parenthesis-removing footer. Explanation: .+ (&)  Wrap the entire expression in parentheses. ~(  Evaluate the remaining stages and execute the result as a script on the wrapped input. Ka-z¶|¶\^¶&¶<>¶!=¶:¶-+¶*/%¶^ ()  Temporarily replace the input with a list of character classes. Note that -+ in particular is in that order because of the way character classes work. The character classes are listed in ascending order of priority. L.+  Loop over each character class in the list. +0i$$((([^ ()]+ +){2})*[^ ()]+)( +[&][^ ()]* +)([^()]+)$$¶(($$1)$$4($$5))  Find the largest possible sub expression that contains an operator beginning with that class and wrap both of the arguments in parentheses. The actual generated code looks like this: +0i$$((([^ ()]+ +){2})*[^ ()]+)( +[a-z][^ ()]* +)([^()]+)$$  Match a (, then an even number of terms, then a term, then the operator, then any remaining terms, then a ). (($1)$4($5))


Wrap the terms on both sides of the operator in parentheses.

# Perl 5, 292149 137 bytes

(last 12 bytes lost with tip from Nahuel Fouilleul in comments below)

sub{$_=pop;s/ +/ /g;for$o(qw(\*\/% +- : =! <> & \^ | \w)){1while s/\S+ +[$o]\S* +\S+/push@s,$&;"$#s,"/e}1while s/\d+,/($s[$&])/;/.(.*)./}  Try it online! sub {$_=pop;                             #put input string in $_ s/ +/ /g; #trim away unneeded spaces for$o (                            #loop through operators
qw(\*\/% +- : =! <> & \^ | \w)    #...in order of precedence
) {