На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Arithmetical string.
    Good evening, All.

    Помогите с разбором арифметической строки (с возможностью использования переменных). Желательно с исходниками.

    Thanks in advance.
      Создаешь простой анализатор строки.
      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


        Вот неск. примеров на паскале (а на 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
          http://www.sources.ru/cpp/cpp_mat_expression.shtml
            Могу предложить более детальное опиание алгоритма
            ExpandedWrap disabled
               <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>
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0260 ]   [ 15 queries used ]   [ Generated: 4.03.24, 08:34 GMT ]