Хочется рассказать о такой задаче, как определение корректности расстановки скобок. Она так же известна, как balanced parenthesis problem. Суть ее в следующем: дана строка, содержащая открывающиеся и закрывающиеся скобки, и какие то другие символы. Нужно узнать правильно ли расставлены скобки. Т.е. для каждой открывающейся скобки должна быть закрывающаяся. Например, строки вида (()) или (()()) содержат корректную расстановку, а (()() и )()( уже нет.

Существует несколько решений. Самое очевидное из возможных, это использование стека. Т.е. проходя по строке, складывать в стек все открывающиеся скобки. Если встречаемый символ не скобка, то его пропускаем. Если встречается закрывающаяся, то возможны два варианта:

  • стек пустой, тогда очевидно, что скобки расставлены некорректно.
  • стек непустой, тогда нужно удалить из него один элемент.

Если достигается конец строки и стек оказывается не пустой, то мы получили ситуацию, когда для одной или нескольких открывающих скобок недостает закрывающихся скобок.

Код решения довольно прост:

public static boolean isCorrect(String str) {
  Stack<Character> stack = new Stack<>();
  for (int i = 0; i < str.length(); i++)
     if (str.charAt(i) == '(')
       stack.push('(');
     else if (str.charAt(i) == ')') {
       if (stack.isEmpty())
         return false;
       stack.pop();
     }

  return stack.isEmpty();
}

Так же, можно решить эту задачу с использованием счетчика. Ход решения следующий: завести переменную и каждый раз ее увеличивать, если встречается открывающаяся скобка, закрывающаяся — уменьшать. Если, в момент ее уменьшения, она становится меньше нуля, то эта свидетельствует о несбалансированности расстановки скобок. После прохождения по строке, проверяем, значение счетчика. Оно должно быть равно нулю, если это не так, то расстановка скобок некорректна. С помощью рекурсии, это легко реализуется:

def isCorrect(str: String): Boolean = {
  @tailrec
  def isCorrect(index: Int, result: Int): Boolean = {
    if (str.length == index)
      return result == 0

    str(index) match {
      case '(' => isCorrect(index + 1, result + 1)
      case ')' => result - 1 >= 0 && isCorrect(index + 1, result - 1)
      case _ => isCorrect(index + 1, result)
    }
  }

  isCorrect(0, 0)
}

И напоследок, предлагаю рассмотреть многопоточный вариант.

Основная идея заключается в следующем — для любого префикса строки, количество открывающихся скобок не меньше, чем количество закрывающихся скобок в остальной строке. Общее же число открывающихся скобок должно быть равно числу закрывающихся.

Здесь потребуется более подробное объяснение.

Возьмем S1,S2,S3...Snn строк из которых состоит исходная строка S. Т.е. конкатенация этих строк S1+S2+S3+...+Sn = S составляет первоначальную строку. У каждой строки S с номером i есть два числа — финальное значение finalValue и наименьшее значение minValue. Вычисляются они следующим образом:

Так же как и в решении со счетчиком, мы заводим переменную value = 0. Если встречаем ( то увеличиваем на 1, если ) то уменьшаем. В результате получаются значения finalValue = value, а minValue = минимальное value, которое было в процессе обработки.

Таким образом, должно выполняться неравенство sum (j = от 1 до i-1) finalValue(j) + min(i) >=0 и sum(j = от 1 до n) finalValue(j) = 0

Код решения на языке Scala:

def parIsCorrect(str: String) = {
  val threshold = 100

  def traverse(start: Int, end: Int): (Int, Int) = {
    var finalValue = 0
    var min = 0

    var i = start
    while (i < end) {
      if (str(i) == '(')
        finalValue += 1
      else if (str(i) == ')')
        finalValue -= 1

      min = Math.min(finalValue, min)
      i += 1
    }

    (min, finalValue)
  }

  def reduce(start: Int, end: Int): (Int, Int) = {
    if (end - start <= threshold)
      traverse(start, end)
    else {
      val middle = (end + start) / 2

      val firstTask = new Callable[(Int, Int)] {
        override def call(): (Int, Int) = reduce(start, middle)
      }
      val secondTask = new Callable[(Int, Int)] {
        override def call(): (Int, Int) = reduce(middle, end)
      }

      val results = ForkJoinPool.commonPool().invokeAll(List(firstTask, secondTask))

      val r1 = results(0).get()
      val r2 = results(1).get()

      var finalValue = 0
      var minValue = 0
      minValue = Math.min(minValue, finalValue + r1._1)
      finalValue += r1._2
      minValue = Math.min(minValue, finalValue + r2._1)
      finalValue += r2._2

      (minValue, finalValue)
    }
  }

  reduce(0, str.length) == (0, 0)
}