:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Разбор выражений. Компиляторы и интерпретаторы. » Классические алгоритмы
На правах рекламы
Гинекологические кресла от 9300р - гинекологическое кресло. Гинекологическая клиника 24 ч/сут.
  Разбор арифметического(и не только) выражения. Классические алгоритмы.



Алгоритм Рутисхаузера

Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например:

D:=((C-(B*L))+K)

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:

1. если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;

2. если знак опеpации или закpывающаяся скобка, то уменьшается на 1.

Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом :

      |-------|---------------------------------------|
      |N симв.| 1   2   3    4   5    6   7    8   9  |
      |-------|---------------------------------------|
      |Символы|                                       |
      |строки | (   A   +    (   B    *   C    )   )  |
      |-------|---------------------------------------|
      |Номера |                                       |
      |уровней| 1   2   1    2   3    2   3    2   1  |
      |-------|---------------------------------------|

Алгоритм складывается из следующих шагов:

1. выполнить расстановку уровней;

2. выполнить поиск элементов строки с максимальным значением уровня;

3. выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними;

4. результат вычисления тройки обозначить вспомогательной переменной;

5. из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;

6. выполнять п.п.2 - 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.

Пример разбора :
	 
     |------------|--------------------------------------|
     |Генерируемые|            Выражение                 |
     |   тройки   |                                      |
     |------------|--------------------------------------|
     |            |   ( ( ( ( А + В ) * С ) / D ) - E )  |
     |            | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0|
     |            |                                      |
     |+ А В - > R |      ( ( ( R * C ) / D ) - E )       |
     |            |    0 1 2 3 4 3 4 3 2 3 2 1 2 1 0     |
     |            |                                      |
     |* R C -> S  |          ( ( S / D ) - E )           |
     |            |        0 1 2 3 2 3 2 1 2 1 0         |
     |            |                                      |
     |------------|--------------------------------------|

     |------------|-----------------------------------|
     |Генерируемые|            Выражение              |
     |   тройки   |                                   |
     |------------|-----------------------------------|
     |/ S D -> Q  |         ( Q - E )                 |
     |            |       0 1 2 1 2 1 0               |
     |            |                                   |
     |- Q E -> T  |             T                     |
     |------------|-----------------------------------|

Алгоритм Бауэра и Замельзона

Из ранних стековых методов расматривается алгоритм Бауэра и Замельзона. Алгоритм использует два стека и таблицу функций перехода. Один стек используется при трансляции выражения, а второй - во время интерпретации выражения. Обозначения: Т - стек транслятора, Е - стек интерпретатора.

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

- f1 - заслать операцию из входной строки в стек Т; читать следующий символ стpоки;

- f2 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; заслать операцию из входной строки в стек Т; читать следующий символ стpоки;

- f3 - исключить символ из стека Т; читать следующий символ стpоки;

- f4 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; по таблице определить функцию для данного символа входной строки;

- f5 - выдача сообщения об ошибке;

- f6 - завершение работы.

Таблица переходов для алгебраических выражений будет иметь вид(символ $ является признаком пустого стека или пустой строки):

 |----------|---------------------------------|
 |          |     Операция из входной строки  |
 |          |---------------------------------|
 |          |     $   (   +   -   *   /   )   |
 |----------|---|-----------------------------|
 |Операция  |$  | 6   1   1   1   1   1   5   |
 |на вершине|(  | 5   1   1   1   1   1   3   |
 |стека Т   |+  | 4   1   2   2   1   1   4   |
 |          |-  | 4   1   2   2   1   1   4   |
 |          |*  | 4   1   4   4   2   2   4   |
 |          |/  | 4   1   4   4   2   2   4   |
 |----------|---|-----------------------------|

Алгоритм просматривает слева направо выражение и циклически выполняет следующие действия: если очередной символ входной строки является операндом, то он безусловно переносится в стек Е; если же операция, то по таблице функций перехода определяется номер функции для выполнения. Для выражения А+(В-С)*D ниже приводится последовательность действий алгоритма.

    |-------|--------|-------|-------|----------|
    |стек Е | стек Т |Входной|Номер  |   Тройка |
    |       |        |символ |функции|          |
    |-------|--------|-------|-------|----------|
    |$      | $      |  A    |       |          |
    |$A     | $      |  +    |    1  |          |
    |$A     | $+     |  (    |    1  |          |
    |$A     | $+(    |  B    |       |          |
    |$AB    | $+(    |  -    |    1  |          |
    |$AB    | $+(-   |  C    |       |          |
    |$ABC   | $+(-   |  )    |    4  |- B C ->R |
    |$AR    | $+(    |  )    |    3  |          |
    |$AR    | $+     |  *    |    1  |          |
    |$AR    | $+*    |  D    |       |          |
    |$ARD   | $+*    |  $    |    4  |* R D ->Q |
    |$AQ    | $+     |  $    |    4  |+ A Q ->S |
    |$S     | $      |  $    |Конец  |          |
    |-------|--------|-------|-------|----------|