# Matching parentheses

Consider finding pairs of balanced parentheses in a string such as
`"()(()())((()))"`

consisting entirely of open and closing
parentheses. This problem has an elegant parallel solution. We’ll
assume that the string is indeed balanced - *checking* whether that
is the case, or also allowing non-parenthesis characters, is a
fairly easy extension.

First we define a function for finding the nesting depth of each character.

```
def depths [n] (s: [n]u8) : [n]i32 =
let depth = scan (+) 0 (map (\c -> if c == '(' then 1 else -1) s)
in map2 (\c d -> d - if c == '(' then 1 else 0) s depth
```

`> depths "()(()())((()))"`

`[0i32, 0i32, 0i32, 1i32, 1i32, 1i32, 1i32, 0i32, 0i32, 1i32, 2i32, 2i32, 1i32, 0i32]`

Next, we define a function that gives the sorting order of an array
of integers. Although we will use a previously defined radix
sort as a building block, this is not the
same as a sorted array! We use the name `grade`

for this function,
inspired by APL:

```
import "radix-sort-key"
def grade xs =
zip (map u32.i32 xs) (indices xs)0)
|> radix_sort (.1) |> map (.
```

For an array `A`

, the result `grade A`

tells us the order in which
to index `A`

to obtain the sorted array.

`> grade [5,0,1,3,2,4]`

`[1i64, 2i64, 4i64, 3i64, 5i64, 0i64]`

Finally, with the help of a small auxiliary function for permuting arrays, we can finish our implementation of parentheses matching.

```
def permute xs is = scatter (copy xs) is xs
def match_parens [n] (s: [n]u8) =
let depth = depths s
let rnk = grade depth
let ret = tabulate n (\i -> if i % 2 == 0 then rnk[i+1] else rnk[i-1])
in permute ret rnk
```

The function returns, for each parenthesis in the input string, the index of its counterpart.

`> match_parens "()(()())((()))"`

`[1i64, 0i64, 7i64, 4i64, 3i64, 6i64, 5i64, 2i64, 13i64, 12i64, 11i64, 10i64, 9i64, 8i64]`