Рубрики

Проверить наличие сбалансированных скобок в выражении | O (1) пробел | O (N ^ 2) сложность времени

Учитывая строку str, содержащую символы '(' , ')' , '{' , '}' , '[' и ']' , задача состоит в том, чтобы определить, сбалансированы ли скобки или нет.
Скобки сбалансированы, если:

  1. Открытые скобки должны быть закрыты скобками того же типа.
  2. Открытые скобки должны быть закрыты в правильном порядке.

Примеры:

Input: str = “(())[]”
Output: Yes

Input: str = “))(({}{”
Output: No

Подходить:

  • Оставьте две переменные i и j, чтобы отслеживать две скобки для сравнения.
  • Ведите счет, значение которого увеличивается при обнаружении открывающей скобки и уменьшается при обнаружении закрывающей скобки.
  • Установите j = i , i = i + 1 и counter ++ при открытии скобок.
  • Когда встречаются закрывающие скобки, уменьшите счетчик и сравните скобки в i и j ,
    • Если скобки в i и j совпадают, то подставьте '#' в строке в i- й и j- й позиции. Увеличивайте i и уменьшайте j, пока не встретите значение, отличное от '#' или j ≥ 0 .
    • Если скобки в i и j не совпадают, вернуть false.
  • Если count! = 0, вернуть false.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// Эта вспомогательная функция вызывается всякий раз, когда
// встречается закрывающая скобка.
// Отсюда уменьшается число
// j и i указывают на открытие и закрытие
// скобки для сопоставления соответственно
// Если скобки в i и j совпадают
// заменим их символом "#" и уменьшим j
// чтобы указать следующую открывающую скобку для соответствия *
// Аналогично, приращение i указывает на следующее закрытие
// скобка для сопоставления
// Если j выходит за пределы или скобки не совпадают, возвращаем 0

bool helperFunc(int& count, string& s, int& i, int& j, char tocom)

{

    count--;

    if (j > -1 && s[j] == tocom) {

        s[i] = '#';

        s[j] = '#';

        while (j >= 0 && s[j] == '#')

            j--;

        i++;

        return 1;

    }

    else

        return 0;

}

  
// Функция, которая возвращает true, если s является
// допустимая строка сбалансированной скобки

bool isValid(string s)

{

  

    // Пустая строка считается сбалансированной

    if (s.length() == 0)

        return true;

  

    else {

        int i = 0;

  

        // Приращения для открывающей скобки и

        // декременты для закрывающей скобки

        int count = 0;

        int j = -1;

        bool result;

        while (i < s.length()) {

            switch (s[i]) {

            case '}':

                result = helperFunc(count, s, i, j, '{');

                if (result == 0) {

                    return false;

                }

                break;

  

            case ')':

                result = helperFunc(count, s, i, j, '(');

                if (result == 0) {

                    return false;

                }

                break;

  

            case ']':

                result = helperFunc(count, s, i, j, '[');

                if (result == 0) {

                    return false;

                }

                break;

  

            default:

                j = i;

                i++;

                count++;

            }

        }

  

        // count! = 0 указывает на несбалансированные скобки

        // эта проверка необходима для обработки случаев, когда

        // количество открывающих скобок> закрывающих скобок

        if (count != 0)

            return false;

  

        return true;

    }

}

  
// Код драйвера

int main()

{

    string str = "[[]][]()";

  

    if (isValid(str))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

python3

# Python3 реализация подхода

  
# Они определены как глобальные, потому что они
# передаются по ссылке

count = 0

i = 0

j = -1

  
# Эта вспомогательная функция вызывается всякий раз, когда
# встречается закрывающая скобка.
# Следовательно, количество уменьшается
# j и i указывает на открытие и закрытие
# скобки для сопоставления соответственно
# Если скобки в i и j совпадают
# замените их символом "#" и уменьшите j
# чтобы указать следующую открывающую скобку, чтобы она * соответствовала
# Аналогично, приращение i указывает на следующее закрытие
# скобка для сопоставления
# Если j выходит за границы или в скобках
# не соответствует return 0

def helperFunc(s, tocom):

    global i, j, count

    count -= 1

    if j > -1 and s[j] == tocom:

        s[i] = '#'

        s[j] = '#'

        while j >= 0 and s[j] == '#':

            j -= 1

        i += 1

        return 1

    else:

        return 0

  
# Функция, которая возвращает true, если s является
# допустимая строка сбалансированных скобок

def isValid(s):

    global i, j, count

  

    # Пустая строка считается сбалансированной

    if len(s) == 0:

        return True

    else:

  

        # Приращения для открывающей скобки и

        # уменьшение для закрывающей скобки

        result = False

        while i < len(s):

            if s[i] == '}':

                result = helperFunc(s, '{')

                if result == 0:

                    return False

            elif s[i] == ')':

                result = helperFunc(s, '(')

                if result == 0:

                    return False

            elif s[i] == ']':

                result = helperFunc(s, '[')

                if result == 0:

                    return False

            else:

                j = i

                i += 1

                count += 1

  

        # count! = 0 указывает на несбалансированные скобки

        # эта проверка требуется для обработки случаев, когда

        # количество открывающих скобок> закрывающих скобок

        if count != 0:

            return False

        return True

  
Код водителя

if __name__ == "__main__":

    string = "[[]][]()"

    string = list(string)

  

    print("Yes") if isValid(string) else print("No")

  
# Этот код предоставлен
# sanjeev2552

Выход:

Yes

Рекомендуемые посты:

Проверить наличие сбалансированных скобок в выражении | O (1) пробел | O (N ^ 2) сложность времени

0.00 (0%) 0 votes