Задача о корректности расстановки скобок

05/04/2020

Хочется рассказать о такой задаче, как определение корректности расстановки скобок. Она так же известна, как 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...Sn — n строк из которых состоит исходная строка 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)
}

izebit