Parse a Scala expression

Question

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 code-golf, 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

Answer 1

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)
   µ...µÐL - repeat the monadic link (below) until no change occurs

Ḋ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
                ¤      - nilad followed by link(s) as a nilad:
        ØẠ             -   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)
                     Ḣ - head
                       - 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

Answer 2

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[]

Answer 3

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:

.+
($&)
~(K`a-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.

K`a-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.

Answer 4

Perl 5, 292 149 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
  ) {
    1 while s/\S+\s+[$o]\S*\s+\S+     #find first such operator and
             /push@s,$&; "$#s,"       #replace its sub-expression with
             /ex                      #a tag of id plus comma
                                      #and continue until no more
                                      #of current operator
  }
  1 while s/\d+,/($s[$&])/;           #replace all tags with their
                                      #subexpressions, now in parens
  /.(.*)./                            #remove first+last char, return rest
}

Answer 5

Charcoal, 82 68 67 bytes

≔⮌Φ⪪Ｓ ιθＦ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«Ｗ⊖Ｌθ¿№ι↥§§θ⊖κ⁰⊞θＥ³⊟θＦ²⊞υ⊟θＷυ⊞θ⊟υ»⭆θι

Try it online! Link is to verbose version of code. Outputs the Python representation of a nested list. Explanation:

≔⮌Φ⪪Ｓ ιθ

Split the input string on spaces and filter out empty strings (corresponding to runs of spaces). Reverse the result, so that the list can be processed by popping terms from it.

Ｆ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«

Concatenate the compressed literal string */%.-+.:.!=.<>.&.^.|. with the uppercase alphabet, split on .s, and loop over each character class.

Ｗ⊖Ｌθ

While there are operators left to process:

¿№ι↥§§θ⊖κ⁰

Does the uppercased current operator start with a character in the current class?

⊞θＥ³⊟θ

If so then extract the operator and its parameters into their own sublist, and then push that list back as the left parameter of the next operator.

Ｆ²⊞υ⊟θ

Otherwise move the operator and its left parameter to a temporary list.

Ｗυ⊞θ⊟υ

Once all of the operators have been processed move all the saved operators and parameters back to the main list, also emptying the temporary list again.

»⭆θι

Stringify the resulting list.

85 70 bytes for a human-readable format (with enclosing parentheses):

≔⮌Φ⪪Ｓ ιθＦ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«Ｗ⊖Ｌθ¿№ι↥§§θ⊖κ⁰⊞θ⪫()⪫Ｅ³⊟θ Ｆ²⊞υ⊟θＷυ⊞θ⊟υ»θ

Try it online! Link is to verbose version of code. Explanation: As above, but after extracting the three elements into an array, the array is joined with spaces and then wrapped in parentheses before being pushed back to the list, meaning that the final result can be directly printed.

Answer 6

Scala, 308 bytes

I am sure it is not the shortest way to do that, but here is a solution in Scala :)

s=>{def g(q:Seq[String]):String=if(q.size<2)q(0)else{val o=Seq("*/%","+-",":","!=","<>","&","^","|").zipWithIndex
val t=1.to(q.size-1,2).map(r=>o.map(a=>(r,if(a._1.contains(q(r)(0)))a._2 else 8))).map(_.minBy(_._2)).reverse.maxBy(_._2)._1
"("+g(q.take(t))+")"+q(t)+"("+g(q.drop(t+1))+")"}
g(s.split("\\s+"))}

Try it online!