Проверить "правильность" скобок в строке.

@neruproton · Регистрация: 15.04.2017

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

Здравствуйте, уважаемые форумчане. Задачка состоит в том, чтобы проверить "правильность" скобок в строке str.
Задачу нужно решить через односвязный список, я занес в список 1 открывающиеся скобки, а в список 2 закрывающиеся. Вопрос как мне развернуть список 2, чтобы сравнить его с первым списком. Т.е. сейчас при выводе
____________________________
(
[
{
____________________________
}
]
)
____________________________
Или можете предложить другую идею решения (может более рациональную).

JavaScript
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
var list = function (e) 
{
    var self = this;
    var first, last, head;
 
    self.insert = function (value) {
        var node = new Node(value);
        if (first == null) {
            first = last = node;
        } else {
            var head = first;
            while (head.next != null) {
                head = head.next;
            }
            head.next = node;
            last = head.next;
        }
    }
    self.show = function () {
        var head = first;
        while (head != null) {
            console.log(head.value);
            head = head.next;
        }
    }
    var Node = function (value) {
        this.value = value;
        var next = {};
    }
    return self;
};
 
var list_1 = new list();
var list_2 = new list();
var str = "(Я [ хочу {программировать} на ] JavaScript)";
for (var i=0; i<str.length; i++)
    if(str[i].indexOf('(') + 1 > 0 || str[i].indexOf('[') + 1 > 0 || str[i].indexOf('{') + 1 > 0)
        list_1.insert(str[i]);
    else if(str[i].indexOf(')') + 1 > 0 || str[i].indexOf(']') + 1 > 0 || str[i].indexOf('}') + 1 > 0)
        list_2.insert(str[i]);
console.log("____________________________");
list_1.show();
console.log("____________________________");
list_2.show();
console.log("____________________________");

@diadiavova · 01.04.2018, 03:11

neruproton, очень странный способ решения такой задачи. Если каждый вид скобок встречается по одному разу, то, возможно, это и сработает, а как насчет случаев со вложенными скобками одного типа? Ну например такой вариант ([(){}])? В данном случае скобки согласованны, но если проверять это твоим способом, то список открывающих скобок будет выглядеть так ([({, а список закрывающих - так )}]). И, как ты понимаешь, при развороте одного из списков они не совпадут. Возможно, конечно, я просто не понял смысла твоего решения. Что до реверса списка, то не очень понятно зачем он вообще нужен и чем массив не угодил? У массива есть метод reverse, а связный список обычно разворачивают путем создания нового списка и поочередного добавления всех элементов в него.

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

Или можете предложить другую идею решения (может более рациональную).

Мне пришло в голову такое решение

JavaScript
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
        function checkString(input)
        {
            let stack = [];
            for (const ch of input.split(""))
            {
                switch (ch)
                {
                    case "(":
                        stack.push(1) ;
                        break;
                    case "[":
                        stack.push(2);
                        break;
                    case "{":
                        stack.push(3);
                        break;
                    case "}":
                        if (stack[stack.length - 1] != 3) return false;
                        stack.pop();
                        break;
                    case "]":
                        if (stack[stack.length - 1] != 2) return false;
                        stack.pop();
                        break;
                    case ")":
                        if (stack[stack.length - 1] != 1) return false;
                        stack.pop();
                        break;
                    default:
                        break;
                }
            }
            return stack.length == 0;
        }

Функция принимает строку и возвращает true, если все три вида скобок в ней согласованны. Но надо тестировать, я сам проверил строку из твоего кода и немного поизменял, вроде все работает, но полноценное тестирование не повредить, поскольку гарантий корректной работы во всех ситуациях дать не могу.

@Eva Rosalene · 03.04.2018, 16:48

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

JavaScript
1
input.split("")

В split('') в данном случае нет нужды.

Добавлено через 9 минут
Чуть более компактно:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const isCorrect = string => {
  const pairs = [['(', ')'], ['{', '}'], ['[', ']']];
  const open = new Set(pairs.map(pair => pair[0]));
  const close  = new Set(pairs.map(pair => pair[1]));
  const relevant = pairs.reduce((acc, [open, close]) => ({...acc, [close]: open}), {});
 
  let stack = [];
  for (let char of string) {
    if (open.has(char)) {
      stack.push(char);
    }
    if (close.has(char)) {
      if (relevant[char] !== stack.pop()) return false;
    }
  }
  
  return stack.length === 0;
};

@diadiavova · 04.04.2018, 06:19

Сообщение от Eva Rosalene

Чуть более компактно:

Тогда уж так лучше

JavaScript
1
2
3
4
5
6
7
8
9
10
11
        function checkBalance(str)
        {
            let stack = [], open = "([{", close = ")]}";
            for (const ch of str)
            {
                let i = open.indexOf(ch);
                if (i > -1) stack.push(close[i]);
                if (close.includes(ch) && ch != stack.pop()) return false
            }
            return stack.length == 0;
        }

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

Проверить "правильность" скобок в строке.

Решение