Попытка написать алгоритм, который определяет, верна ли строка скобок

Question

Я сделал кусок кода, чтобы проверить, действительна ли строка круглых скобок. Я думал, что буду считать открывающие скобки и помещать их в массив. после этого, если бы была закрывающая скобка, я бы заменил открывающую скобку в массиве чем-то еще, например буквой A. После всего этого я бы проверял, все ли символы в массиве были буквой A. Это не это действительно не кажется эффективным, и у меня еще нет кода для работы. Кажется, у меня нет синтаксических ошибок, но я, похоже, получаю исключение нулевого указателя в строке 26 моего кода:

if(!(arrays[i].equals("A"))).

Вот: весь кусок кода для оценки:

public class Parenth {
    public boolean validParentheses(String parens){
          int count=0;
        String[] arrays= new String[parens.length()];
          if(parens.substring(0,1).equals(")"))
             {
             return false;
             }
          for(int i=0;i<parens.length();i++)
            {
            if(parens.substring(i,i+1).equals("("))
              {
               arrays[count]= parens.substring(i,i+1);
               count++;
              }
            if(parens.substring(i,i+1).equals(")"))
              {
                arrays[count-1]= "A";
              }
             }
          for(int i=0;i<arrays.length;i++)
            {
            if(!(arrays[i].equals("A")))
                {
                  return false;
                }
            }
          return true;
        }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
Parenth a = new Parenth();
a.validParentheses("()()()()()");
    }

}
 

Answer 1

Используйте стековую структуру данных:

Stack<Character> stack = new Stack();
char[] str = s.toCharArray();
    
for (int i = 0; i < str.length; i++) {
    if (str[i] == '(') {
        stack.push(str[i]);
    } else {
        if (str[i] == ')') {
            if (stack.isEmpty() || stack.pop() != '(') return false;
        }
    }
}
return stack.isEmpty();

Answer 2

Намного более простой вариант - подсчитать все открывающие скобки и все закрывающие скобки и проверить, совпадают ли они с одним и тем же значением.

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

public boolean validParentheses(String parens) {

    int firstClosingIndex = parens.indexOf(")");
    int firstOpeningIndex = parens.indexOf("(");
    if (firstClosingIndex < firstOpeningIndex && firstClosingIndex != -1) {
        return false;
    }

    int openingBrackets = 0;
    for (int i = 0; i < parens.length(); i++) {
        if (parens.charAt(i) == '(') {
            openingBrackets ++;
        }
    }

    int closingBrackets = 0;
    for (int i = 0; i < parens.length(); i++) {
        if (parens.charAt(i) == ')') {
            closingBrackets ++;
        }
    }
    
    return closingBrackets == openingBrackets;
}