Last active
August 5, 2017 14:43
-
-
Save shawa/3f3bb46ab478512acd473de42f324555 to your computer and use it in GitHub Desktop.
Checking bracket balances and nesting depth
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
⍝ extract only the parentheses from the character array ⍵ | |
⍝ | |
⍝ parens 'aa(bb)cc' | |
⍝ '()' | |
parens ← {(⍵∊'()')/⍵} | |
⍝ from a character array containing only '(' and ')', | |
⍝ map '(' to 1, and ')' to ¯1 | |
⍝ | |
⍝ open_close '()' | |
⍝ 1 ¯1 | |
open_close ← {('()'⍳⍵)⊃1 ¯1} | |
⍝ return 1 if the sum scan of ⍵ never falls below zero | |
⍝ return 0 otherwise | |
⍝ (if 1 and ¯1 represent open and close parens, the sum | |
⍝ scan of ⍵ is the nesting depth at each point in the array) | |
⍝ | |
⍝ never_neg ¯1 ¯2 3 | |
⍝ 0 | |
⍝ never_neg 1 1 ¯2 | |
⍝ 1 | |
never_negb ← {0=+/0>+\⍵} | |
⍝ return 1 if ⍵ sums to zero, i.e, if 1 and ¯1 represent | |
⍝ appearances of '(' and ')', respectively, that the number | |
⍝ of occurrences of each are the same | |
cancellation ← {0=+/⍵} | |
⍝ thus a character array has balanced brackets if | |
⍝ ∘ the number of occurrences of '(' and ')' is equal | |
⍝ ∘ the nesting depth never falls below zero | |
balanced ← {cancellation ir ∧ never_neg (ir ← open_close parens ⍵)} | |
⍝ the max nesting depth is just the max reduction of the | |
⍝ sum scan of the 1 ¯1 representation of ⍵, as before | |
max_nesting_depth ← {⌈/ +\ open_close parens ⍵} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Although parens could be written more simply as
parens←{⍵
⍵'()'}... forget that,
parens ← ∩∘'()'
Parens and open_close can be combined:
delta_depth← {'()'⍳⍵⊃1 ¯1 0 }
(typo?) never_negb is defined, but mentioned as never_neg, without the b.
balanced could use a fork, although I understand the desire for clarity via verbosity in this context:
(cancellation∧never_neg)∘delta_depth