Blog. Just Blog

Быстрый поиск

Введите фрагмент названия статьи для поиска

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

28.01.2011 | Категория: Образ мышления: 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-подобных документов, при проверке синтаксиса каких-либо скриптов и т.п., так что главное уяснить принцип.

Читать статью целиком »
Просмотров: 7387 | Комментариев: 4

Динамо-фонарь + подзарядка мобильного телефона

26.01.2011 | Категория: Обзоры техники | Автор: ManHunter

Динамо-фонарь + подзарядка мобильного телефона

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

Читать статью целиком »
Просмотров: 64084 | Комментариев: 20

Решение примера в обратной польской нотации

21.01.2011 | Категория: Web-мастеру и не только | Автор: ManHunter
Обратная польская нотация - один из классических алгоритмов, используемых в вычислительной технике. Он используется для вычислений, и особенностью является следование символов операций за символами операндов, а также в отсутствии скобок. Если интересно, можете почитать описание алгоритма польской нотации. Листая сайт с вакансиями, я наткнулся на одно предложение работы, где в качестве тестового задания требовалось написать функцию, которая получает строку примера, записанного в обратной польской нотации, и возвращает результат вычислений. Сама вакансия для меня никакого интереса не представляла, с работой у меня все в порядке, а задание показалось интересным. Вот что у меня сперва получилось.
  1. // Польская нотация. Реализация алгоритма с рекурсией
  2. function polish_recursive($str) {
  3.     // подчистить строку и разделить ее на "стек"
  4.     $stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
  5.  
  6.     $cnt=count($stack);
  7.     // если в стеке более 1 элемента
  8.     if ($cnt>1) {
  9.         // debug
  10.         //echo join(' ',$stack).'<br>';
  11.  
  12.         // пройтись по стеку
  13.         for ($i=0$i<$cnt$i++) {
  14.             // знак арифметического действия?
  15.             if (in_array($stack[$i], array('-''+''*''/'))) {
  16.                 // слева осталось меньше двух цифр?
  17.                 if ($i<2) { return 'error'; }
  18.                 // выполнить операцию, записать в "стек" результат
  19.                 eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
  20.                 // изъять из "стека" операнды
  21.                 unset($stack[($i-1)]);
  22.                 unset($stack[($i-2)]);
  23.                 break;
  24.             }
  25.             else {
  26.                 // не арифметический знак и не число
  27.                 if (!is_numeric($stack[$i])) { return 'error'; }
  28.             }
  29.         }
  30.         // в стеке ничего не изменилось после выполнения цикла
  31.         if ($cnt==count($stack)) { return 'error'; }
  32.  
  33.         // следующий рекурсивный проход
  34.         $str=polish_recursive(join(' ',$stack));
  35.     }
  36.     // результат
  37.     return($str);
  38. }
В решении реализован псевдо-стек в массиве, а вычисление выполняется рекурсивно до получения результата или до перехода в состояние "ошибка". Соответственно, возвращается или результат, или сообщение о невозможности его получения.

Читать статью целиком »
Просмотров: 8431 | Комментариев: 7

Автомобильный FM-трансмиттер Jet.A Cabigu JA-16

20.01.2011 | Категория: Обзоры техники | Автор: ManHunter

Автомобильный FM-трансмиттер Jet.A Cabigu JA-16

Купил жене в машину FM-трансмиттер Jet.A Cabigu JA-16. Это мой первый опыт общения с подобными устройствами, так что выбирал, целиком положившись на интуицию. Ориентир был на внешний вид, функционал и стоимость, в итоге выбрал эту модель. Офсайт разработчика находится в перманентном состоянии "under construction", так что расскажу о трансмиттере поподробнее. Назначение устройств этого класса одно: передавать звук на заранее выбранной частоте на аудиосистему автомобиля. Это безусловно удобно, если ваша магнитола не имеет функции воспроизведения MP3-файлов или из-за конструктивных особенностей автомобиля заменить ее не представляется возможным (встроенная автомагнитола). Еще одно необычное применение FM-трансмиттера - это прослушивание музыки одновременно сразу в нескольких автомобилях, например, компанией на природе. Небольшого радиуса действия передатчика из одной машины как раз хватит.

Читать статью целиком »
Просмотров: 32373 | Комментариев: 14

Готовим салат из ананасов

17.01.2011 | Категория: А еще я туда ем! | Автор: ManHunter

Готовим салат из ананасов

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

Читать статью целиком »
Просмотров: 9252 | Комментариев: 9

01 ... 352 353 354 355 356 357 358 ... 426
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2025
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.12 сек. / MySQL: 2 (0.0252 сек.) / Память: 4.5 Mb
Наверх