<<
>>

Постфиксная нотация выражения

Выражение в постфиксной нотации определяется так:

? Постфиксная нотация константы или переменной — это сама константа или переменная.

? Применение операции ор к подвыражениям Е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. Если на входе нет элементов, выталкивать из стека все операции на выход.

<< | >>

Еще по теме Постфиксная нотация выражения:

  1. Прерывание нотаций:
  2. Разговорные фразы и выражения
  3. Разговорные фразы и выражения
  4. Правило выражения глаз
  5. Код выражения лица
  6. Код выражения лица
  7. Код выражения лица
  8. Код выражения лица
  9. ЧИТАЯ КОД ВЫРАЖЕНИЯ ЛИЦА
  10. ЧИТАЯ КОД ВЫРАЖЕНИЯ ЛИЦА
  11. Код выражения лица
  12. Код выражения лица
  13. Код выражения лица