2015-04-08
2554
Правило вычисления выражения в обратной польской записи состоит в следующем. Обратная польская запись просматривается слева направо. Если очередной элемент – операнд, то рассматривается следующий элемент. Если текущий элемент – знак операции, то выполняется эта операция над операндами, записанными левее знака операции. Результат операции записывается вместо первого (самого левого) операнда, участвовавшего в операции. Остальные элементы (операнды и знак операции), участвовавшие в операции, вычеркиваются из записи. Просмотр продолжается. В результате последовательного выполнения этого правила будут выполнены все операции в выражении, и запись сократится до одного элемента – результата вычисления выражения.
Для управления порядком выполнения операций над операндами используется скобочная запись выражений. При вычислении сначала вычисляется та часть выражения, скобочный уровень вложенности которой самый высокий. При наличии нескольких операторов с наивысшим скобочным уровнем, они вычисляются слева направо. При вычислении выражений с операциями, которым присвоен приоритет, или частично скобочных выражениях инфиксной формы записи, необходимо повторное сканирование слева направо. Повторное сканирование можно исключить, если инфиксное выражение преобразовать в постфиксную или префиксную форму записи.
|
|
|
Перечислим основные правила выполнения постфиксного выражения:
1) Найти в выражении крайний левый оператор.
2) Выбрать два операнда, стоящих непосредственно слева от найденного оператора.
3) Выполнить операцию.
4) Заменить оператор и операнды результатом.
5) Повторять указанные действия, пока не будут обработаны все операнды.
Постфиксное и префиксное выражения корректны тогда и только тогда, когда ранг выражения равен 1, а ранг любой правой головы польской формулы больше (меньше) или равен 1. Ранг корректного выражения равен 1.
Алгебраическое преобразование инфиксного выражения в обратное польское основано на приоритетах операторов и предлагает использование стека. Обратное польское выражение хранится в виде выходной строки, используемой в дальнейшем при генерации объектного кода.
В ходе преобразования инфиксного выражения в обратное польское порядок всех переменных и констант не меняется, а порядок операторов выходной строки соответствует их приоритетам.
| Символ | Приоритет | Ранг |
| +,– | –1 | |
| *, / | –1 | |
| A,b,…,z | ||
| Дно стека | – |
Рассмотрим пример преобразования инфиксного выражения a+b*c–d/e*h в обратное польское
| Сканируемый символ | Содержание стека | Обратная польская запись | Ранг |
| |– | |||
| А | |– a | ||
| + | |– + | a | |
| B | |– +b | a | |
| * | |– +* | ab | |
| С | |– +*c | ab | |
| – | |– – | abc*+ | |
| D | |– –d | abc*+ | |
| / | |– – / | abc*+d | |
| E | |– – / e | abc*+d | |
| * | |– – * | abc*+de/ | |
| H | |– – * h | abc*+de/ | |
| |– | |– | abc*+de/h*– |
Алгоритм преобразования.
|
|
|
1. В стек помещается признак пустого стека.
2. Значение приоритета очередного входного символа сравнивается с приоритетом верхнего элемента стека.
3. Если приоритет символа больше приоритета верхнего элемента стека, то символ помещается в стек, выбирается следующий входной символ.
4. Если приоритет входного символа меньше или равен приоритету верхнего элемента стека, то этот элемент удаляется из стека и помещается в формируемую строку, после чего сравнивается приоритеты очередного символа и нового верхнего символа.
Каждый раз при изменении обратной польской записи модифицируется ранг результирующего выражения.
