Delphi World - Разбор арифметического (и не только) выражения - Алгоритм Бауэра и Замельзона
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Разбор арифметического (и не только) выражения - Алгоритм Бауэра и Замельзона

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

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

  1. f1 - заслать операцию из входной строки в стек Т; читать следующий символ стpоки;
  2. f2 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; заслать операцию из входной строки в стек Т; читать следующий символ стpоки;
  3. f3 - исключить символ из стека Т; читать следующий символ стpоки;
  4. f4 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; по таблице определить функцию для данного символа входной строки;
  5. f5 - выдача сообщения об ошибке;
  6. 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     | $      |  $    |Конец  |          |
    |-------|--------|-------|-------|----------|
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования