Московский Государственный Университет леса
Кафедра “Прикладная Математика”
Курсовая работа
на тему:
“Расстановка скобок”
Выполнил: студент ФЭСТ
Группы ПМ-11 Сафин В.С.
Проверила: доцент кафедры ПМ Афанасьев А.В.
(Афанасьева В.В.)
г. Москва, 2013
1) Обзор литературы:
Арифметическое выражение – это запись математической формулы с использованием констант, переменных, функций, знаков арифметических операций и круглых скобок.
Константа – постоянная, не изменяющаяся величина.
Переменная – это величина, характеризующаяся множеством значений, которое она может принимать.
Скобки – парные знаки, используемые в математике для задания приоритета математических и логических операций.
2) Точная формулировка задачи:
III.2.7 Расставить скобки в арифметическом выражении, указав последовательность выполнения операций в соответствии с правилом старшинства
3) Расширенная формулировка задачи:
Расставить скобки в выражении по старшинству операций, т.е. операция “возведение в степень” самая старшая, затем “деление”, следующая операция “умножение”, а самые младшие операции “сложение” и “вычитание”.
4) Описание алгоритма:
1) Считываем входную строку посимвольно. Операнды заносим в один массив, операции в другой так, чтобы их индексы не пересекались (например, строку `a+b’ запишем вмассивы как: [`a’, “, `b’], [`’,’+’,”]).
2) Проходим по массиву операций, ищем операцию с максимальным приоритетом выполнения.
3) Когда находим, заменяем первый операнд этой операции на ` (+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) Блок–схема алгоритма
арифметическое выражение алгоритм программа
6) Реализация на языке ТР:
unit brackets;
interface
function isOperation (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;
implementation
function isOperation (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
begin
if ( (inString [i] = ‘ (‘) and (flag >= 0)) then
Inc (flag);
if (inString [i] = ‘) ‘) then
Dec (flag);
end;
if (flag = 0) then
bracketsBalance: = true
else
bracketsBalance: = false;
end;
function isRightExpression (inString: string): boolean; // проверка является ли введенное выражение правильным
var
prevFlag, curFlag, flag: boolean;
i: integer;
begin
flag: = true;
prevFlag: = isOperation (inString [1]);
for i: = 2 to Length (inString) do
begin
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
if ( (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;
priorities: array [1.100] of integer;
symbols: array [1.100] of string;
operand, bracketsExpression: string;
begin
m: = 1;
i: = 1;
while i <> Length (inString) + 1 do
begin
if (isOperation (inString [i]) = true) then // если текущий символ – операция
begin
symbols [m]: = operand; // заносим накопленный операнд в массив элементов выражения
operand: = ”; // обнуляем операнд
Inc (m); // переходим к следующей ячейке массива
priorities [m]: = getPriority (inString [i]); // заносим в массив приоритетов приоритет данной операции
symbols [m]: = inString [i]; // заносим операцию в массив элементов выражения
Inc (m); // переходим к следующей ячейке массива
Inc (count); // увеличиваем счетчик операций
end
else if (inString [i] = ‘ (‘) then
begin
while (inString [i + 1] <> ‘) ‘) do
begin
Inc (i);
bracketsExpression: = bracketsExpression + inString [i];
end;
symbols [m]: = arrangeBrackets (bracketsExpression);
Inc (m);
bracketsExpression: = ”;
if (i < Length (inString) – 1) then
Inc (i)
end
else
operand: = operand + inString [i];
Inc (i);
end;
symbols [m]: = operand;
while (count <> 0) do // пока не прошли по всем операциям
begin
maxPriority: = 0;
i: = 2;
while (i <> m) do
begin
if (priorities [i] >= maxPriority) then // ищем в массиве элементов выражения позицию оператора с наивысшим приоритетом
begin
maxPriority: = priorities [i];
maxPosition: = i;
end;
if (symbols [i] = ”) and (symbols [i + 1] <> ”) then // удаление из массива элементов выражения пустых ячеек (такое бывает после объединения двух операндов и операции)
begin
symbols [i]: = symbols [i + 1];
symbols [i + 1]: = ”;
priorities [i]: = priorities [i + 1];
priorities [i + 1]: = 0;
i: = 1;
end;
Inc (i);
end;
symbols [maxPosition – 1]: = ‘ (‘ + symbols [maxPosition – 1] + symbols [maxPosition] + symbols [maxPosition + 1] + ‘) ‘; // объединяем два операнда с операцией с максимальным приоритетом в одну ячейку, освободившиеся обнуляем
symbols [maxPosition]: = ”;
symbols [maxPosition + 1]: = ”;
priorities [maxPosition]: = 0;
Dec (count);
end;
arrangeBrackets: = symbols [1];
end;
procedure work;
var inString, outString: string;
expressionFlag: boolean;
begin
expressionFlag: = false;
while (expressionFlag <> true) do
begin
writeln (‘Please enter a source expression: ‘);
readln (inString);
expressionFlag: = isRightExpression (inString);
end;
outString: = arrangeBrackets (inString);
writeln (outString);
end;
procedure aboutProgram;
begin
writeln (‘Министерство образования и науки РФ’);
writeln (‘Московский Государственный Университет леса’);
writeln;
writeln;
writeln (‘Курсовая работа’);
writeln (‘по дисциплине: “Программирование”‘);
writeln (‘на тему: ‘);
writeln (‘”Расстановка скобок в арифметическом выражении”‘);
writeln;
writeln;
writeln (‘Выполнил: …’);
writeln (‘Проверил: …’);
writeln;
writeln;
writeln (‘Москва – 2013’);
end;
begin
end.
program III27;
uses CRT, brackets;
const s3 = ‘ Выход ‘;
s2 = ‘ О программе ‘;
s1 = ‘ Начать работу ‘;
Col = 15;
Fon = 0;
FonInv = Col;
ColInv = Fon;
var ActivStr: integer;
c: char;
procedure OverWrite; // вывод пунктов меню
begin
GotoXY (4, ActivStr);
case ActivStr of
7: write (s1);
8: write (s2);
9: write (s3);
end;
end;
Procedure Wind (k: integer); // управление меню с клавиатуры
begin
OverWrite;
ActivStr: = ActivStr + k;
if (ActivStr < 7) then
ActivStr: = 9;
if (ActivStr > 9) then
ActivStr: = 7;
TextBackGround (FonInv);
TextColor (ColInv);
OverWrite;
TextBackGround (Fon);
TextColor (Col);
end;
begin
Activstr: = 7;
while TRUE do
begin
TextBackGround (Fon);
TextColor (Col);
ClrScr;
GotoXY (10,3);
Writeln (‘Расстановка скобок’);
GotoXY (10,5);
Writeln (‘MENU’);
GotoXY (4,7);
WRITE (S1);
GotoXY (4,8);
WRITE (S2);
GotoXY (4,9);
WRITE (S3);
WIND (0);
repeat
c: = ReadKey;
if (c = #0) then
begin
c: = ReadKey;
if c = #38 then
WIND (-1);
if c = #40 then
WIND (1);
end;
until c = #13;
case ActivStr of
0:;
7: begin ClrScr; writeln (S1); work; readln; end;
8: begin ClrScr; writeln (S2); aboutProgram; readln; end;
9: begin ClrScr; writeln (S3); Delay (1000); Halt; end;
end;
ClrScr;
end;
end.
7) Примеры работы программы:
1.
2.
3.
4.
5.
6. В случае ошибки программа начинает работу заново:
8) Инструкция:
Запустив программу, пользователь видит диалоговое окно, в котором предлагается “Начать работу” с программой, узнать “О программе”или выйти из программы. Выбрав пункт “Начать работу” откроется окно, в котором предлагается ввести арифметическое выражение. Введя выражение, программа расставляет скобки по старшинству операций. Если выражение будет введено со скобками, то программа не изменит их, а если скобки будут не закрыты, то программа начнет свое действие заново.
9) Возможности для модификации:
1. Добавить функцию, которая расставляет порядок выполнения действий
2. Добавить функцию, которая осуществляет открытие файла (в котором содержится арифметическое выражение), и создающая новый файл, в котором это выражение было бы записано со скобками по возрастанию операций.
3. Сделать возможность расставления скобок в функциях (таких как sin, cos, tg, log и т.д.)
