. Алгоритмы и методы: Обратная польская запись (исходники)
Алгоритмы и методы: Обратная польская запись (исходники)

Алгоритмы и методы: Обратная польская запись (исходники)

Как правило арифметические выражения удобно преобразовывать в обратную польскую запись (ОПЗ), чтобы избавиться от скобок, содержащихся в выражении. Выражения, преобразованные в ОПЗ, можно вычислять последовательно, слева направо.

Существует два наиболее известных способа преобразования в ОПЗ. Рассмотрим коротко каждый из них:

1. Преобразование выражения в ОПЗ с использованием стека

Нам понадобится стек для переменных типа char, т.к. исходное выражение мы получаем в виде строки.

Рассматриваем поочередно каждый символ:1. Если этот символ - число (или переменная), то просто помещаем его в выходную строку.2. Если символ - знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.Получив один из этих символов, мы должны проверить стек:

3. Если текущий символ - открывающая скобка, то помещаем ее в стек.4. Если текущий символ - закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.

Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.

Рассмотрим алгоритм на примере простейшего выражения:Дано выражение: a + ( b - c ) * d

Рассмотрим поочередно все символы:

Символ Действие Состояние выходной строки после совершенного действия Состояние стека после совершенного действия a 'a' - переменная. Помещаем ее в выходную строку a пуст + '+' - знак операции. Помещаем его в стек (поскольку стек пуст, приоритеты можно не проверять) a + ( '(' - открывающая скобка. Помещаем в стек. a + ( b 'b' - переменная. Помещаем ее в выходную строку a b + ( - '-' - знак операции, который имеет приоритет 2. Проверяем стек: на вершине находится символ '(', приоритет которого равен 1. Следовательно мы должны просто поместить текущий символ '-' в стек. a b + ( - c 'c' - переменная. Помещаем ее в выходную строку a b c + ( - ) ')' - закрывающая скобка. Извлекаем из стека в выходную строку все символы, пока не встретим открывающую скобку. Затем уничтожаем обе скобки. a b c - + * '*' - знак операции, который имеет приоритет 3. Проверяем стек: на вершине находится символ '+', приоритет которого равен 2, т.е. меньший, чем приоритет текущего символа '*'. Следовательно мы должны просто поместить текущий символ '*' в стек. a b c - + * d 'd' - переменная. Помещаем ее в выходную строку a b c - d + * Теперь вся входная строка разобрана, но в стеке еще остаются знаки операций, которые мы должны просто извлечь в выходную строку. Поскольку стек - это структура, организованная по принципу LIFO, сначала извлекается символ '*', затем символ '+'.Итак, мы получили конечный результат: a b c - d * +

Реализацию алгоритма можно скачать здесь.Этот алгоритм также используется в программе Calc3, которая находится здесь (см. файл CPPNCalc.cpp).

2. Преобразование выражения в ОПЗ с помощью рекурсивного спуска Реализация данного алгоритма представляет собой несколько функций, последовательно вызывающих друг друга. Началом обработки выражения становится вызов функции begin(), которая обрабатывает сложение и вычитание (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции mult_div()). Функция begin() вызывает функцию mult_div(), обрабатывающую знаки деления и умножения (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции symbol()).. Далее функция mult_div() вызывает функцию symbol(), обрабатывающую переменные (или числа) и скобки. Если функция symbol() получает открывающую скобку, она вызывает функцию begin() (т.е. все начинается сначала) и ожидает закрывающей скобки, когда управление вновь возвращается к ней. Если она не дожидаестя закрывающей скобки, это означает, что в выражении содержится синтаксическая ошибка.Если функция symbol() получает переменную, то помещает ее в выходную строку.

Рассмотрим работу этих функций на примере исходного выражения:a + ( b - c ) * d

  1. Текущим символом является 'a'. Преобразование начинается с вызова функции begin(). Далее получаем цепочку вызовов begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'a' в выходную строку, заменяет текущий символ на '+' и возвращает управление. Состояние выходной строки: a
  2. Текущим символом является '+'. symbol() --> mult_div() --> begin(). Функция begin() запоминает текущий символ во временной переменной и заменяет его на '('. Состояние выходной строки: a
  3. Текущим символом является '('. begin() --> mult_div() --> symbol(). Функция symbol() заменяет текущий символ на 'b' и вызывает функцию begin(). Состояние выходной строки: a
  4. Текущим символом является 'b'. symbol()--> begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'b' в выходную строку, заменяет текущий символ на '-' и возвращает управление. Состояние выходной строки: a b
  5. Текущим символом является '-'. symbol() --> mult_div() --> begin(). Функция begin() запоминает текущий символ во временной переменной (поскольку эта переменная - локальная, это, конечно, не означает потерю символа '+', сохраненного ранее) и заменяет текущий символ на 'c'. Состояние выходной строки: a b
  6. Текущим символом является 'с'. begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'с' в выходную строку, заменяет текущий символ на ')' и возвращает управление. Состояние выходной строки: a b c
  7. Текущим символом является ')'. Поскольку закрывающую скобку ни одна функция не обрабатывает, функции поочередно возвращают управление, пока оно не возвратится к функции symbol(), которая обрабатывала открывающую скобку, т.е. цепочка будет такой: symbol() --> mult_div() --> begin(). (здесь функция begin() помещает сохраненный символ '-' в выходную строку) begin() --> symbol(). Далее функция symbol() заменяет текущий символ на '*' Состояние выходной строки: a b c -
  8. Текущим символом является '*'. symbol() --> mult_div() Функция mult_div() запоминает текущий символ во временной переменной и заменяет его на 'd' Состояние выходной строки: a b c -
  9. Текущим символом является 'd'. mult_div() --> symbol(). Функция symbol() помещает символ 'd' в выходную строку и возвращает управление. Состояние выходной строки: a b c - d
  10. Строка разобрана. Возвращение управления: symbol() --> mult_div() (здесь функция mult_div() помещает сохраненный символ '*' в выходную строку). Далее: mult_div() --> begin() (здесь функция begin() помещает сохраненный символ '+' в выходную строку) Состояние выходной строки: a b c - d * +

Реализация на С++ (для работы со строками и исключениями используются классы библиотеки VCL):

3. Алгоритм вычисления выражения, записанного в ОПЗ Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). Алгоритм очень прост. В качестве входной строки мы теперь рассматриваем выражение, записанное в ОПЗ: 1. Если очередной символ входной строки - число, то кладем его в стек. 2. Если очередной символ - знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек. Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.

📎📎📎📎📎📎📎📎📎📎