Рубрики

Удалить неверные скобки

Будет дано выражение, которое может содержать открывающие и закрывающие скобки и, возможно, несколько символов. Никаких других операторов в строке не будет. Нам нужно удалить минимальное количество скобок, чтобы сделать входную строку действительной. Если возможно более одного допустимого вывода, удаляя одинаковое количество скобок, выведите все такие выходные данные.
Примеры:

Input  : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input  : str = (v)())()
Output : (v)()()  (v())()

Поскольку нам нужно сгенерировать все возможные выходные данные, мы вернемся назад между всеми состояниями, удалив одну открывающую или закрывающую скобку и проверим, действительны ли они, если недействительны, затем добавим удаленную скобку обратно и перейдем к следующему состоянию. Мы будем использовать BFS для перемещения по состояниям, использование BFS обеспечит удаление минимального количества скобок, потому что мы перемещаемся в уровни состояний по уровням, и каждый уровень соответствует одному удалению дополнительных скобок. Кроме этого BFS не требует рекурсии, поэтому накладные расходы на передачу параметров также сохраняются.
В приведенном ниже коде есть метод isValidString для проверки правильности строки, он считает открытые и закрытые круглые скобки при каждом индексе, игнорируя символ без скобок. Если в любой момент счетчик закрывающих скобок становится больше, чем открытый, то мы возвращаем false, иначе мы продолжаем обновлять переменную count.

C ++

/ * C / C ++ программа для удаления неверных скобок * /
#include <bits/stdc++.h>

using namespace std;

  
// метод проверяет, является ли символ круглой скобкой (open
// или закрыто)

bool isParenthesis(char c)

{

    return ((c == '(') || (c == ')'));

}

  
// метод возвращает true, если строка содержит valid
// скобка

bool isValidString(string str)

{

    int cnt = 0;

    for (int i = 0; i < str.length(); i++)

    {

        if (str[i] == '(')

            cnt++;

        else if (str[i] == ')')

            cnt--;

        if (cnt < 0)

            return false;

    }

    return (cnt == 0);

}

  
// метод для удаления неверных скобок

void removeInvalidParenthesis(string str)

{

    if (str.empty())

        return ;

  

    // посещение установлено, чтобы игнорировать уже посещенную строку

    set<string> visit;

  

    // очередь для поддержки BFS

    queue<string> q;

    string temp;

    bool level;

  

    // помещаем заданную строку в качестве начального узла в очередь

    q.push(str);

    visit.insert(str);

    while (!q.empty())

    {

        str = q.front();  q.pop();

        if (isValidString(str))

        {

            cout << str << endl;

  

            // Если ответ найден, сделать уровень истинным

            // так, чтобы действительная строка только этого уровня

            // обрабатываются.

            level = true;

        }

        if (level)

            continue;

        for (int i = 0; i < str.length(); i++)

        {

            if (!isParenthesis(str[i]))

                continue;

  

            // Удаление скобок из str и

            // вставляем в очередь, если еще не посетили

            temp = str.substr(0, i) + str.substr(i + 1);

            if (visit.find(temp) == visit.end())

            {

                q.push(temp);

                visit.insert(temp);

            }

        }

    }

}

  
// Код драйвера для проверки вышеуказанных методов

int main()

{

    string expression = "()())()";

    removeInvalidParenthesis(expression);

  

    expression = "()v)";

    removeInvalidParenthesis(expression);

  

    return 0;

}

Джава

// Java-программа для удаления неверных скобок

import java.util.*;

  

class GFG 

{

  
// метод проверяет, является ли символ круглой скобкой (open
// или закрыто)

static boolean isParenthesis(char c)

{

    return ((c == '(') || (c == ')'));

}

  
// метод возвращает true, если строка содержит valid
// скобка

static boolean isValidString(String str)

{

    int cnt = 0;

    for (int i = 0; i < str.length(); i++)

    {

        if (str.charAt(i) == '(')

            cnt++;

        else if (str.charAt(i) == ')')

            cnt--;

        if (cnt < 0)

            return false;

    }

    return (cnt == 0);

}

  
// метод для удаления неверных скобок

static void removeInvalidParenthesis(String str)

{

    if (str.isEmpty())

        return;

  

    // посещение установлено, чтобы игнорировать уже посещенную строку

    HashSet<String> visit = new HashSet<String>();

  

    // очередь для поддержки BFS

    Queue<String> q = new LinkedList<>();

    String temp;

    boolean level = false;

  

    // выдвигаем данную строку как

    // запуск узла в очередь

    q.add(str);

    visit.add(str);

    while (!q.isEmpty())

    {

        str = q.peek(); q.remove();

        if (isValidString(str))

        {

            System.out.println(str);

  

            // Если ответ найден, сделать уровень истинным

            // так, чтобы действительная строка только этого уровня

            // обрабатываются.

            level = true;

        }

        if (level)

            continue;

        for (int i = 0; i < str.length(); i++)

        {

            if (!isParenthesis(str.charAt(i)))

                continue;

  

            // Удаление скобок из str и

            // вставляем в очередь, если еще не посетили

            temp = str.substring(0, i) + str.substring(i + 1);

            if (!visit.contains(temp))

            {

                q.add(temp);

                visit.add(temp);

            }

        }

    }

}

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

public static void main(String[] args) 

{

    String expression = "()())()";

    removeInvalidParenthesis(expression);

  

    expression = "()v)";

    removeInvalidParenthesis(expression);

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для удаления неверных скобок

  
# Метод проверяет, является ли символ круглой скобкой (открыто
# или закрыто)

def isParenthesis(c):

    return ((c == '(') or (c == ')')) 

  
# метод возвращает true, если содержит valid
# скобки

def isValidString(str):

    cnt = 0

    for i in range(len(str)):

        if (str[i] == '('):

            cnt += 1

        elif (str[i] == ')'):

            cnt -= 1

        if (cnt < 0):

            return False

    return (cnt == 0)

      
# метод для удаления неверных скобок

def removeInvalidParenthesis(str):

    if (len(str) == 0):

        return

          

    # посещения, чтобы игнорировать уже посещенные

    visit = set()

      

    # очередь для поддержки BFS

    q = []

    temp = 0

    level = 0

      

    # отправка заданного в качестве начального узла в очередь

    q.append(str)

    visit.add(str)

    while(len(q)):

        str = q[0]

        q.pop()

        if (isValidString(str)):

            print(str)

              

            # Если ответ найден, сделайте уровень истинным

            # так что действует только этого уровня

            # обрабатываются.

            level = True

        if (level):

            continue

        for i in range(len(str)):

            if (not isParenthesis(str[i])):

                continue

                  

            # Удаление скобок из str и

            # толкаем в очередь, если еще не посещали

            temp = str[0:i] + str[i + 1:] 

            if temp not in visit:

                q.append(temp)

                visit.add(temp)

  
Код водителя

expression = "()())()"

removeInvalidParenthesis(expression)

expression = "()v)"

removeInvalidParenthesis(expression)

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

C #

// C # программа для удаления неверных скобок

using System;

using System.Collections.Generic;

  

class GFG 

{

  
// метод проверяет, является ли символ
// скобки (открытые или закрытые)

static bool isParenthesis(char c)

{

    return ((c == '(') || (c == ')'));

}

  
// метод возвращает true, если строка содержит
// допустимая скобка

static bool isValidString(String str)

{

    int cnt = 0;

    for (int i = 0; i < str.Length; i++)

    {

        if (str[i] == '(')

            cnt++;

        else if (str[i] == ')')

            cnt--;

        if (cnt < 0)

            return false;

    }

    return (cnt == 0);

}

  
// метод для удаления неверных скобок

static void removeInvalidParenthesis(String str)

{

    if (str == null || str == "")

        return;

  

    // посещение установлено, чтобы игнорировать уже посещенную строку

    HashSet<String> visit = new HashSet<String>();

  

    // очередь для поддержки BFS

    Queue<String> q = new Queue<String>();

    String temp;

    bool level = false;

  

    // выдвигаем данную строку как

    // запуск узла в очередь

    q.Enqueue(str);

    visit.Add(str);

    while (q.Count != 0)

    {

        str = q.Peek(); q.Dequeue();

        if (isValidString(str))

        {

            Console.WriteLine(str);

  

            // Если ответ найден, сделать уровень истинным

            // так, чтобы действительная строка только этого уровня

            // обрабатываются.

            level = true;

        }

          

        if (level)

            continue;

        for (int i = 0; i < str.Length; i++)

        {

            if (!isParenthesis(str[i]))

                continue;

  

            // Удаление скобок из str и

            // вставляем в очередь, если еще не посетили

            temp = str.Substring(0, i) + 

                   str.Substring(i + 1);

            if (!visit.Contains(temp))

            {

                q.Enqueue(temp);

                visit.Add(temp);

            }

        }

    }

}

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

public static void Main(String[] args) 

{

    String expression = "()())()";

    removeInvalidParenthesis(expression);

  

    expression = "()v)";

    removeInvalidParenthesis(expression);

}

  
// Этот код предоставлен Принчи Сингхом


Выход:

(())()
()()()

(v)
()v

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Удалить неверные скобки

0.00 (0%) 0 votes