Рекурсия. Синтаксический анализатор - 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, не является результатом работы программы, а используется для корректного выхода из программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д