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

Московский Государственный Университет леса Кафедра «Прикладная Математика»

Курсовая работа на тему:

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

Выполнил: студент ФЭСТ Группы ПМ-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 и т. д.)