creating parallel processing of parenthesis balancer

I am attending coursera scala course for parallel programming. I have an assignment to solve paranthesis balancer both sequential and parallel. I have solved the sequential function. For the parallel function I have doubts as to how I can maintain the current paranthesis data across parallel threads.

Here is my sequential function:

def balance(chars: Array[Char]): Boolean = {

    def helper( arr: Array[Char], acc: Int): Boolean = {
      if (arr.isEmpty && acc ==0)
        true
      else if (arr.isEmpty  || arr.head == ')' && acc <=0)
        false
      else if (arr.head == '(')
        helper( arr.tail,  acc +1)
      else if (arr.head == ')' )
        helper( arr.tail,  acc - 1)
      else
        helper(arr.tail, acc)
    }

    helper(chars, 0)
  }

now, my whole logic is based on acc value. When I will run these across multiple threads, what should I be focusing on? The parallel method will have range start and end index. The only thing I have understood so far is that aggregate of all these operations should be acc==0.

Please let me know some pointers in this direction.

Thanks

Due to Coursera rules, I won't give you exact solution, but rather give some advises.

As I remember this assignment advises you to use two values in recursion result. Typically students decide that this is the count of "(" and count of ")", but the correct solution is another one. You should compute two values on each recursion step:

1. Delta of current step= countOf "(" - countOf ")"
2. Minimum "depth" of current step. I.e. minimum value of delta, if try to traverese left-to-right on current chunk. It can be lower then delta.

Few examples (imagine this is some intermediate step): "(())" : delta = 0, minDepth = 0 ")))(" : delta = -2, minDepth = -3

Then, after doing typical parallel traverse, you will need to correctly reduce these two values. This you will easily guess by yourself.

You will finally get (0,0) if balanced.

And for example case ")(" will give you (0,-1)