Стек, очередь, дек | Вычисление арифметических выражений (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Уроки 74 - 76
Стек, очередь, дек
(§42. Стек, очередь, дек)



Содержание урока

Что такое стек?

Использование динамического массива

Вычисление арифметических выражений

Скобочные выражения

Очереди, деки

Вопросы и задания

Задачи


Вычисление арифметических выражений


Вы не задумывались, как компьютер вычисляет арифметические выражения, записанные в такой форме: (5 + 15) / (4 + 7 - 1)?

Такая запись называется инфиксной — в ней знак операции расположен между операндами (данными, участвующими в операции). Инфиксная форма неудобна для автоматических вычислений из-за того, что выражение содержит скобки и его нельзя вычислить за один проход слева направо.

В 1920 г. польский математик Ян Лукасевич предложил префиксную форму, которую стали называть польской нотацией. В ней знак операции расположен перед операндами. Например, выражение (5 + 15) / (4 + 7 - 1) может быть записано в виде

/ + 5 15 - + 4 7 1.

Скобки здесь не требуются, так как порядок операций строго определён: сначала выполняются два сложения (+   5   15 и +   4   7), затем вычитание, и, наконец, деление. Первой стоит последняя операция.

В середине 1950-х гг. была предложена обратная польская нотация, или постфиксная форма записи, в которой знак операции стоит после операндов:

5 15 + 4 7 + 1 - /

В этом случае также не нужны скобки, и выражение может быть вычислено за один просмотр с помощью стека следующим образом:

• если очередной элемент — число (или переменная), он записывается в стек;
• если очередной элемент — операция, то она выполняется с верхними элементами стека, и после этого в стек помещается результат выполнения этой операции.

Покажем, как работает этот алгоритм (стек «растёт» снизу вверх) (рис. 6.7).

Рис. 6.7

Рис. 6.7

В результате в стеке остаётся значение заданного выражения.

Следующая страница Скобочные выражения



Cкачать материалы урока







Наверх