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

@DEN2621 · Регистрация: 17.05.2019

Студворк — интернет-сервис помощи студентам

Задана скобочная последовательность (например, "())[]{}"). Определить, является ли она правильной. Если нет, то исправить её. Решить через рекурсивный метод.

Для начала можно решить и без рекурсий...

Вот несколько моих попыток реализовать это:

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

Здесь я пытался рассмотреть хотя бы случай, когда открывается круглая скобка, и идёт "ожидание" момента, когда появляется скобка другого типа, чтобы перед её появлением поставить закрывающую круглую скобку.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 0; i < Length; ++i)
{
    if (String[i] == '(')
    {
        int j = i;
        if ((String[j] != '[') || (String[j] != ']') || (String[j] != '{') || (String[j] != '}') || (String[j] != '<') || (String[j] != '>'))
        {
            ++j;
        }
        else
        {
            String = String.Insert(j + 1, ")");
        }
        //while ((String[j] != '[') || (String[j] != ']') || (String[j] != '{') || (String[j] != '}') || (String[j] != '<') || (String[j] != '>'))
        //{
        //    ++j;
        //}
    }
}

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

Здесь я совсем заморочился и ввёл массивы для каждого символа скобок, в которые записал их местоположения. Работает, красиво. Но бесполезно...

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
              int Length = String.Length;
        char[] OpenBrackets = new char[String.Length];
        char[] CloseBrackets = new char[String.Length];
        char[] OpenSquareBrackets = new char[String.Length];
        char[] CloseSquareBrackets = new char[String.Length];
        char[] OpenFigureBrackets = new char[String.Length];
        char[] CloseFigureBrackets = new char[String.Length];
        char[] OpenAngleBrackets = new char[String.Length];
        char[] CloseAngleBrackets = new char[String.Length];
        for (int i = 0; i < Length; ++i)
        {
            switch (String[i])
            {
                case '(': OpenBrackets[i] = String[i]; break;
                case ')': CloseBrackets[i] = String[i]; break;
                case '[': OpenSquareBrackets[i] = String[i]; break;
                case ']': CloseSquareBrackets[i] = String[i]; break;
                case '{': OpenFigureBrackets[i] = String[i]; break;
                case '}': CloseFigureBrackets[i] = String[i]; break;
                case '<': OpenAngleBrackets[i] = String[i]; break;
                case '>': CloseAngleBrackets[i] = String[i]; break;
                default: OpenBrackets[i] = '~'; CloseBrackets[i] = '~'; OpenSquareBrackets[i] = '~'; CloseSquareBrackets[i] = '~'; OpenFigureBrackets[i] = '~'; CloseFigureBrackets[i] = '~'; OpenAngleBrackets[i] = '~'; CloseAngleBrackets[i] = '~'; break;
            }
        }
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{OpenBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{CloseBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{OpenSquareBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{CloseSquareBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{OpenFigureBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{CloseFigureBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{OpenAngleBrackets[i]}");
        }
        Console.WriteLine();
        for (int i = 0; i < Length; ++i)
        {
            Console.Write($"{CloseAngleBrackets[i]}");
        }
        Console.WriteLine();
        Console.WriteLine(String);

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

Далее я попытался ввести метод
Но на 15 строчке программа ругается, что индекс выходит из диапазона

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
        static string Brackets(string String)
        {
            StringBuilder SubString = new StringBuilder();
            for (int i = 0; i < String.Length; ++i)
            {
                if (String[i] == '(')
                {
                    for (int j = i; j < String.Length; ++j)
                    {
                        int k = j;
                        while (String[k] != ')')
                        {
                            for (int l = 0; l < SubString.Length; ++l)
                            {
                                SubString[l] += String[k];
                                ++k;
                            }
                        }
                    }
                }
            }
            Console.WriteLine(SubString);
            Brackets(Convert.ToString(SubString));
            return String;
        }

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

И. наконец, программа, которая всё же смогла внести в строку какие-то изменения, а именно: добавить открывающую скобку в начале, если строка начинается с закрывающей. Далее я пытаюсь на основе этого сделать рекурсию, но на 21, 28, 35 и 42 строчках программа снова ругается, что индекс уходит за границы массива, и я никак не могу сообразить, что делать дальше...

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using System;
using System.Text;
 
namespace SavinApp1
{
    class Program
    {
        static StringBuilder Brackets(StringBuilder String)
        {
            switch (String[0])
            {
                case ' ': break;
                case ')': String = String.Insert(0, '('); break;
                case ']': String = String.Insert(0, '['); break;
                case '}': String = String.Insert(0, '{'); break;
                case '>': String = String.Insert(0, '<'); break;
                case '(':
                    {
                        StringBuilder SubString = new StringBuilder();
                        SubString = String.Remove(0, 1);
                        Brackets(SubString);
                        break;
                    }
                case '[':
                    {
                        StringBuilder SubString = new StringBuilder();
                        SubString = String.Remove(0, 1);
                        Brackets(SubString);
                        break;
                    }
                case '{':
                    {
                        StringBuilder SubString = new StringBuilder();
                        SubString = String.Remove(0, 1);
                        Brackets(SubString);
                        break;
                    }
                case '<':
                    {
                        StringBuilder SubString = new StringBuilder();
                        SubString = String.Remove(0, 1);
                        Brackets(SubString);
                        break;
                    }
            }
            return String;
        }
        static void Main(string[] args)
        {
            Console.Write("Введите строку: ");
            StringBuilder String = new StringBuilder(Console.ReadLine());
            Brackets(String);
            Console.WriteLine(String);
        }
    }
}

@Элд Хасп · 28.05.2019, 23:59

Сообщение от DEN2621

Определить, является ли она правильной. Если нет, то исправить её.

Методов определения множество. Посмотрите в разделе найдёте несколько десятков реализаций.

Что касается исправления, то это (в общем виде) не возможно.
Вот допустим выражение 4*(5+6+7 - где надо ставить закрывающую скобку: после 6 или после 7?

@DEN2621 · 29.05.2019, 00:04 **[ТС]**

В моём случае речь идёт не о выражениях, а о последовательностях скобок, таких как "){([)(]{)(})(]({(}(])[({(})()[({)"
А что касается неоднозначных вариантов постановки новых скобок - пусть они будут ставиться при первой возможности.

@Diamante · 29.05.2019, 00:58

не вкурил сути задачи, есть только скобки? и именно их надо привести в правильное расположение, через добавление?

@DEN2621 · 29.05.2019, 01:08 **[ТС]**

Да, именно так

@shelluser · 29.05.2019, 01:27

DEN2621,

дана строка string s = "))))"

как правильно исправить ? Так ()()()() ? или (((()))) а может (())(()) или вообще ((()))() ?
какой вариант или все подходят ?

@DEN2621 · 29.05.2019, 02:09 **[ТС]**

все подходят

Добавлено через 38 минут
Алгоритм, который я пытался реализовать в последней версии своей программы:

1. Считать первый символ. Если он является закрывающей скобкой, добавить перед ним соответствующую открывающую;
2. Если он является открывающей скобкой, записать все следующие символы до первой парной скобки в новую подстроку SubString;
3. Вызвать метод Brackets(SubString) от новой подстроки.

@Элд Хасп · 29.05.2019, 12:00

Сообщение от DEN2621

все подходят

Попробуйте такую реализацию

Структура для пары скобок

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
        public struct PairBrackets
        {
            public char Open { get; }
            public char Close { get; }
            public PairBrackets(char open, char close)
            {
                if (open == close)
                    throw new ArgumentException("Скобки не могут быть одинаковыми!");
                Open = open;
                Close = close;
            }
            public PairBrackets(string pair)
            {
                if (pair == null || pair.Length != 2)
                    throw new ArgumentException("Должна быть строка из двух символов!");
                Open = pair[0];
                Close = pair[1];
            }
            public bool Concat(char bracket) => Close == bracket || Open == bracket;
            public static List<PairBrackets> BracketsFromString(string pairs)
            {
                if (pairs.Length != pairs.Distinct().Count())
                    throw new ArgumentException("В строке не может быть одинаковых символов скобок!");
                if (pairs.Length % 2 != 0)
                    throw new ArgumentException("В строке должно быть парное количество скобок");
 
                List<PairBrackets> brackets = new List<PairBrackets>();
                for (int i = 0; i < pairs.Length; i += 2)
                    brackets.Add(new PairBrackets(pairs[i], pairs[i + 1]));
                return brackets;
            }
        }

Метод для обработки строки со скобками

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
        public static string FixBrackets(string expression)
        {
            if (string.IsNullOrEmpty(expression))
                return expression;
            string bracketsString = "()[]{}<>«»";
            List<PairBrackets> brackets = PairBrackets.BracketsFromString(bracketsString);
 
            if (!expression.All(ch => brackets.FindIndex(br => br.Concat(ch)) >= 0))
                throw new ArgumentException("В выражении должны быть только скобки!");
 
            return _fix(expression);
            string _fix(string exp)
            {
                if (exp == string.Empty)
                    return exp;
               PairBrackets pair = brackets.First(br => br.Concat(exp[0]));
                if (exp[0] == pair.Close)
                    return pair.Open.ToString() + pair.Close.ToString() + _fix(exp.Substring(1));
                else
                {
                    int ind = exp.IndexOf(pair.Close);
                    if (ind < 0)
                        return pair.Open.ToString() + _fix(exp.Substring(1)) + pair.Close.ToString();
                    else
                    {
                        int indPrev = exp.LastIndexOf(pair.Open, ind);
                        return _fix(exp.Remove(indPrev)) + pair.Open.ToString()
                            + _fix(exp.Substring(indPrev + 1, ind - indPrev - 1)) + pair.Close.ToString()
                            + _fix(exp.Remove(ind));
                    }
                }
            }
        }

Для Console.WriteLine(FixBrackets("){([)(]{)(})(]({(}(])[({(})()[({)")); возвращает (){([])([])}{()()}{([])([])}

Добавлено через 2 минуты
Не - ошибка где-то

@Элд Хасп · 29.05.2019, 12:23

С индексами напутал.
Вот правильный код

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
        public static string FixBrackets(string expression)
        {
            if (string.IsNullOrEmpty(expression))
                return expression;
            string bracketsString = "()[]{}<>«»";
            List<PairBrackets> brackets = PairBrackets.BracketsFromString(bracketsString);
 
            if (!expression.All(ch => brackets.FindIndex(br => br.Concat(ch)) >= 0))
                throw new ArgumentException("В выражении должны быть только скобки!");
 
            return _fix(expression);
            string _fix(string exp)
            {
                string ret;
                //Console.WriteLine(exp.Length+"="+exp);
                if (exp == string.Empty)
                    ret = exp;
                else
                {
                    PairBrackets pair = brackets.First(br => br.Concat(exp[0]));
                    if (exp[0] == pair.Close)
                        ret= pair.Open.ToString() + pair.Close.ToString() + _fix(exp.Substring(1));
                    else
                    {
                        int ind = exp.IndexOf(pair.Close);
                        if (ind < 0)
                            ret = pair.Open.ToString() + _fix(exp.Substring(1)) + pair.Close.ToString();
                        else
                        {
                            int indPrev = exp.LastIndexOf(pair.Open, ind);
                            ret= _fix(exp.Remove(indPrev)) + pair.Open.ToString()
                                + _fix(exp.Substring(indPrev + 1, ind - indPrev - 1)) + pair.Close.ToString()
                                + _fix(exp.Substring(ind+1));
                        }
                    }
                }
                //Console.WriteLine(exp.Length + "=" + exp + "=" + ret);
                return ret;
            }
        }

Для ){([)(]{)(})(]({(}(])[({(})()[({)
возвращает (){([])([])}{()()}()([]({()}))([])[({})({})()[({})]]

@DEN2621 · 30.05.2019, 00:09 **[ТС]**

Это великолепно... Оно работает!
Большое спасибо!
Осталось только разобраться, что к чему...

@Элд Хасп · 30.05.2019, 10:27

Сообщение от DEN2621

Осталось только разобраться, что к чему...

Сами не разберётесь - пишите.

Новые блоги и статьи Все статьи Все блоги /
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .

@DEN2621 1 / 1 / 0 Регистрация: 17.05.2019 Сообщений: 21
	29.05.2019, 00:04 [ТС]
	В моём случае речь идёт не о выражениях, а о последовательностях скобок, таких как "){([)(]{)(})(]({(}(])[({(})()[({)" А что касается неоднозначных вариантов постановки новых скобок - пусть они будут ставиться при первой возможности. 0

@Diamante 3566 / 2507 / 1174 Регистрация: 14.08.2016 Сообщений: 8,219
	29.05.2019, 00:58
	не вкурил сути задачи, есть только скобки? и именно их надо привести в правильное расположение, через добавление? 0

@DEN2621 1 / 1 / 0 Регистрация: 17.05.2019 Сообщений: 21
	29.05.2019, 01:08 [ТС]
	Да, именно так 0

@shelluser 146 / 39 / 26 Регистрация: 11.05.2019 Сообщений: 122
	29.05.2019, 01:27
	DEN2621, дана строка string s = "))))" как правильно исправить ? Так ()()()() ? или (((()))) а может (())(()) или вообще ((()))() ? какой вариант или все подходят ? 0

@DEN2621 1 / 1 / 0 Регистрация: 17.05.2019 Сообщений: 21
	29.05.2019, 02:09 [ТС]
	все подходят Добавлено через 38 минут Алгоритм, который я пытался реализовать в последней версии своей программы: 1. Считать первый символ. Если он является закрывающей скобкой, добавить перед ним соответствующую открывающую; 2. Если он является открывающей скобкой, записать все следующие символы до первой парной скобки в новую подстроку SubString; 3. Вызвать метод Brackets(SubString) от новой подстроки. 0

@DEN2621 1 / 1 / 0 Регистрация: 17.05.2019 Сообщений: 21
	30.05.2019, 00:09 [ТС]
	Это великолепно... Оно работает! Большое спасибо! Осталось только разобраться, что к чему... 0

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

Решение