Пример использования Стека на Java

Уважаемые читатели, поскольку в прошлой статье мы рассмотрели элементарную реализацию стека, на этот раз хотелось бы показать вам пример его использования. Как правило строки (объекты, которые имеют тип String), включают в себя программный код, написанный на компьютерном языке, который обрабатывает программа компилятор.

Наша строка не обязательно будет содержать Java код, но использование скобок в программе все равно должно согласовываться с правилами Java. Работать мы сегодня будем с тремя видами скобок:

  • {} — фигурными
  • [] -kvadratnimi
  • () -круглимы

Сформируем правила использования этих элементов:

  • Каждая открывающая скобка должна иметь закрывающую
  • Скобки, которые расположены ближе к концу строки, должны закрываться раньше

Немного запутанно, не так ли? Рассмотрим на примерах:

  • [c][/c]

    d – правильное использование

  • a{b

    [c][/c]

    d}e –правильное использование

  • a {b (c] d} e — неправильное использование, ] не соответствует (
  • a [b {c} d] e} — неправильное использование, в закрывающей скобки } нет пары
  • a {b (c) — неправильное использование, в открывающей скобки { нет пары

Аглоритм работы

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

Рассмотрим состояние стека при разборе строки a {b (c [d] e) f}

1

В процессе работы программы, каждая открывающая скобка заносится в стек. Каждая закрывающая скобка сравнивается с вершиной стека и если они формируют пару — то все в порядке. В стек мы заносим только скобки, а остальное символов игнорируем. Таким образом, пара скобок, открытая последней, будет закрыта первой. Идеальная иллюстрация принципа LIFO (first in, first out).

На этом завершим нашу теоретическую часть.

Пример использования Стека на Java

Для начала реализуем класс стека. Пояснение к нему предоставлялись в предыдущей статье, поэтому не будем повторяться:

Следующим шагом реализуем класс, который будет отвечать за решение нашей задачи:

Создадим поля:

  • input — принимает строку, который нужно проверить
  • lengthInput — включает в себя размер введенной строки
  • stack — объект класса Stack

Помните! Конструктор предназначен для инициализации данных, поэтому объявляем переменные перед конструктором. Создадим метод makeCheck , который будет содержать алгоритм проверки правильности ввода скобок. Начнем поэлементно перебирать нашу строку и если встречаем открывающую скобку — заносим ее в стек.

Когда алгоритм находит закрывающую скобку происходит ее сравнение с последней скобки добавленной в стек и соответствующая реакция алгоритма проверки (или сообщение об ошибке, или продолжение работы программы).

И наконец класс main :

Результат выполнения программы:

Пример работы со стеком на java готов. Следите за обновлениями на Prologistic.com.ua

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *