Как проверить, сбалансирован ли вектор строки?

Question

У меня есть следующий алгоритм, чем проверить, если строка сбалансирован

bool IsBalanced(string input) 
{ 
    int count = 0; 
    for (int i = 0; i < input.size(); i++) 
    { 
     if (input[i] == '(') count++; 
     if (input[i] == ')') count--; 
     if (count < 0) return false; 
    } 
    if (count == 0) return true; 
    return false; 
} 

Как использовать этот метод, чтобы проверить, если vector<string> сбалансирован?

vector<string> VectorOfBalanced(vector<string> values) 
{ 
} 

Пример ввода:

values = { "{}[]()", "{[}]}" } 

Пример вывода

return = { "YES", "NO" }` 

Answer 1

Ваш вопрос состоит из двух Партер: как проверить, если строка сбалансирован относительно нескольких наборов открытия/закрытия символы, такие как «()», «{}» и «[]», а затем как это расширить для вектора строк.

Последняя часть проста: просто повторите алгоритм для каждой строки в векторе.

Для первой части вам необходимо отслеживать список всех выдающихся открывающих символов в виде стека. A std::vector<char> будет отличным выбором:

1. Инициализировать стек до пустого.
2. Итерации над каждым символом в строке для проверки.
3. Если символ является одним из символов открытия, например '(', '[' или '{', то нажмите его в стек.
4. Если символ является одним из символов закрытия, например ')' , ']' или '}', тогда: тогда и только тогда, когда стек не пуст, а символ в конце стека соответствует совпадающему символу открытия, затем выталкивает его из стека и продолжает свою итерацию. В противном случае строка не сбалансирована.
5. Если после завершения итерации стек не пуст, строка не сбалансирована.

Вы должны иметь возможность тривиально перевести вышеуказанный код на C++.

Answer 2

Это руководство для вас больше, чем фактический ответ. Вам нужно искать std::stack, и простой способ сделать это - каждый раз, когда вы видите открытые { [ (, вы делаете YourStackName.push(), и как только увидите закрытые, вы делаете YourStackName.pop(). Тем не менее, вам нужно поддерживать свою логику (не тяните, если она пуста, на каком персонаже нажать, может быть, три стека для трех типов и т. Д.)

Итак, в конце вы просто проверяете, YourStackName.Empty() и если это, тогда хура это было сбалансировано!

Answer 3

Как использовать этот метод для проверки того, сбалансирован ли вектор?

Вы можете использовать регулярный цикл, но в C++ у нас есть более общие алгоритмы, такие как std :: transform.

Я предполагаю, что ваш вопрос не в том, правильно ли IsBalanced, но как применить его к вектору строк.

vector<string> res; 
std::transform(
    values.begin(), values.end(), 
    std::back_inserter(res), 
    [](auto& s) -> auto { return IsBalanced(s) ? "Yes" : "No"; });