В некоторых прикладных задачах информационной обработки данных является актуальной проблема символической интерпретации алгебраических выражений с целью их преобразования и упрощения для экономии вычислительных ресурсов при последующей обработке. Как правило, алгебраическое выражение может содержать различные типы скобок для группировки элементов и изменения приоритета операций.

Например, алгебраическое выражение:

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

1) число открывающих и закрывающих скобок каждого типа одинаково;

2) каждой закрывающей скобке любого типа предшествует открывающая скобка того же типа.

Например, алгебраические выражения:

нарушают 1-е, 2-е и оба условия, соответственно.

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

В заключении следует отметить, что рассмотренный стековый алгоритм, очевидно, можно применять, когда в алгебраическом выражении присутствуют только скобки одного типа. Однако, для этого простого частного случая существует другой алгоритм, не использующий стек. В нем применяется счетчик скобок. Каждая открывающая скобка увеличивает значение счетчика на 1, каждая закрывающая - уменьшает на 1. При правильной расстановки скобок значение счетчика в конце алгебраического выражения должно быть равно 0, а внутри выражения неотрицательно. Должно быть понятно, что этот алгоритм нельзя применять, когда в алгебраическом выражении присутствуют различные типы скобок, т.к. счетчик скобок не обеспечивает соответствия типов скобок.