Уроки 101 - 102
Модель и представление
(§55. Модель и представление)

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

Введение

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

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

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

Задачи

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

Построим программу, которая вычисляет арифметическое выражение, записанное в символьной строке. Для простоты будем считать, что в выражении используются только:

• целые числа;
• знаки арифметических действий + - * /.

Предположим, что выражение не содержит ошибок и посторонних символов.

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

Вспомните, что аналогичную задачу мы решали в § 43, где использовалась структура типа «дерево». Теперь мы применим другой способ.

Как вы знаете, при вычислении арифметического выражения последней выполняется крайняя справа операция с наименьшим приоритетом (см. § 43). Таким образом, можно сформулировать следующий алгоритм вычисления арифметического выражения, записанного в символьной строке s:

1. Найти в строке s последнюю операцию с наименьшим приоритетом (пусть номер этого символа записан в переменной k).

2. Используя дважды этот же алгоритм, вычислить выражения слева и справа от символа с номером к и записать результаты вычисления в переменные n1 и n2 (рис. 7.23).

Рис. 7.23

3. Выполнить операцию, символ которой записан в s[k], с переменными n1 и n2.

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

Основную функцию назовём Calc (от англ. calculate — вычислить). Она принимает символьную строку и возвращает целое число — результат вычисления выражения, записанного в этой строке. Алгоритм её работы на псевдокоде:

k:=номер символа, соответствующего последней операции

если k=0 то

знач:=перевести всю строку в число

иначе

nl:=результат вычисления левой части

n2:=результат вычисления правой части

знач:=применить найденную операцию к n1 и n2

все

Для того чтобы найти последнюю выполняемую операцию, будем использовать функцию LastOp из § 43. Если эта функция вернула 0, то операция не найдена, т. е. вся переданная ей строка — это число (предполагается, что данные корректны).

Теперь можно написать функцию Calc:

function Calc ( s: string )	:	integer;
var k, nl, n2: integer;
begin
k:=LastOp (s);
if k=0 then Calc:=StrToInt(s) {вся строка - число} 
else begin
n1:=Calc(Copy(s, 1, k—1));	(левая часть}
n2:=Calc(Copy(s, k+1, Length(s)-k));
			{правая часть} 
case s[k] of	{выполнить	операцию}
		'+': Calc:=n1+n2;
		'-': Calc:=n1-n2;
		'*': Calc:=nl*n2;
		'/': Calc:=n1 div n2; 
		end; 
	end; 
end;

Обратите внимание, что функция Calc — рекурсивная, она дважды вызывает сама себя.

Функции Calc и LastOp (а также функцию Priority, которая вызывается из LastOp) удобно объединить в отдельный модуль Model (модуль модели):

unit Model; 
interface
function Calc(s: string): integer;
implementation
uses SysUtils;
function Priority(op: char): integer; 
...
function LastOp(s: string): integer; 
...
function Calc(s: string): integer; 
...
end.

Секция interface этого модуля содержит только заголовок функции Calc — это всё, что доступно другим модулям программы. В секции implementation подключается модуль SysUtils (в котором находится функция StrToInt) и записаны все функции (многоточие обозначает тело функции). Таким образом, наша модель — это функции, с помощью которых вычисляется арифметическое выражение, записанное в строке.

Следующая страница Вычисление арифметических выражений: представление

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