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