Уважаемые читатели, поскольку в прошлой статье мы рассмотрели элементарную реализацию стека, на этот раз хотелось бы показать вам пример его использования. Как правило строки (объекты, которые имеют тип 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}
В процессе работы программы, каждая открывающая скобка заносится в стек. Каждая закрывающая скобка сравнивается с вершиной стека и если они формируют пару — то все в порядке. В стек мы заносим только скобки, а остальное символов игнорируем. Таким образом, пара скобок, открытая последней, будет закрыта первой. Идеальная иллюстрация принципа LIFO (first in, first out).
На этом завершим нашу теоретическую часть.
Пример использования Стека на Java
Для начала реализуем класс стека. Пояснение к нему предоставлялись в предыдущей статье, поэтому не будем повторяться:
|
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 |
class Stack { private int mSize; private int[] stackArray; private int top; public Stack(int m) { this.mSize = m; stackArray = new int[mSize]; top = -1; } public void addElement(int element) { stackArray[++top] = element; } public int deleteElement() { return stackArray[top--]; } public int readTop() { return stackArray[top]; } public boolean isEmpty() { return (top == -1); } public boolean isFull() { return (top == mSize - 1); } } |
Следующим шагом реализуем класс, который будет отвечать за решение нашей задачи:
Создадим поля:
input— принимает строку, который нужно проверитьlengthInput— включает в себя размер введенной строкиstack— объект классаStack
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Check { private String input; private int lengthInput; private Stack stack; //В конструкторе инициализируем поля public Check(String input) { this.input = input; this.lengthInput = input.length(); stack = new Stack(lengthInput); } |
Помните! Конструктор предназначен для инициализации данных, поэтому объявляем переменные перед конструктором. Создадим метод makeCheck , который будет содержать алгоритм проверки правильности ввода скобок. Начнем поэлементно перебирать нашу строку и если встречаем открывающую скобку — заносим ее в стек.
|
1 2 3 4 5 6 7 8 9 10 |
public void makeCheck() { for (int i = 0; i < lengthInput; i++) { // начинаем последовательно считывать char ch = input.charAt(i); // считывание символа switch (ch) { case '{': case '[': case '(': stack.addElement(ch); break; |
Когда алгоритм находит закрывающую скобку происходит ее сравнение с последней скобки добавленной в стек и соответствующая реакция алгоритма проверки (или сообщение об ошибке, или продолжение работы программы).
|
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 |
case '}': case ']': case ')': if (!stack.isEmpty()) { //если стек не пустой char chClosed = stack.deleteElement(); //удалить и проверить if ((ch == '}' && chClosed != '{') || (ch == ']' && chClosed != '[') || (ch == ')' && chClosed != '(')) System.out.println("Ошибка! Скобка " + ch + " в " + i + " позиции."); } else //недостаток элементов в стеке System.out.println("Ошибка! Скобка " + ch + " в " + i + " позиции."); break; default: // для других символов действия не выполняются break; } } if (!stack.isEmpty()) { System.out.println("Ошибка! Отсутствует закрывающая скобка"); } } } |
И наконец класс main :
|
1 2 3 4 5 6 7 8 |
public class AwesomeBrakesPairChecker { public static void main(String[] args) { Check check = new Check("a[b{c}d]e}"); check.makeCheck(); } } |
Результат выполнения программы:
|
1 |
Ошибка! Скобка } в 9 позиции |
Пример работы со стеком на java готов. Следите за обновлениями на Prologistic.com.ua
