Расстановка скобок в арифметическом выражении
Московский Государственный
Университет леса
Кафедра "Прикладная
Математика"
Курсовая работа
на тему:
"Расстановка скобок"
Выполнил: студент ФЭСТ
Группы ПМ-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 и т.д.)