Blog. Just Blog

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

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

Решение заключается в том, что мы двигаемся по строке с самого начала, перебирая все символы по одному. Если символ является открывающей скобкой любого типа, то мы помещаем его в стек. Если символ является закрывающей скобкой, то берем из стека последнюю сохраненную открывающую скобку и проверяем на соответствие. Если не совпадают - ошибка несоответствия скобок, если стек пустой, то ошибка лишней закрывающей скобки. Если конец строки достигнут, но стек не пустой, то ошибка незакрытых скобок. Как видите, решение целиком построено на работе со стеком, а Ассемблер предоставляет для этого все возможности. Переходим к программированию.
  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)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 4831 | Комментариев: 2

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

Комментарии

Отзывы посетителей сайта о статье
Ret (28.12.2012 в 19:32):
Даа, надо бы попробовать написать свой парсер для конфигов ;)
- парсинг вложенных секций
- комментарии
- списки
итд.
похоже на очередной велосипед, но это не совсем так, ini под описание не подходит, xml как бы это сказать, в общем не торт
Студент (01.02.2011 в 07:07):
Огромное Вам спасибо... :3

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

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

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.06 сек. / MySQL: 2 (0.0037 сек.) / Память: 4.5 Mb
Наверх