Search code examples
smlsmlnj

Checking for matching parenthesis

I am trying to write a code such that, given a list of parenthesis, I will check if the order is valid or not.

For simpleness, the follwoing datatype is defined. 

datatype par = LPAR | RPAR
 type pList = par list

What I have until now is: 

fun valid(nil:plist): bool = true
| valid([Lpar]) = false
| valid([Rpar]) = false
| valid([Lrap,Rpar) = true
| valid(L::L1) =

For instance, "(()()"--> [Lpar,Lpar,Rpar,Lpar,Rpar] will return false You can see that the parenthesis is in string format. I am confused since I will have to check to two things: that the left ( are equal to the left ) and that each ( matches a ). If so then I will need to make some helper functions.

Can you please provide me with information about what my helper functions should be or a better implementation of this? ty

Solution

  • I didn't try this in the repl but it should look something like this

    fun valid_paren xs : bool = 
fun aux (xs, ctr) = case xs of
    [] => ctr = 0
  | (x:xs') => case x of 
           '(' => aux (xs', ctr+1)
           ')' => aux (xs', ctr-1)
            _  => aux (xs', ctr)
in
  aux (xs, 0)