Уроки 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
В результате в стеке остаётся значение заданного выражения.
Следующая страница 
Скобочные выражения
Cкачать материалы урока
