Есть такая классическая задача по программированию: проверка правильности расстановки скобок в строке, или иначе проверка баланса скобок. Суть задачи заключается в том, что есть произвольное математическое выражение, записанное в строку, в этом выражении используется три вида скобок "( )", "[ ]" и "{ }", последовательность и вложенность может быть любая. Требуется проверить, все ли скобки закрыты, соответствует ли каждая закрывающая скобка открывающей и нет ли лишних закрывающих скобок. В разных интернетах есть решения на различных языках программирования, я решил добавить свое решение на Ассемблере, тем более, что он идеально подходит для реализации этого алгоритма.
Решение заключается в том, что мы двигаемся по строке с самого начала, перебирая все символы по одному. Если символ является открывающей скобкой любого типа, то мы помещаем его в стек. Если символ является закрывающей скобкой, то берем из стека последнюю сохраненную открывающую скобку и проверяем на соответствие. Если не совпадают - ошибка несоответствия скобок, если стек пустой, то ошибка лишней закрывающей скобки. Если конец строки достигнут, но стек не пустой, то ошибка незакрытых скобок. Как видите, решение целиком построено на работе со стеком, а Ассемблер предоставляет для этого все возможности. Переходим к программированию.
;------------------------------------------------------------------------
; Функция проверки правильности расстановки скобок в выражении
; На входе: указатель на строку ASCIIZ
; На выходе: EAX - результат проверки выражения
; 0 - скобки расставлены правильно
; 1 - ОШИБКА: скобки не совпадают
; 2 - ОШИБКА: закрывающая скобка без открывающей
; 3 - ОШИБКА: открывающая скобка без закрывающей
;------------------------------------------------------------------------
proc CheckBrackets str:DWORD
local res:DWORD ; Результат
pusha ; Сохранить все регистры
mov esi,[str] ; Указатель на строку
cld
xor ecx,ecx ; Глубина стека
mov [res],0 ; Результат проверки
.scan_expr:
lodsb ; Прочитать символ из строки
or al,al ; Конец строки достигнут?
jz .finish
; Проверить открывающие скобки
cmp al,'['
je .push_bracket
cmp al,'('
je .push_bracket
cmp al,'{'
je .push_bracket
; Проверить закрывающие скобки
cmp al,']'
je .pop_bracket
cmp al,')'
je .pop_bracket
cmp al,'}'
je .pop_bracket
jmp .scan_expr ; Следующий символ
; Занести скобку в стек
.push_bracket:
inc ecx ; Увеличить счетчик
movzx eax,al ; Записать скобку в стек
push eax
jmp .scan_expr ; Следующий символ
; Извлечь скобку из стека
.pop_bracket:
or ecx,ecx ; В стеке ничего нет?
jne @f
; ОШИБКА: закрывающая скобка без открывающей
mov [res],2
jmp .finish
@@:
dec ecx ; Уменьшить счетчик
pop ebx ; Извлечь из стека скобку
; Проверить закрывающие скобки
cmp bl,'['
jne @f
cmp al,']' ; Скобки совпадают?
je .scan_expr ; Да, следующий символ
@@:
cmp bl,'('
jne @f
cmp al,')' ; Скобки совпадают?
je .scan_expr ; Да, следующий символ
@@:
cmp bl,'{'
jne @f
cmp al,'}' ; Скобки совпадают?
je .scan_expr ; Да, следующий символ
@@:
; ОШИБКА: скобки не совпадают
mov [res],1
or ecx,ecx ; В стеке пусто?
jz .exit ; Да, просто на выход
jmp .clean_stack ; Надо почистить стек
.finish:
or ecx,ecx ; Все проверили и в стеке пусто?
jz .exit ; Да, скобки расставлены правильно
; ОШИБКА: открывающая скобка без закрывающей
mov [res],3
; Почистить стек от оставшихся скобок
.clean_stack:
pop eax
loop .clean_stack
.exit:
popa ; Восстановить все регистры
mov eax,[res]
ret
endp
Текст функции проверки подробно прокомментирован, так что в дополнительных пояснениях не нуждается. Тем более, что алгоритм был расписан словами выше. Где это можно использовать? Кроме различных калькуляторов подобные решения можно применять для валидации xml-подобных документов, при проверке синтаксиса каких-либо скриптов и т.п., так что главное уяснить принцип.
В приложении готовый пример и исходник программы, получающей от пользователя строку математического выражения и проверяющей ее на правильность расстановки скобок. Для проверки используется описанная выше функция.