Быстрый поиск
Введите фрагмент названия статьи для поиска
Проверка баланса скобок на Ассемблере
28.01.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
Есть такая классическая задача по программированию: проверка правильности расстановки скобок в строке, или иначе проверка баланса скобок. Суть задачи заключается в том, что есть произвольное математическое выражение, записанное в строку, в этом выражении используется три вида скобок "( )", "[ ]" и "{ }", последовательность и вложенность может быть любая. Требуется проверить, все ли скобки закрыты, соответствует ли каждая закрывающая скобка открывающей и нет ли лишних закрывающих скобок. В разных интернетах есть решения на различных языках программирования, я решил добавить свое решение на Ассемблере, тем более, что он идеально подходит для реализации этого алгоритма.Решение заключается в том, что мы двигаемся по строке с самого начала, перебирая все символы по одному. Если символ является открывающей скобкой любого типа, то мы помещаем его в стек. Если символ является закрывающей скобкой, то берем из стека последнюю сохраненную открывающую скобку и проверяем на соответствие. Если не совпадают - ошибка несоответствия скобок, если стек пустой, то ошибка лишней закрывающей скобки. Если конец строки достигнут, но стек не пустой, то ошибка незакрытых скобок. Как видите, решение целиком построено на работе со стеком, а Ассемблер предоставляет для этого все возможности. Переходим к программированию.
Code (Assembler) : Убрать нумерацию
- ;------------------------------------------------------------------------
- ; Функция проверки правильности расстановки скобок в выражении
- ; На входе: указатель на строку 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
Читать статью целиком »
Просмотров: 7387 | Комментариев: 4
Динамо-фонарь + подзарядка мобильного телефона
26.01.2011 | Категория: Обзоры техники | Автор: ManHunter
Динамо-фонарь + подзарядка мобильного телефона
Не могу пройти спокойно мимо павильонов торговой марки "Экспедиция". Все-таки молодцы ребята, что начали производить толковое оборудование и снаряжение для любителей походов, путешествий, активного и экстремального отдыха, да и просто для тех, кто проводит время на природе. Всех полезностей, производимых этой маркой, не перечислить, а вот одним недавним приобретением я хочу все-таки похвастаться. Это динамо-фонарь с подзарядкой для мобильных телефонов. Динамо-фонари не новинка, еще в детстве я игрался с фонариком-"жучком", который не требовал батареек и светил, когда быстро-быстро нажимали на его рычаг. Промежуточных аккумуляторов в нем не было, и лампочка фонарика гасла сразу, как только прекращалась работа динамо-машины. Идея подзарядки для мобильных устройств "с ручным приводом" также уже обрела воплощение в материале, но пока только в виде отдельных динамо-машинок. По крайней мере из того, что я встречал в продаже.
Читать статью целиком »
Просмотров: 64084 | Комментариев: 20
Решение примера в обратной польской нотации
21.01.2011 | Категория: Web-мастеру и не только | Автор: ManHunter
Обратная польская нотация - один из классических алгоритмов, используемых в вычислительной технике. Он используется для вычислений, и особенностью является следование символов операций за символами операндов, а также в отсутствии скобок. Если интересно, можете почитать описание алгоритма польской нотации. Листая сайт с вакансиями, я наткнулся на одно предложение работы, где в качестве тестового задания требовалось написать функцию, которая получает строку примера, записанного в обратной польской нотации, и возвращает результат вычислений. Сама вакансия для меня никакого интереса не представляла, с работой у меня все в порядке, а задание показалось интересным. Вот что у меня сперва получилось.Code (PHP) : Убрать нумерацию
- // Польская нотация. Реализация алгоритма с рекурсией
- function polish_recursive($str) {
- // подчистить строку и разделить ее на "стек"
- $stack=explode(' ',trim(preg_replace('/[[:space:]]{2,}/',' ',$str)));
- $cnt=count($stack);
- // если в стеке более 1 элемента
- if ($cnt>1) {
- // debug
- //echo join(' ',$stack).'<br>';
- // пройтись по стеку
- for ($i=0; $i<$cnt; $i++) {
- // знак арифметического действия?
- if (in_array($stack[$i], array('-', '+', '*', '/'))) {
- // слева осталось меньше двух цифр?
- if ($i<2) { return 'error'; }
- // выполнить операцию, записать в "стек" результат
- eval('$stack[$i]=$stack[($i-2)]'.$stack[$i].'$stack[($i-1)];');
- // изъять из "стека" операнды
- unset($stack[($i-1)]);
- unset($stack[($i-2)]);
- break;
- }
- else {
- // не арифметический знак и не число
- if (!is_numeric($stack[$i])) { return 'error'; }
- }
- }
- // в стеке ничего не изменилось после выполнения цикла
- if ($cnt==count($stack)) { return 'error'; }
- // следующий рекурсивный проход
- $str=polish_recursive(join(' ',$stack));
- }
- // результат
- return($str);
- }
Читать статью целиком »
Просмотров: 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
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 36,795 раз
Поблагодарили 36,795 раз
 |
2025 - ИЮНЬ |  |
||||
| Пн | Вт | Ср | Чт | Пт | Сб | Вс |
| 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 | ||||||
День швейной машинки
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 360 |
 |
 |