Ways of defining a recursive function that counts right-parentheses in a string

Question

I'm trying to find a more elegant way of defining a recursive function on $\{(,)\}$ that counts right-parentheses in a string.

Let $r$ be a function on $\{(,)\}$ defined recursively, such that:

• $r(\lambda) = 0$, and
• $r(sx) = r(s) + 1$, if x is symbol )
• $r(sx) = r(s)$, if x is symbol (

I have also found another way of saying the same thing:

Leg r be a function $\{(,)\}$ defined recursively, such that:

• $r(\lambda) = 0$, $r\left(\mathbf(\right) = 0$, $r\left(\mathbf)\right) = 1$, and
• $r(sx) = r(s) + r(x)$, where x is a symbol

Is the last example correct? Is there anybody who can recommend a better way of defining this?

Answer 1

The two definitions are equivalent. I agree with the commenter that the first form is more intuitive.

The only change I could suggest would be a typesetting/presentation change to the following:

Define $r(s)$ recursively by $r(\lambda) = 0$, and $$r(sx) = \begin{cases} r(s) +1 & \text{if } x=\mathbf{)}\\ r(s) & \text{otherwise} \end{cases}$$ (where $x$ is a character/symbol)

By using "otherwise" instead of "if $x=\mathbf($", it is abundantly clear that $\mathbf{)}$ is the only character we care about. This also extends the definition to work for larger alphabets than $\{(, )\}$.