Порядок выполнения работы. Вычисление выражений в польской записи

Вычисление выражений в польской записи

End

Begin

Begin

End

Begin

Begin

if S.top < Max then

S.top:= S.top + 1;

S.element:= x;

else Error(“Стек заполнен”);

end;

Операция выборки элемента из стека S производится функцией POP.

function Pop(var S: Stack): real;

if S.top > 0 then

Pop:= S.element[S.top];

S.top:= S.top - 1;

else Error(“Стек пустой”);

end;

Выражение, представленное в польской записи, можно вычислить за один просмотр слева направо. При этом для записи операндов и промежуточных результатов используется отек.

Алгоритм вычисления выражений в польской записи можно пред­ставить в виде следующей последовательности шагов.

1. Если текущий символ строки польской записи является опе­рандом, то его значение помещается в стек.

2. Если текущий символ является бинарным оператором, то он выполняется над двумя верхними элементами, выбранными из стека. Результат операции записывается в стек.

3. Если текущий символ входной строки - унарный оператор, то он применяется к верхнему элементу стека. Результат помещается в стек.

Шаги 1-3 повторяются до тех пор, пока не будут просмотрены все символы входной строки, представляющей собой польскую запись арифметического выражения. Результат вычисления выражения остает­ся в стеке.

Необходимо еще раз отметить, что стек используется дляхра­нения операндов. Каждый операнд записывается в стек по мере поя­вления. Следовательно, максимальный размер стека ограничен числом операндов, имеющихся в исходном выражении. Однако при работе с большинством постфиксных выражений фактический размер стека ока­зывается меньшим, чем максимальный, поскольку при выполнении каждой операции удаляются операнды из стека. При этом запись каждого промежуточного результата в стек делает его доступным в виде операнда для следующей операции.

В качестве примера рассмотрим вычисление выражения (2). Предположим, что операнды имеют следующие значения: a = 4, b = 1, c = 5, d = 64, e = 2, f = 5. Процесс вычислений по шагам приведен в следующей таблице.

Входной символ	Первый операнд	Второй операнд	Результат операции	Состояние стека
				...
a b - c * d e f ^ / +	a = 4     e = 2 d = 64	b = 1   c = 5   f = 5		a a	b c d d d d	e e	f

2.1. Для заданного арифметического выражения построить би­нарное дерево. Если выражение допускает одновременное выполнение нескольких операций над общими операндами, то при построении де­рева следует считать, что операции выполняются в порядке слева направо. Например, выражение
a + b + c следует рассматривать как (a + b) + с,а не как a + (b + c).

2.2. Получить постфиксную (польскую запись) и префиксную формы заданного арифметического выражения посредством обхода пост­роенного бинарного дерева.

2.3. Задать значения (целые числа) для переменных, вхо­дящих в исходное выражение. Желательно так подобрать эти значе­ния, чтобы конечный и промежуточные результаты вычислений также были бы целыми числами.

2.4. Выполнить вычисление арифметического выражения, пред­ставленного в польской записи, в соответствии с описанным выше алгоритмом. Процесс вычисления представить в виде таблицы.

2.5. Составить схему алгоритма вычисления выражений, представленных в польской записи.

2.6. Разработать программу вычисления арифметических выражений, представленных в польской записи.

Дата добавления: 2015-06-28