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

При решении задач синтаксического анализа, валидации пользовательского ввода или построения собственных парсеров математических выражений возникает необходимость проверить корректность расстановки скобок. В строке могут присутствовать различные типы скобок, например: круглые (), квадратные [] и фигурные {}. При этом выражение считается корректным, если соблюдены правила вложенности и каждой открывающей скобке соответствует закрывающая скобка того же типа.

Рассмотрим несколько способов реализации такой проверки на встроенном языке 1С:Предприятие без использования функции Вычислить().

Вариант 1. Классический алгоритм на основе структуры данных «Стек»

Разберем наиболее надежный, производительный и универсальный способ. В основе этого метода лежит использование стека (структуры LIFO — «последним пришел, первым ушел»). В среде 1С стек удобно реализовать с помощью стандартной коллекции Массив, а сопоставление типов скобок — через объект Соответствие.

Проанализируем алгоритм по шагам:

1. Инициализируем коллекцию соответствий, где ключом будет выступать закрывающая скобка, а значением — парная ей открывающая скобка.
2. Создаем пустой массив, который будет служить стеком для открытых скобок.
3. Посимвольно обходим входную строку слева направо. Символы, не являющиеся скобками (цифры, знаки операций, пробелы), просто игнорируем.
4. Если встречаем открывающую скобку — помещаем её в конец массива методом Добавить().
5. Если встречаем закрывающую скобку — проверяем стек. Если стек пуст или на его вершине лежит открывающая скобка другого типа, то баланс нарушен (возвращаем «Не верно»). Если тип совпал — извлекаем последнюю открывающую скобку из массива методом Удалить().
6. После завершения цикла проверяем размер стека: если массив пуст, баланс соблюден («Верно»), если в нем остались незакрытые скобки — выражение неверно.

Посмотрим на программную реализацию функции, работающей на клиенте и на сервере:

Функция ПроверитьБалансСкобок(Знач Выражение) Экспорт
    
    Стек = Новый Массив;
    
    // Задаем пары скобок: Ключ - закрывающая, Значение - открывающая
    ПарыСкобок = Новый Соответствие;
    ПарыСкобок.Вставить(")", "(");
    ПарыСкобок.Вставить("]", "[");
    ПарыСкобок.Вставить("}", "{");
    
    ОткрывающиеСкобки = "([{";
    ЗакрывающиеСкобки = ")]}";
    
    ДлинаСтроки = СтрДлина(Выражение);
    
    Для Позиция = 1 По ДлинаСтроки Цикл
        Символ = Сред(Выражение, Позиция, 1);
        
        Если СтрНайти(ОткрывающиеСкобки, Символ) > 0 Тогда
            // Помещаем открывающую скобку в стек
            Стек.Добавить(Символ);
            
        ИначеЕсли СтрНайти(ЗакрывающиеСкобки, Символ) > 0 Тогда
            // Если встретили закрывающую скобку при пустом стеке - ошибка
            Если Стек.Количество() = 0 Тогда
                Возврат "Не верно";
            КонецЕсли;
            
            // Получаем последнюю открытую скобку из вершины стека
            ИндексВершины = Стек.ВГраница();
            ПоследняяОткрытая = Стек[ИндексВершины];
            
            // Проверяем соответствие типов
            Если ПоследняяОткрытая = ПарыСкобок[Символ] Тогда
                Стек.Удалить(ИндексВершины);
            Иначе
                Возврат "Не верно";
            КонецЕсли;
            
        КонецЕсли;
    КонецЦикла;
    
    // Если стек пуст - все скобки успешно закрыты
    Если Стек.Количество() = 0 Тогда
        Возврат "Верно";
    Иначе
        Возврат "Не верно";
    КонецЕсли;
    
КонецФункции

Вариант 2. Упрощенный метод циклического сворачивания пар

Рассмотрим альтернативный способ, который часто применяется для быстрой проверки строк, очищенных от сторонних символов. Суть метода заключается в циклическом поиске и удалении соседних правильных пар (), [], {} с помощью функции СтрЗаменить() до тех пор, пока строка не перестанет уменьшаться в размере.

Разберем особенности этого подхода:

1. Метод требует предварительной очистки строки от арифметических знаков, переменных и цифр.
2. Если после полного сжатия длина строки стала равна нулю — скобки расставлены правильно.
3. Если длина перестала уменьшаться, но строка не пуста — баланс или порядок нарушены.

Посмотрим на пример кода с предварительной фильтрацией:

Функция ПроверитьСкобкиСворачиванием(Знач Выражение) Экспорт
    
    // Оставляем только скобки
    СтрокаСкобок = "";
    ВсеСкобки = "()[]{}";
    
    Для Позиция = 1 По СтрДлина(Выражение) Цикл
        Символ = Сред(Выражение, Позиция, 1);
        Если СтрНайти(ВсеСкобки, Символ) > 0 Тогда
            СтрокаСкобок = СтрокаСкобок + Символ;
        КонецЕсли;
    КонецЦикла;
    
    // Последовательно удаляем корректные пары
    Пока Истина Цикл
        ДлинаДо = СтрДлина(СтрокаСкобок);
        
        СтрокаСкобок = СтрЗаменить(СтрокаСкобок, "()", "");
        СтрокаСкобок = СтрЗаменить(СтрокаСкобок, "[]", "");
        СтрокаСкобок = СтрЗаменить(СтрокаСкобок, "{}", "");
        
        // Если замены больше не уменьшают строку, прерываем цикл
        Если СтрДлина(СтрокаСкобок) = ДлинаДо Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
    
    Если СтрДлина(СтрокаСкобок) = 0 Тогда
        Возврат "Верно";
    Иначе
        Возврат "Не верно";
    КонецЕсли;
    
КонецФункции

Сравнение подходов и частые ошибки

Выясним основные нюансы и типичные ошибки при разработке подобных алгоритмов:

1. Проверка четности длины строки: Ошибочно полагать, что нечетная длина всего выражения свидетельствует об ошибке скобок. В арифметическом выражении присутствуют операнды и пробелы, поэтому проверять кратность двум нельзя.
2. Использование тяжелых коллекций: Применение ТаблицаЗначений или СписокЗначений вместо Массив избыточно увеличивает потребление памяти и запрещает выполнение кода на тонком клиенте (для таблиц значений).
3. Рекурсивный разбор: Использование глубокой рекурсии во встроенном языке 1С не рекомендуется из-за риска получить аварийное завершение сеанса при ошибке «Переполнение стека встроенного языка» на длинных строках.

Таким образом, использование классического стека на базе объекта Массив является наиболее оптимальным, надежным и быстрым решением для платформы 1С:Предприятие.