
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.169] |
![]() |
|
Сообщ.
#1
,
|
|
|
Good evening, All.
Помогите с разбором арифметической строки (с возможностью использования переменных). Желательно с исходниками. Thanks in advance. |
Сообщ.
#2
,
|
|
|
Создаешь простой анализатор строки.
ar_str - входная строка arg - строковый массив аргументов Например такого типа for (i=0;i<strlen(ar_str);i++) switch (ar_str[i]) { case '0..9','.' :arg[j]=arg[j]+ar_str[i];break; case '-','+','/','*' :arg[j];j++;break; } Таким образом получаешь массив arg. К примеру для 1324.343+563/54-5*7 получишь arg[0]=1324.343 arg[1]=+ arg[2]=563 arg[3]=/ arg[4]=54 arg[5]=- arg[6]=5 arg[7]=* arg[8]=7 Если обратишь внимание, то все операции располагаются либо на четных либо на нечетных местах (если не учесть скобки). Дальше остается только провести анализ операций таким же switch'ем и определив приоритет вычислить. ;D ;D ;D P.S. Это только первый наводящий шаг. Если дальше сам не сможешь сообщи ;D ;D ;D |
![]() |
Сообщ.
#3
,
|
|
Вот неск. примеров на паскале (а на TMT даже такая функция есть в стандартном модуле): ftp://copyhere.by.ru:ByBy@ftp.by.ru/pub/CALCS.RAR
А вот на VB (мой ;D): ftp://copyhere.by.ru:ByBy@ftp.by.ru/pub/Analyzer.rar |
Сообщ.
#4
,
|
|
|
http://www.sources.ru/cpp/cpp_mat_expression.shtml
|
Сообщ.
#5
,
|
|
|
Могу предложить более детальное опиание алгоритма
![]() ![]() <br><br>Алгоритм Рутисхаузера<br>Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например:<br><br>D:=((C-(B*L))+K)<br>Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:<br><br>1. если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;<br><br>2. если знак опеpации или закpывающаяся скобка, то уменьшается на 1.<br><br>Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом :<br><br> |-------|---------------------------------------|<br> |N симв.| 1 2 3 4 5 6 7 8 9 |<br> |-------|---------------------------------------|<br> |Символы| |<br> |строки | ( A + ( B * C ) ) |<br> |-------|---------------------------------------|<br> |Номера | |<br> |уровней| 1 2 1 2 3 2 3 2 1 |<br> |-------|---------------------------------------|<br><br>Алгоритм складывается из следующих шагов:<br><br>1. выполнить расстановку уровней;<br><br>2. выполнить поиск элементов строки с максимальным значением уровня;<br><br>3. выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними; <br><br>4. результат вычисления тройки обозначить вспомогательной переменной;<br><br>5. из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки; <br><br>6. выполнять п.п.2 - 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.<br><br>Пример разбора :<br> <br> |------------|--------------------------------------|<br> |Генерируемые| Выражение |<br> | тройки | |<br> |------------|--------------------------------------|<br> | | ( ( ( ( А + В ) * С ) / D ) - E ) |<br> | | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0|<br> | | |<br> |+ А В - > R | ( ( ( R * C ) / D ) - E ) |<br> | | 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 |<br> | | |<br> |* R C -> S | ( ( S / D ) - E ) |<br> | | 0 1 2 3 2 3 2 1 2 1 0 |<br> | | |<br> |------------|--------------------------------------|<br><br> |------------|-----------------------------------|<br> |Генерируемые| Выражение |<br> | тройки | |<br> |------------|-----------------------------------|<br> |/ S D -> Q | ( Q - E ) |<br> | | 0 1 2 1 2 1 0 |<br> | | |<br> |- Q E -> T | T |<br> |------------|-----------------------------------|<br><br>Алгоритм Бауэра и Замельзона<br>Из ранних стековых методов расматривается алгоритм Бауэра и Замельзона. Алгоритм использует два стека и таблицу функций перехода. Один стек используется при трансляции выражения, а второй - во время интерпретации выражения. Обозначения: Т - стек транслятора, Е - стек интерпретатора.<br><br>В таблице переходов задаются функции, которые должен выполнить транслятор при разборе выражения. Возможны шесть функций при прочтении операции из входной строки:<br><br>- f1 - заслать операцию из входной строки в стек Т; читать следующий символ стpоки;<br><br>- f2 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; заслать операцию из входной строки в стек Т; читать следующий символ стpоки;<br><br>- f3 - исключить символ из стека Т; читать следующий символ стpоки;<br><br>- f4 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; по таблице определить функцию для данного символа входной строки;<br><br>- f5 - выдача сообщения об ошибке;<br><br>- f6 - завершение работы.<br><br>Таблица переходов для алгебраических выражений будет иметь вид(символ $ является признаком пустого стека или пустой строки):<br><br> |----------|---------------------------------|<br> | | Операция из входной строки |<br> | |---------------------------------|<br> | | $ ( + - * / ) |<br> |----------|---|-----------------------------|<br> |Операция |$ | 6 1 1 1 1 1 5 |<br> |на вершине|( | 5 1 1 1 1 1 3 |<br> |стека Т |+ | 4 1 2 2 1 1 4 |<br> | |- | 4 1 2 2 1 1 4 |<br> | |* | 4 1 4 4 2 2 4 |<br> | |/ | 4 1 4 4 2 2 4 |<br> |----------|---|-----------------------------|<br><br>Алгоритм просматривает слева направо выражение и циклически выполняет следующие действия: если очередной символ входной строки является операндом, то он безусловно переносится в стек Е; если же операция, то по таблице функций перехода определяется номер функции для выполнения. Для выражения А+(В-С)*D ниже приводится последовательность действий алгоритма.<br><br> |-------|--------|-------|-------|----------|<br> |стек Е | стек Т |Входной|Номер | Тройка |<br> | | |символ |функции| |<br> |-------|--------|-------|-------|----------|<br> |$ | $ | A | | |<br> |$A | $ | + | 1 | |<br> |$A | $+ | ( | 1 | |<br> |$A | $+( | B | | |<br> |$AB | $+( | - | 1 | |<br> |$AB | $+(- | C | | |<br> |$ABC | $+(- | ) | 4 |- B C ->R |<br> |$AR | $+( | ) | 3 | |<br> |$AR | $+ | * | 1 | |<br> |$AR | $+* | D | | |<br> |$ARD | $+* | $ | 4 |* R D ->Q |<br> |$AQ | $+ | $ | 4 |+ A Q ->S |<br> |$S | $ | $ |Конец | |<br> |-------|--------|-------|-------|----------|<br><br> |