Определить, если число открытых скобок "(" равно закрывающим скобкам ")"

Question

Задана строка в следующем формате:

"(1 AND (2 OR 3) AND 4)"

Какой самый быстрый способ определить, совпадает ли число «открытых» скобок »(« равно «закрывающим» скобкам »)» .

ПРИМЕЧАНИЕ: Длина строки может составлять несколько сотен символов.

Answer 1

Просто используйте простой счетчик, который начинается с 0.

Когда вы встречаете "(", увеличивайте его на единицу. Когда вы встречаете ")", уменьшайте на единицу.

Если в конце счетчик не равен 0, значит, имеется несоответствие.

Кроме того, как уже упоминали другие, если счетчик становится отрицательным, это означает, что возникла такая ситуация, как )(. Сообщить об ошибке и прекратить дальнейший анализ.

Answer 2

1. Инициализировать счетчик на ноль.

2. Перебор символов строки.

   а. На открывающей скобке увеличьте счетчик.

   б. На закрывающей скобке уменьшите счетчик.

   с. Ошибка, если счетчик отрицательный.

3. Ошибка, если счетчик не равен нулю после цикла.

Это также отлавливает такие случаи, как )(, в которых есть одинаковое количество открывающих и закрывающих паренов, но в любом случае, вероятно, их следует считать ошибочными.

Answer 3

Если вы пытаетесь посчитать, что число ( совпадает с числом ), просто пропустите строку после сохранения счетчиков, увеличивая, если вы видите (, и уменьшая, если вы видите ). Это O(n), и вы не можете сделать лучше; Вы должны проверять каждого персонажа.

Однако я подозреваю, что вы хотели задать другой вопрос. А именно, как вы скажете, если баланс ( равен ). В этом случае вы поддерживаете стек и толкаете каждый раз, когда видите (, и вы всплываете, когда видите ). Если вы когда-нибудь попытаетесь всплыть, когда стек пуст, скобки не сбалансированы. Если при достижении конца входной строки стек не пуст, скобки не сбалансированы.

Конечно, вы можете просто имитировать это с помощью счетчика, но об этом более естественно думать с точки зрения стека.

Answer 4

:) Вы можете

int left = "your string".split("(").length()
int right = "your string".split(")").length()
boolean ok = (left == right)

Конечно, это глупо, но это просто другой способ

Answer 5

Это O (n).Обойти это невозможно.Вот грубая идея.

For i=0 to string.length
   if string[i] == ')'
        add to rightBracketCount
   else if string[i] == '('
        add to leftBracketCount
end for

сравнить rightBracketCount с leftBracketCount