Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Контрольная работа - №3 (Программирование)

.doc
Скачиваний:
12
Добавлен:
01.04.2014
Размер:
87.04 Кб
Скачать

Учреждение образования Белорусский Государственный Университет Информатики и Радиоэлектроники

Факультет заочного и дистанционного обучения

Специальность: Информатика

Контрольная работа по предмету

Программирования №3

Задание:

Написать программу расшифровки и вычисления арифметических выражений с использованием стека. В основе программы должны лежать два алгоритма:

a) преобразование арифметического выражения из инфиксной формы в постфиксную (форму обратной польской записи);

б) расшифровка и вычисление выражения в постфиксной форме. Для контроля вычислить выражение обычным образом.

Индивидуальный вариант №8 (Номер зачётной книжки 7 +1):

r = (d-c/x^e)*z+f*e

Замечание:

Процедура Power (возведение в степень) взята из модуля Math, а функцию для расчета факториала я написал сам.

Вот что получилось после компиляции:

Листинг программы:

unit PolishRecFrm;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Math;

type

TForm1 = class(TForm)

Formula: TEdit;

Calc: TButton;

Label1: TLabel;

Otvet: TEdit;

Label2: TLabel;

Polish: TEdit;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

procedure CalcClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Expression: string;

Razbor: TStringList;

implementation

{$R *.dfm}

(* Вычисляем факториал *)

function Factorial( ch: integer ): integer;

var

i: integer;

begin

if ch < 0 then

begin

Result := 2147483648; // 2147483647 + 1 - выход за пределы integer

Exit;

end;

Result := 1;

if ch = 0 then

Exit;

for i := 1 to ch do

Result := Result * i;

end;

(* Получение приоритета *)

function GetPriority( c: char ): byte;

begin

Result := 0;

case c of

'(': Result := 1;

'+', '-': Result := 2;

'*', '/': Result := 3;

'^', '!': Result := 4;

'c', 's', 'l', 'e': Result := 5;

'n': Result := 6;

end;

end;

(* Переводим строку с формулой в обратную польскую запись *)

procedure ParseString( s: string; var _Stack: TStringList );

var

Ms: TMemoryStream;

Temp: TStringList; // Временный стек для знаков и геометрических функций

flag: boolean;

begin

Temp := TStringList.Create;

Ms := TMemoryStream.Create;

Ms.WriteBuffer( s[1], Length( s ) );

Ms.Position := 0;

with TParser.Create( Ms ) do

begin

while Token <> toEof do

begin

// Если это число, помещаем его в выходной стек

if ( TokenString[1] in ['0'..'9'] ) then

if flag then

begin

_Stack[_Stack.Count-1] := _Stack[_Stack.Count-1] + TokenString;

flag := false;

end

else

_Stack.Add( TokenString );

// Если это разделитель дробной части

if ( TokenString[1] in [DecimalSeparator] ) then

begin

_Stack[_Stack.Count-1] := _Stack[_Stack.Count-1] + TokenString;

flag := true;

end;

// Если это знак (или геометрическая функция), то...

if ( TokenString[1] in ['+','-','/','*','^','!','c','s','l','n','e'] ) then

begin

// ...если стек пустой, помещаем знак в стек ...

if Temp.Count = 0 then

Temp.Add( TokenString )

else

begin

// ... если приоритер текущей операции выше, чем приоритет

// последней операции в стеке, помещаем знак в стек ...

if GetPriority( TokenString[1] ) > GetPriority( Temp.Strings[Temp.Count-1][1] ) then

Temp.Add( TokenString )

else

begin

// ... иначе извлекаем из стека все операции, пока

// не встретим операцию с более высшим приоритетом

while true do

begin

_Stack.Add( Temp.Strings[Temp.Count-1] );

Temp.Delete( Temp.Count-1 );

if Temp.Count = 0 then Break;

if GetPriority( TokenString[1] ) > GetPriority( Temp.Strings[Temp.Count-1][1] ) then

Break;

end;

// Не забываем добавить в стек текущую операцию

Temp.Add( TokenString );

end;

end;

end;

// Если это открывающая скобка, помещаем ее в стек операций

if ( TokenString[1] in ['('] ) then

Temp.Add( TokenString );

// Если это закрывающая скобка, извлекаем из стека операций в

// выходной стек все операции, пока не встретим открывающую скобку.

// Сами скобки при зтом уничтожаются.

if ( TokenString[1] in [')'] ) then

while true do

begin

if Temp.Count = 0 then Break;

if Temp.Strings[Temp.Count-1] = '(' then

begin

Temp.Delete( Temp.Count-1 );

Break;

end;

_Stack.Add( Temp.Strings[Temp.Count-1] );

Temp.Delete( Temp.Count-1 );

end;

NextToken;

end;

end;

Ms.Free;

// Если по окончании разбора строки с формулой, в стеке операций

// еще чтото осталось, извлекаем все в выходной стек

if Temp.Count <> 0 then

while Temp.Count <> 0 do

begin

_Stack.Add( Temp.Strings[Temp.Count-1] );

Temp.Delete( Temp.Count-1 );

end;

Temp.Free;

end;

(* Рассчитываем выражение в постфиксной форме *)

function Calculate( var _Stack: TStringList ): real;

var

i: integer;

a1, a2: real;

Temp: TStringList; // Временный стек для рассчетов

begin

Result := 0;

Temp := TStringList.Create;

for i := 0 to _Stack.Count-1 do

// Если зто число, помещаем его в стек для рассчета, иначе ...

if _Stack.Strings[i][1] in ['0'..'9'] then

Temp.Add( _Stack.Strings[i] )

else

begin

// ... Вынимаем из стека рассчета последнее число

a2 := StrToFloat( Temp.Strings[Temp.Count-1] );

Temp.Delete( Temp.Count-1 );

// если для выполнения операции требуется 2 аргумента,

// вынимаем из стека рассчета еще одно число

if _Stack.Strings[i][1] in ['+','-','/','*','^'] then

begin

a1 := StrToFloat( Temp.Strings[Temp.Count-1] );

Temp.Delete( Temp.Count-1 );

end;

// Производим рассчет

case _Stack.Strings[i][1] of

'+': Temp.Add( FloatToStr( a1 + a2 ) );

'-': Temp.Add( FloatToStr( a1 - a2 ) );

'/': Temp.Add( FloatToStr( a1 / a2 ) );

'*': Temp.Add( FloatToStr( a1 * a2 ) );

'^': Temp.Add( FloatToStr( Power( a1, a2 ) ) );

'!': Temp.Add( FloatToStr( Factorial( Round( a2 ) ) ) );

'c': Temp.Add( FloatToStr( cos( a2 ) ) );

's': Temp.Add( FloatToStr( sin( a2 ) ) );

'l': Temp.Add( FloatToStr( ln( a2 ) ) );

'n': Temp.Add( FloatToStr( -a2 ) );

'e': Temp.Add( FloatToStr( exp( a2 ) ) );

end;

end;

Result := StrToFloat( Temp.Strings[0] );

Temp.Free;

end;

procedure TForm1.CalcClick(Sender: TObject);

var

i: integer;

begin

Razbor.Clear;

Polish.Clear;

Expression := AnsiLowerCase( Formula.Text );

Expression := StringReplace( Expression, '+', ' + ', [rfReplaceAll, rfIgnoreCase] );

Expression := StringReplace( Expression, '-', ' - ', [rfReplaceAll, rfIgnoreCase] );

ParseString( Expression, Razbor );

for i := 0 to Razbor.Count-1 do

Polish.Text := Polish.Text + Razbor.Strings[i] + ' ';

Otvet.Text := FloatToStr( Calculate( Razbor ) );

end;

end.

Соседние файлы в предмете Программирование