Welcome everyone to APL Seeds episode 3!
Last time we were able to "compile" the APL-syntax expression 3+√2×8 to the reverse Polish 328×√+.
Today we are going to handle parentheses, so we'll now do the more complicated expression ((-3)+√(3×3)-4×2×1)÷2×2.
We're only shuffling the terms around, so there's actually a part missing in that we won't keep track of how many arguments each function has.
So in the output, both -s will appear the same even though one is monadic and one is dyadic.
Here's the code we had last time, in BQN:
x←"3+√2×8"
f←¬x∊•d
l←≠x
x⊏˜(↕l)+(f×l-↕l)-+`f
x←'3+√2×8'
f←~x∊⎕d
l←≢x
x[⍋(⍳l)+(f×l-⍳l)-+⍀f]
The idea here is that we push every function forward to the end of the expression (l), and compensate by moving everything it goes past backwards by 1 (-+`f).
When we have parentheses, we instead want to push every function up to the containing closing parentheses, or the end if it's at the top level.
So I want to find the index of the closing parenthesis for every character in the expression.
The idea here is similar to what we did in the first APL Seeds. We are going to sort the whole expression by nesting depth.
I'm starting with these definitions, which are the same as above with a different expression:
x←"((-3)+√(3×3)-4×2×1)÷2×2"
l←≠x
f←¬x∊•d
Let's find masks for the opening and closing parentheses, and the nesting depth.
o←x='(' ⋄ c←x=')' ⋄ d←+`o-c
The depths are [ 1 2 2 2 1 1 1 2 2 2 2 1 1 1 1 1 1 1 0 0 0 0 0 ].
Now we can sort our expression using (⍋d)⊏x
which gives [ )÷2×2()+√)-4×2×1(-3(3×3 ].
This expression looks fairly confusing at first, since the parens aren't paired any more. Since the depth increases and decreases at/before each paren, the opening paren is considered to be inside the pair but the closing paren is outside.
So the closing paren gets left behind when we do this sorting. That's actually good, because we now have a record of where the expression belongs.
On the other hand, the open paren always ends up at the beginning of the expression in parens when sorting. It serves as a marker of the beginning of a subexpression.
To see what's happening better, we can split the expression based on open parens with '('(+`∘=⊔⊢)(⍋d)⊏x.
[ [ )÷2×2 ] [ ()+√)-4×2×1 ] [ (-3 ] [ (3×3 ] ]
To find the containing closing parenthesis, I want to find which expression each character belongs to. In the format above, this is easy because expressions are contiguous. I just need to find the number of open parens before the character.
This is just the prefix sum +`(⍋d)⊏o.
We can visualize with (g⊏x)≍(+`g⊏o):
┌
) ÷ 2 × 2 ( ) + √ ) - 4 × 2 × 1 ( - 3 ( 3 × 3
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 3 3 3
┘
Now to go back to the original expression, we have to undo our depth sorting. We could use ⍋g to select from the depth, but in BQN we have a nice tool called structural Under for this.
[ 1 2 2 2 1 1 1 3 3 3 3 1 1 1 1 1 1 1 0 0 0 0 0 ]
g⊸⊏ is the function that permutes by g, and +`⌾(g⊸⊏) does a prefix sum under this permutation.
Now to put it next to the original code, use x≍+`⌾(g⊸⊏)o:
┌
( ( - 3 ) + √ ( 3 × 3 ) - 4 × 2 × 1 ) ÷ 2 × 2
1 2 2 2 1 1 1 3 3 3 3 1 1 1 1 1 1 1 0 0 0 0 0
┘
We have identified which set of parentheses each character belongs to, by index. Does that idea make sense?
