Шановні читачі, оскільки в минулій статті ми розглянули елементарну реалізацію стеку, цього разу хотілось би показати вам приклад його використання. Як правило рядки (об'єкти, які мають тип String), містять у собі програмний код, написаний комп'ютерною мовою і згодом цей код обробляє програма компілятор. Наш рядок, не обов'язково буде містити Java код, але використання дужок у програмі все одно повинно узгоджуватись з правилами Java. Працювати ми сьогодні будемо з трьома видами дужок:
- {} - фігурними
- [] - квадратними
- () - круглими
Сформуємо правила використання цих елементів:
- Кожна відкриваюча дужка, повинна мати парну закриваючу
- Дужки, які розташовані ближче до кінця рядка, повинні закриватися раніше
Трохи заплутано, чи не так? Розглянемо на прикладах:
- [c]d – правильне використання
- a{b[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).
На цьому завершимо нашу теоретичну частину.
Для початку реалізуємо клас стеку. Пояснення до нього надавались у попередній статті, тож не будемо повторюватися:
class StackForBrakes {
private char[] myStack;
private int top;
private int maxSize;
public StackForBrakes(int maxSize) {
this.maxSize = maxSize;
this.top = -1;
myStack = new char[maxSize];
}
public void addElement(char elem) {
myStack[++top] = elem;
}
public char deleteFromHead() {
return myStack[top--];
}
public void viewHead() {
System.out.println("Head: " + myStack[top]);
}
public boolean isEmpty() {
return (top == -1);
}
}
Наступним кроком реалізуємо клас, який буде відповідати за рішення нашої задачі:
class Check {
private String input;
private int lengthInput;
private StackForBrakes stack;
public Check(String input) {
this.input = input;
this.lengthInput = input.length();
stack = new StackForBrakes(lengthInput);
}
Створимо поля:
-
input– приймає рядок, який потрібно перевірити -
lengthInput– містить у собі розмір введеного рядка -
stack– об'єкт класуStackForBrakes
Пам'ятайте! Конструктор призначений для ініціалізації даних, тому оголошуємо змінні перед конструктором.
Створимо метод makeCheck, який буде містити алгоритм перевірки правильності введення дужок.
Почнемо поелементно перебирати наш рядок, і якщо зустрічаємо відкриваючу дужку – заносимо її в стек.
public void makeCheck() {
for (int i = 0; i < lengthInput; i++) { // початок послідовного зчитування
char ch = input.charAt(i); // зчитування символу
switch (ch) {
case '{':
case '[':
case '(':
stack.addElement(ch);
break;
Коли алгоритм знаходить закриваючу скобку відбувається її порівняння з останньою скобкою доданою у стек і відповідна реакція алгоритму перевірки (або повідомлення про помилку, або продовження роботи програми).
case '}':
case ']':
case ')':
if (!stack.isEmpty()) { //якщо стек не порожній
char chClosed = stack.deleteFromHead(); //вилучити та перевірити
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:
public class StackWhichCheckBrakesPair {
public static void main(String[] args) {
Check check = new Check("a[b{c}d]e}");
check.makeCheck();
}
}
Результат роботи програми:
Лістинг програми:
class StackForBrakes {
private char[] myStack;
private int top;
private int maxSize;
public StackForBrakes(int maxSize) {
this.maxSize = maxSize;
this.top = -1;
myStack = new char[maxSize];
}
public void addElement(char elem) {
myStack[++top] = elem;
}
public char deleteFromHead() {
return myStack[top--];
}
public void viewHead() {
System.out.println("Head: " + myStack[top]);
}
public boolean isEmpty() {
return (top == -1);
}
}
class Check {
private String input;
private int lengthInput;
private StackForBrakes stack;
public Check(String input) {
this.input = input;
this.lengthInput = input.length();
stack = new StackForBrakes(lengthInput);
}
public void makeCheck() {
//autor binaryUA
for (int i = 0; i < lengthInput; i++) { // початок послідовного зчитування
char ch = input.charAt(i); // зчитування символу
switch (ch) {
case '{':
case '[':
case '(':
stack.addElement(ch);
break;
case '}':
case ']':
case ')':
if (!stack.isEmpty()) { //якщо стек не порожній
char chClosed = stack.deleteFromHead(); //вилучити та перевірити
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("Помилка! Загублена закриваюча дужка");
}
}
}
public class StackWhichCheckBrakesPair {
public static void main(String[] args) {
Check check = new Check("a[b{c}d]e}");
check.makeCheck();
}
}
Ще немає коментарів