Рекурсия. Синтаксический анализатор - C (СИ)
Формулировка задачи:
Проверить правильность расстановки скобок в строке S. Текст в строке S определяется следующим образом:
<текст>::=<элемент>|<элемент><текст>
<элемент>::=a|b|c|(<текст>)|[<текст>]|{<текст>}
Если текст составлен правильно, то вывести True, иначе вывести False
Решение задачи: «Рекурсия. Синтаксический анализатор»
textual
Листинг программы
#include <stdio.h>
/*
Проверить правильность расстановки скобок в строке S. Текст в строке S определяется следующим образом:
<текст>::=<элемент>|<элемент><текст>
<элемент>::=a|b|c|(<текст>)|[<текст>]|{<текст>}
Если текст составлен правильно, то вывести True, иначе вывести False
*/
class Scaner {
private:
int i;
const char* buf;
public:
Scaner(const char* text) {
this->i = 0;
this->buf = text;
}
char get() {
//printf("get %c\n", buf[i]);
return buf[i];
}
char next() {
//printf("next %c\n", buf[i]);
return buf[i++];
}
};
bool A_text(Scaner* s);
bool A_El(Scaner* s) {
//puts("el");
switch(s->next()) {
case 'a':
case 'b':
case 'c':
return true;
case '(':
A_text(s);
if (s->next() != ')' ) return false;
return true;
case '[':
A_text(s);
if (s->next() != ']' ) return false;
return true;
case '{':
A_text(s);
if (s->next() != '}' ) return false;
return true;
default: return false;
}
}
bool A_text(Scaner* s) {
//puts("text");
do {
switch(s->get()) {
case 'a':
case 'b':
case 'c':
case '(':
case '[':
case '{':
if (!A_El(s)) return false;
break;
default: return false;
}
} while(s->get() != '\0');
return true;
}
int main() {
Scaner* s = new Scaner("abcacbacbabcb[a]cb");
printf(A_text(s)? "True" : "False");
return 0;
}
Объяснение кода листинга программы
- Создание класса Scaner для синтаксического анализатора
- Определение функции A_text для проверки корректности расстановки скобок в строке
- Определение функции A_El для обработки элементов в строке
- Использование оператора switch для определения типа текущего элемента в строке
- Рекурсивный вызов функции A_El для обработки вложенных скобок
- Проверка правильности закрытия скобок в строке
- Использование оператора do-while для обработки последовательности элементов в строке
- Проверка каждого элемента строки на соответствие синтаксису
- Вывод результата работы программы на экран
- Создание экземпляра класса Scaner для заданной строки в функции main
- Вызов функции A_text для проверки корректности расстановки скобок в созданном экземпляре класса Scaner
- Вывод результата проверки на экран
- Вызов функции A_text в функции main возвращает значение True, если строка содержит корректно расставленные скобки, иначе возвращает значение False
- Вложенные вызовы функций A_El и A_text в функции A_text обеспечивают рекурсивный анализ строки
- Использование оператора new для выделения памяти под экземпляр класса Scaner
- Использование оператора delete для освобождения памяти после использования экземпляра класса Scaner
- Использование оператора printf для вывода результата работы программы на экран
- Значение True выводится на экран, если строка содержит корректно расставленные скобки, иначе выводится значение False
- Возврат значения 0 из функции main указывает на успешное завершение программы
- Значение 0, возвращаемое из функции main, не является результатом работы программы, а используется для корректного выхода из программы.