Blog. Just Blog

Проверка баланса скобок на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail 28.01.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
Есть такая классическая задача по программированию: проверка правильности расстановки скобок в строке, или иначе проверка баланса скобок. Суть задачи заключается в том, что есть произвольное математическое выражение, записанное в строку, в этом выражении используется три вида скобок "( )", "[ ]" и "{ }", последовательность и вложенность может быть любая. Требуется проверить, все ли скобки закрыты, соответствует ли каждая закрывающая скобка открывающей и нет ли лишних закрывающих скобок. В разных интернетах есть решения на различных языках программирования, я решил добавить свое решение на Ассемблере, тем более, что он идеально подходит для реализации этого алгоритма.

Решение заключается в том, что мы двигаемся по строке с самого начала, перебирая все символы по одному. Если символ является открывающей скобкой любого типа, то мы помещаем его в стек. Если символ является закрывающей скобкой, то берем из стека последнюю сохраненную открывающую скобку и проверяем на соответствие. Если не совпадают - ошибка несоответствия скобок, если стек пустой, то ошибка лишней закрывающей скобки. Если конец строки достигнут, но стек не пустой, то ошибка незакрытых скобок. Как видите, решение целиком построено на работе со стеком, а Ассемблер предоставляет для этого все возможности. Переходим к программированию.
Code (Assembler) : Убрать нумерацию
  1. ;------------------------------------------------------------------------
  2. ; Функция проверки правильности расстановки скобок в выражении
  3. ; На входе: указатель на строку ASCIIZ
  4. ; На выходе: EAX - результат проверки выражения
  5. ;    0 - скобки расставлены правильно
  6. ;    1 - ОШИБКА: скобки не совпадают
  7. ;    2 - ОШИБКА: закрывающая скобка без открывающей
  8. ;    3 - ОШИБКА: открывающая скобка без закрывающей
  9. ;------------------------------------------------------------------------
  10. proc    CheckBrackets str:DWORD
  11.         local res:DWORD ; Результат
  12.  
  13.         pusha                   ; Сохранить все регистры
  14.  
  15.         mov     esi,[str]       ; Указатель на строку
  16.         cld
  17.         xor     ecx,ecx         ; Глубина стека
  18.         mov     [res],0         ; Результат проверки
  19.  
  20. .scan_expr:
  21.         lodsb                   ; Прочитать символ из строки
  22.         or      al,al           ; Конец строки достигнут?
  23.         jz      .finish
  24.  
  25.         ; Проверить открывающие скобки
  26.         cmp     al,'['
  27.         je      .push_bracket
  28.         cmp     al,'('
  29.         je      .push_bracket
  30.         cmp     al,'{'
  31.         je      .push_bracket
  32.  
  33.         ; Проверить закрывающие скобки
  34.         cmp     al,']'
  35.         je      .pop_bracket
  36.         cmp     al,')'
  37.         je      .pop_bracket
  38.         cmp     al,'}'
  39.         je      .pop_bracket
  40.  
  41.         jmp     .scan_expr      ; Следующий символ
  42.  
  43.         ; Занести скобку в стек
  44. .push_bracket:
  45.         inc     ecx             ; Увеличить счетчик
  46.         movzx   eax,al          ; Записать скобку в стек
  47.         push    eax
  48.         jmp     .scan_expr      ; Следующий символ
  49.  
  50.         ; Извлечь скобку из стека
  51. .pop_bracket:
  52.         or      ecx,ecx         ; В стеке ничего нет?
  53.         jne     @f
  54.  
  55.         ; ОШИБКА: закрывающая скобка без открывающей
  56.         mov     [res],2
  57.         jmp     .finish
  58. @@:
  59.         dec     ecx             ; Уменьшить счетчик
  60.         pop     ebx             ; Извлечь из стека скобку
  61.  
  62.         ; Проверить закрывающие скобки
  63.         cmp     bl,'['
  64.         jne     @f
  65.  
  66.         cmp     al,']'          ; Скобки совпадают?
  67.         je      .scan_expr      ; Да, следующий символ
  68. @@:
  69.         cmp     bl,'('
  70.         jne     @f
  71.  
  72.         cmp     al,')'          ; Скобки совпадают?
  73.         je      .scan_expr      ; Да, следующий символ
  74. @@:
  75.         cmp     bl,'{'
  76.         jne     @f
  77.  
  78.         cmp     al,'}'          ; Скобки совпадают?
  79.         je      .scan_expr      ; Да, следующий символ
  80. @@:
  81.         ; ОШИБКА: скобки не совпадают
  82.         mov     [res],1
  83.         or      ecx,ecx         ; В стеке пусто?
  84.         jz      .exit           ; Да, просто на выход
  85.         jmp     .clean_stack    ; Надо почистить стек
  86. .finish:
  87.         or      ecx,ecx         ; Все проверили и в стеке пусто?
  88.         jz      .exit           ; Да, скобки расставлены правильно
  89.  
  90.         ; ОШИБКА: открывающая скобка без закрывающей
  91.         mov     [res],3
  92.  
  93.         ; Почистить стек от оставшихся скобок
  94. .clean_stack:
  95.         pop     eax
  96.         loop    .clean_stack
  97. .exit:
  98.         popa                    ; Восстановить все регистры
  99.         mov     eax,[res]
  100.  
  101.         ret
  102. endp
Текст функции проверки подробно прокомментирован, так что в дополнительных пояснениях не нуждается. Тем более, что алгоритм был расписан словами выше. Где это можно использовать? Кроме различных калькуляторов подобные решения можно применять для валидации xml-подобных документов, при проверке синтаксиса каких-либо скриптов и т.п., так что главное уяснить принцип.

В приложении готовый пример и исходник программы, получающей от пользователя строку математического выражения и проверяющей ее на правильность расстановки скобок. Для проверки используется описанная выше функция.

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

Brackets.Balance.Demo.zip (3,265 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 7179 | Комментариев: 4

Метки: Assembler
Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (05.05.2020 в 14:28):
Конечно. Вот прямо так и пишет "код не найден". Ассемблер подразумевает определенный порог вхождения, например, пару лет теории, лет 10 практики, полгода бессонных ночей в отладчике. А не так, что увидел, скачал, скомп_Е_лировал.
Старец (05.05.2020 в 13:10):
А как скомпелировать этот код?Просто у меня фасм выдаёт ошибку что код не найден
Ret (28.12.2012 в 19:32):
Даа, надо бы попробовать написать свой парсер для конфигов ;)
- парсинг вложенных секций
- комментарии
- списки
итд.
похоже на очередной велосипед, но это не совсем так, ini под описание не подходит, xml как бы это сказать, в общем не торт
Студент (01.02.2011 в 07:07):
Огромное Вам спасибо... :3

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (30), AJAX (5), Assembler (361), COM (41), CSS (41), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (51), iconBIT (4), JavaScript (73), MySQL (13), Nikon (19), PDF (9), PHP (122), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (125), выпечка (28), выставки (119), генератор ПСЧ (10), графика (120), десерты (31), Египет (8), заготовки на зиму (47), закуска (22), закуска к пиву (24), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (315), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (68), мониторы (6), музеи (78), мультимедиа (75), мясо (62), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (49), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (129), полезные функции (42), прохождения (4), процессы (25), птица (20), путешествия (25), распаковка (22), реверсинг (51), рыба (35), салаты (19), сброс триала (4), сеть (36), система (178), Сокольники (8), соусы (14), супы (14), телефоны (9), Тунис (6), умный дом (13), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 35,133 раза
<< 2024 - СЕНТЯБРЬ >>
Пн Вт Ср Чт Пт Сб Вс
            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            
Всемирный день уничтожения военной игрушки
Всемирный день бороды
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0051 сек.) / Память: 4.5 Mb
Наверх