Valid Parens method - Java

Question

Может ли кто-нибудь предложить лучший оптимизированный способ решить эту загадку для кодирования? Я использовал кучу утверждений if, и мне сказали, что просто увеличена циклическая сложность. Является ли решение регулярным выражением или структурой данных (например, стеком)? Любая обратная связь очень ценится.

/** 
* Write a function that will take a string as input and output 
* a boolean (true or false) that describes if the string has valid parens. 
* 
* Use Cases: 
* 
* "" -> false 
* 
* null -> false 
* 
* "()" -> true 
* 
* ")" -> false 
* 
* "(" -> false 
* 
* "(())" -> true 
* 
* "())(" -> false 
* 
* "()))" -> false 
* 
* ")(" -> false 
* 
* "()()" -> true 
*/ 
public boolean validParen(String input) { 
    // implementation? 
} 

Answer 1

Вам просто нужен счетчик.

Если ввод пустой или пустой строки, верните false.

Затем итерации символов строки и приращение счетчика, когда вы видите (, и уменьшите счетчик, когда увидите ).

Если вы видите ), а счетчик равен нулю, верните значение false.
Если счетчик не равен нулю в конце, верните значение false.
В противном случае верните true.

Answer 2

Чтобы проверить, действительны ли скобки (попарно), вам не нужна структура данных. Просто увеличивайте переменную счетчика, когда вы сталкиваетесь с (и уменьшаете ее при обнаружении пары). В конце счетчик должен = 0, если (а) уравновешены:

static boolean check(String toCheck) { 
    if (toCheck == null || toCheck.equals("")) 
     return false; 
    int count = 0; 
    for (int i = 0; i < toCheck.length(); i++) { 
     char c = toCheck.charAt(i); 
     if (c == '(') { 
      count++; 
     } else if (c == ')') { 
      if (count == 0) 
       return false; 
      count--; 
     } 
    } 
    return count == 0; 
}