Постфиксная нотация выражения
? Постфиксная нотация константы или переменной — это сама константа или переменная.
? Применение операции ор к подвыражениям Е2 и Е2 записывается в виде Е2 Е2 ор.
Постфиксную нотацию иначе называют обратной польской записью.Примеры
Сумма х и у соответствует постфиксной записи х у +.
Произведение х у + и z записывается в следующей форме: х у + z *.
Значение выражения 20 30 + равно 50.
Значение выражения 20 30 + 60 * равно 50 60 * или равно 3000.
Значение выражения 20 30 60 + * равно 20 90 * или равно 1800. Преимущество: постфиксные выражения могут вычисляться механически, с помощью структуры данных типа стек. Так как в постфиксной нотации операция записывается сразу за своими операндами, то при считывании символа операции ее операнды уже известны. Следовательно, вычисление постфиксного выражения ЕР выполняется по алгоритму:
1. Если следующий элемент является операндом, помещаем его в стек.
2. Если очередной элемент обозначает символ п-арной операции, то п ее операндов должны находиться в верхних ячейках стека. Заменяем эти операнды на результат выполнения соответствующей операции.
Словом, алгоритм вычислений прост и легко реализуем. В большинстве компиляторов этот алгоритм является основой для генерации кода, вычисляющего выражения. В ходе компиляции выражения часто переводятся в постфиксную нотацию, а для вычисления выражения генератор кода применяет описанный выше алгоритм.
Для «ручного» преобразования исходного выражения в постфиксную нотацию в нем ищется первая (по выполнению) операция. Эта операция группирует (в постфиксной нотации) свои операнды, затем выбирается вторая операция и группирует свои операнды и т. д.
Примеры
а + Ь * с ^ (а + Ь) с * ^ а Ь + с * а * Ь + с ^ (а Ь *) + с ^ а Ь * с +
Формально подобное преобразование можно выполнять по алгоритму Дейкстры:
1. Проанализировать очередной элемент на входе.
2. Если это операнд, передать его на выход.
3. Если это «(», поместить ее в стек.
4. Если это операция, то:
■ если в вершине стека «(», поместить операцию в стек;
■ если у входной операции приоритет выше, чем у операции в вершине стека, поместить в стек новую операцию;
■ в противном случае — извлечь операцию из стека и отправить ее на выход, а затем повторить шаг 4.
102 |
Глава 4. Выражения и присваивания в языках программирования |
5. Если это «)», извлекать из стека операции на выход до тех пор, пока в вершине стека не окажется «(». Извлечь «(» из стека и уничтожить. 6. Если на входе еще есть элементы, перейти к шагу 1. 7. Если на входе нет элементов, выталкивать из стека все операции на выход.
Еще по теме Постфиксная нотация выражения:
-
Windows -
Архитектура компьютера -
Интернет -
Информатика -
Компьютер -
Компьютерные и телекоммуникационные системы -
Программирование -
Социальные сети -
-
Английский язык -
Астрология -
Астрономия -
Биология -
Военная литература -
Журналистика -
Компьютерная инженерия -
Педагогика -
Право -
Психология -
Социология -
Lecture.Center
|