Расстановка скобок в арифметическом выражении

Московский Государственный Университет леса

Кафедра "Прикладная Математика"

Курсовая работа

на тему:

"Расстановка скобок"

Выполнил: студент ФЭСТ

Группы ПМ-11 Сафин В.С.

Проверила: доцент кафедры ПМ Афанасьев А.В.

(Афанасьева В.В.)

г. Москва, 2013

1) Обзор литературы:

Арифметическое выражение - это запись математической формулы с использованием констант, переменных, функций, знаков арифметических операций и круглых скобок.

Константа - постоянная, не изменяющаяся величина.

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

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

2) Точная формулировка задачи:

III.2.7 Расставить скобки в арифметическом выражении, указав последовательность выполнения операций в соответствии с правилом старшинства

3) Расширенная формулировка задачи:

Расставить скобки в выражении по старшинству операций, т.е. операция "возведение в степень" самая старшая, затем "деление", следующая операция "умножение", а самые младшие операции "сложение" и "вычитание".

4) Описание алгоритма:

1)      Считываем входную строку посимвольно. Операнды заносим в один массив, операции в другой так, чтобы их индексы не пересекались (например, строку ‘a+b’ запишем вмассивы как: [‘a’, ‘‘, ‘b’], [‘’,’+’,’’]).

2)      Проходим по массиву операций, ищем операцию с максимальным приоритетом выполнения.

)        Когда находим, заменяем первый операнд этой операции на ‘ (+operand1+operation+operand2+) ’, производим сдвиг остальных элементов массива на пустые места. Переходим к пункту 2.

Процедура OverWrite - выводит пункты меню в графической оболочке

Процедура Wind (k: integer) - управление меню с клавиатуры

Функция isOperation (symbol: char): boolean - проверка является ли символ операцией

Функция isRightExpression (inString: string): boolean - проверка правильности введенного выражения

Функция getPriority (symbol: char): integer - возвращает приоритет операции

Функция arrangeBrackets (inString: string): string - расставляет скобки в выражении

Процедура Work - пункт меню, запускающий программу

Процедура aboutProgram - пункт меню, в котором указаны сведения о программе

5) Блок-схема алгоритма

арифметическое выражение алгоритм программа

) Реализация на языке ТР:

unit brackets;

interfaceisOperation (symbol: char): boolean;

function bracketsBalance (inString: string): boolean;

function isRightExpression (inString: string): boolean;

function getPriority (symbol: char): integer;

function arrangeBrackets (inString: string): string;

procedure work;

procedure aboutProgram;

implementationisOperation (symbol: char): boolean; // проверка является ли символ операцией

begin

isOperation: = false;

case symbol of

'+': isOperation: = true;

'-': isOperation: = true;

'*': isOperation: = true;

'/': isOperation: = true;

'^': isOperation: = true;

end;

end;

function bracketsBalance (inString: string): boolean; // проверка баланса скобок

var

flag, i: integer;

begin

flag: = 0;

for i: = 1 to Length (inString) do( (inString [i] = ' (') and (flag >= 0)) then

Inc (flag);

if (inString [i] = ') ') then

Dec (flag);

end;

if (flag = 0) then

bracketsBalance: = true

else

end;

function isRightExpression (inString: string): boolean; // проверка является ли введенное выражение правильным

var

prevFlag, curFlag, flag: boolean;: integer;

begin

flag: = true;: = isOperation (inString [1]);

for i: = 2 to Length (inString) do

curFlag: = isOperation (inString [i]);

if ( (prevFlag = true) and (curFlag = true)) then

flag: = false; // если предыдущий и текущий символы - операции, то выражение неправильное

prevFlag: = curFlag;

end;

if (flag = true) then

isRightExpression: = bracketsBalance (inString)

else

isRightExpression: = flag;

end;

function getPriority (symbol: char): integer; // получение приоритета операции для правильной расстановки скобок, чем выше приоритет - тем раньше выполняется операция

begin( (symbol = '-') or (symbol = '+')) then

getPriority: = 1

else if (symbol = '*') then

getPriority: = 2

else if (symbol = '/') then

getPriority: = 3

else if (symbol = '^') then

getPriority: = 4;

end;

function arrangeBrackets (inString: string): string;

var

i, m, count, maxPriority, maxPosition: integer;: array [1.100] of integer;: array [1.100] of string;, bracketsExpression: string;

begin

m: = 1;: = 1;

while i <> Length (inString) + 1 do(isOperation (inString [i]) = true) then // если текущий символ - операция

begin

symbols [m]: = operand; // заносим накопленный операнд в массив элементов выражения: = ''; // обнуляем операнд(m); // переходим к следующей ячейке массива[m]: = getPriority (inString [i]); // заносим в массив приоритетов приоритет данной операции[m]: = inString [i]; // заносим операцию в массив элементов выражения(m); // переходим к следующей ячейке массива(count); // увеличиваем счетчик операций

endif (inString [i] = ' (') then(inString [i + 1] <> ') ') do

Inc (i);: = bracketsExpression + inString [i];

end;[m]: = arrangeBrackets (bracketsExpression);(m);: = '';

if (i < Length (inString) - 1) then

Inc (i)

end

operand: = operand + inString [i];(i);

end;[m]: = operand;

while (count <> 0) do // пока не прошли по всем операциям

begin

maxPriority: = 0;: = 2;

while (i <> m) do

begin(priorities [i] >= maxPriority) then // ищем в массиве элементов выражения позицию оператора с наивысшим приоритетом

begin

maxPriority: = priorities [i];: = i;

end;

if (symbols [i] = '') and (symbols [i + 1] <> '') then // удаление из массива элементов выражения пустых ячеек (такое бывает после объединения двух операндов и операции)

begin

symbols [i]: = symbols [i + 1];[i + 1]: = '';[i]: = priorities [i + 1];[i + 1]: = 0;: = 1;

end;(i);

end;[maxPosition - 1]: = ' (' + symbols [maxPosition - 1] + symbols [maxPosition] + symbols [maxPosition + 1] + ') '; // объединяем два операнда с операцией с максимальным приоритетом в одну ячейку, освободившиеся обнуляем[maxPosition]: = '';[maxPosition + 1]: = '';[maxPosition]: = 0;(count);

end;: = symbols [1];

end;

procedure work;

var inString, outString: string;: boolean;

begin

expressionFlag: = false;

while (expressionFlag <> true) do

writeln ('Please enter a source expression: ');(inString);: = isRightExpression (inString);

end;: = arrangeBrackets (inString);(outString);

end;

procedure aboutProgram;

begin

writeln ('Министерство образования и науки РФ');('Московский Государственный Университет леса');

writeln;;('Курсовая работа');

writeln;;('Выполнил: …');('Проверил: …');;;('Москва - 2013');

end;

begin.

program III27;

uses CRT, brackets;

const s3 = ' Выход ';

s2 = ' О программе ';= ' Начать работу ';

Col = 15;= 0;= Col;= Fon;

var ActivStr: integer;: char;

procedure OverWrite; // вывод пунктов меню

begin

GotoXY (4, ActivStr);

case ActivStr of

7: write (s1);

: write (s2);

: write (s3);

end;

end;

Procedure Wind (k: integer); // управление меню с клавиатуры

begin

OverWrite;: = ActivStr + k;

if (ActivStr < 7) then

ActivStr: = 9;

if (ActivStr > 9) then

ActivStr: = 7;(FonInv);(ColInv);;(Fon);(Col);

end;

begin

Activstr: = 7;

while TRUE do

TextBackGround (Fon);(Col);;(10,3);('Расстановка скобок');(10,5);('MENU');(4,7);(S1);(4,8);(S2);(4,9);(S3);(0);

repeat

c: = ReadKey;

if (c = #0) then

c: = ReadKey;

if c = #38 then

WIND (-1);

if c = #40 then

WIND (1);

end;

until c = #13;

case ActivStr of

0:;

: begin ClrScr; writeln (S1); work; readln; end;

: begin ClrScr; writeln (S2); aboutProgram; readln; end;

: begin ClrScr; writeln (S3); Delay (1000); Halt; end;

end;;

end;

end.

7) Примеры работы программы:

1.     

2.     

3.     

4.     

5.     

.        В случае ошибки программа начинает работу заново:

) Инструкция:

Запустив программу, пользователь видит диалоговое окно, в котором предлагается "Начать работу" с программой, узнать "О программе"или выйти из программы. Выбрав пункт "Начать работу" откроется окно, в котором предлагается ввести арифметическое выражение. Введя выражение, программа расставляет скобки по старшинству операций. Если выражение будет введено со скобками, то программа не изменит их, а если скобки будут не закрыты, то программа начнет свое действие заново.

9) Возможности для модификации:

1.      Добавить функцию, которая расставляет порядок выполнения действий

2.      Добавить функцию, которая осуществляет открытие файла (в котором содержится арифметическое выражение), и создающая новый файл, в котором это выражение было бы записано со скобками по возрастанию операций.

.        Сделать возможность расставления скобок в функциях (таких как sin, cos, tg, log и т.д.)