Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями

м
нет описания правки
Нет описания правки
мНет описания правки
 
Рассмотрим запись арифметческих выражений, в которых
сначала следуют два операнда арифметической операции,
|}
 
Это нотация записи выражений называется [[w:Обратная польская нотация|обратной польской записью]] (Reverse Polish Notation, RPN).
Заметьте, что скобки в обратной польской нотации не нужны. В частности,
В теории языков программирования эта нотация называется ''постфиксной нотацией'. Обычная нотация называется алгебраической или ''инфиксной нотацией''.
если во втором примере мы опустим скобки,
Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке [[:w:LISP]]
 
Заметьте, что скобки в обратной польской нотации не нужны. В частности, если во втором примере мы опустим скобки,
выражение по прежнему будет интерпретироваться однозначно.
 
Транслятор этих RPN-выражений основан на [[w:Стек|стэке]]. Каждое следующее число
помещается в стэк. Если встречается знак операции, то два числа из стэка извлекаются (a = pop(), b = pop()), для них вычисляется значение соответствующей бинарной арифметической операции и результат помещается в стек ( push(a * b) ).
(a = pop(), b = pop()), для них вычисляется значение соответствующей бинарной арифметической операции и результат помещается в стек ( push(a * b) ).
 
 
'''Задача:''' Напишите программу-калькулятор арифметических выражений записанных в обратной польской ноации.
 
НИжеНиже приведена постая реализация такого калькулятора на CСи. Заметим, что в ней нет никаких проверок ошибок ввода (если первый символ есть знак операции, она "умрёт"), а также стэк с его операциями pop и push не выделен в явную структуру.
Роль стэка играет обычный массив (stack[1000]). Переменная <tt>sp</tt> (stack pointer) равна количеству элементов в стеке.
Число (<tt>sp</tt>-1) равно индексу ячейки, являющейся вершиной стека.
481

правка