Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Обратная польская строка для арифметических выражений
Обратная польская строка (ОПС) является бесскобочной записью арифметических выражений. В отличии от обычной (инфиксной) записи, когда знак двуместной операции записывается между операндами, участвующими в операции, в ОПС вначале пишутся операнды, а затем – знак операции. При этом операнды могут быть простыми (переменными, константами), или сложными, т.е. результатами других операций. В табл. 10 приведены примеры формул в обычной записи и в виде ОПС.
Табл. 10
| № | Формула | ОПС |
| a + b | a b + | |
| a*(c + d) | a c d + * | |
| (x + y)*(a*x – b*y) | x y + a x * b y * – * |
Если в обычной записи формул необходимо учитывать приоритеты операций, то порядок исполнения действий в ОПС полностью определяется местоположением в ней знаков операций. Следует учесть, что при переходе от формулы к ОПС порядок простых операндов не изменяется.
В записи ОПС могут использоваться операции с различным числом операндов: с одним, двумя, тремя и т.д., и даже без операндов. При этом количество операндов определяется знаком операции. Поэтому, в частности, операция «унарный минус» и «бинарный минус» должны обозначаться различающимися знаками.
Вычисление по заданной ОПС можно выполнить интерпретатором, использующим магазин. В магазине сохраняются значения операндов и результаты вычислений. Принцип работы интерпретатора следующий. ОПС просматривается слева направо. Если очередной элемент в ОПС – операнд, то его значение записывается в магазин. Если очередной элемент в ОПС – операция, то из магазина считываются операнды для этой операции, после чего операция выполняется, а ее результат записывается в магазин. Если ОПС корректная, то после всех действий в магазине будет записано единственное значение – результат вычислений.
Пример 9. Дана формула a*(c + d). В табл. 11 приведены шаги алгоритма вычисления ОПС.
Табл. 11
| № шага | Входные символы | Содержимое магазина | |||
| a c d + * | |||||
| c d + * | a | ||||
| d + * | a | c | |||
| + * | a | c | d | ||
| * | a | c+d | |||
| a*(c+d) |
Конец примера.
Пример 10. Дана формула (x + y)*(a*x – b*y). В табл. 11 приведены шаги алгоритма вычисления ОПС.
Табл. 12
| № шага | Входные символы | Содержимое магазина | ||||
| x y + a x * b y * – * | ||||||
| y + a x * b y * – * | x | |||||
| + a x * b y * – * | x | y | ||||
| a x * b y * – * | x+y | |||||
| x * b y * – * | x+y | a | ||||
| * b y * – * | x+y | a | x | |||
| b y * – * | x+y | a*x | ||||
| y * – * | x+y | a*x | b | |||
| * – * | x+y | a*x | b | y | ||
| – * | x+y | a*x | b*y | |||
| * | x+y | a*x– b*y | ||||
| (x+y)*(a*x–b*y) |
Конец примера.
| <== предыдущая страница | | | следующая страница ==> |
| Детерминированный LL-разбор | | | Генерация ОПС для арифметических выражений |
Дата добавления: 2015-07-26; просмотров: 112; Нарушение авторских прав
Мы поможем в написании ваших работ!