Skip to content

Instantly share code, notes, and snippets.

@shawa
Last active August 5, 2017 14:43
Show Gist options
  • Save shawa/3f3bb46ab478512acd473de42f324555 to your computer and use it in GitHub Desktop.
Save shawa/3f3bb46ab478512acd473de42f324555 to your computer and use it in GitHub Desktop.
Checking bracket balances and nesting depth
⍝ 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 ⍵}
@arraymac-rogers
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment