ЗМІСТ
Введення
1. Аналіз існуючих методів рішення задачі
2. Детальний опис використовуваних методів
3. Опис програми
3.1 Постановка завдання
3.2 Інтерфейс користувача
3.3 Детальний опис основної функції
3.4 Детальний опис функції ChartoInt
3.5 Детальний опис функції Scobka
3.6 Детальний опис функції Sumin
3.7 Загальна структура програмного засобу
4. Блок схема програми
4.1 Основна блок схема
4.2 Блок схема функції ChartoInt
4.3 Блок схема функції Sumin
4.4 Блок схема функції Scobka
5. Висновок
6. Програмна підтримка
7. Список літератури
8. Додаток 1
9. Додаток 2
Введення
Мова "C" є універсальною мовою програмування. Мова "C" - це мову щодо "низького рівня". Це означає, що "C" має справу з об'єктами того ж виду, що й більшість ЕОМ, а саме, з символами, числами та адресами. Вони можуть об'єднуватися і пересилатися за допомогою звичайних арифметичних і логічних операцій, здійснюваних реальними ЕОМ.
У мові "C" відсутні операції, що мають справу безпосередньо зі складовими об'єктами, такими як рядки символів, безлічі, списки або з масивами, розглянутими як ціле. Мова не надає ніяких інших можливостей розподілу пам'яті, окрім статичного визначення та механізму стеків, забезпечуваного локальними змінних функцій; тут немає ні "куп" (heap), ні "складання сміття". Нарешті, сам по собі "C" не забезпечує ніяких можливостей вводу-виводу: тут немає операторів read або write і ніяких вбудованих методів доступу до файлів. Всі ці механізми високого рівня повинні забезпечуватися явно викликаються функціями.
Аналогічно, мова "C" пропонує тільки прості, послідовні конструкції потоків управління: перевірки, цикли, групування і підпрограми, але не мультипрограмування, паралельні операції, синхронізацію або співпрограми. Мова "C" не є мовою із суворими типами в сенсі паскаля.
Нарешті, мова "C", подібно будь-якому іншому мови, має свої недоліки. Деякі операції мають невдале старшинство; деякі розділи синтаксису могли б бути краще; існує кілька версій мови, що відрізняються невеликими деталями. Тим не менш, мова "C" зарекомендував себе як виключно ефективний і виразну мову для широкого розмаїття застосувань програмування. [1]
Однією з головних причин, що лежать в основі появи мов програмування "високого рівня", з'явилися обчислювальні задачі, що вимагають великих обсягів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. У зв'язку з цим однією з перших областей системного програмування сформувалося дослідження способів трансляції виразів. Найбільшого поширення набув метод трансляції за допомогою зворотного користувача запису. [4] Методи вирішення задачі використання зворотного користувача запису детально розглянуті в цій роботі.
1. Аналіз існуючих методів рішення задачі
Існує безліч варіантів розв'язання завдання. На даний момент нам відомо 3 методу розв'язання задачі. 1 - з використанням стека, 2 - це, так зване подвійне використання стека, 3 - метод використання масивів.
Для порівняння наведу один із прикладів використання стека для вирішення даного завдання:
Очевидно, що одним з недоліків даного методу є складність використання методів, які без перебільшення можна назвати застарілими.
Так як сьогодні стек використовується за допомогою класів. Розглянемо приклад використання стека за допомогою класів:
class Stek
{Int something;
public:
Stek (); / / конструктор
~ Stek (); / / деструктор
void pop (int); / / помістити
int push (void); / / витягти
void print (); / / роздрукувати
}
Використання стека ефективно внаслідок того, що в асемблері не ефективно використовувалися масиви і є регістри стека:
ss - сегментний регістр стека,
sp / esp - регістр покажчика стека,
bd / ebd - регістр покажчика бази кадру стека,
Отже, реалізація масивів через стек була дуже ефективна. Тепер же ця проблема не критична для розробки програм, так як продуктивність ЕОМ велика. У С + + "вільно" використовуються масиви. У мовах "середнього" та "високого" рівня використання стека не принесе значущого прискорення, а навіть може уповільнити виконання програми. Внаслідок того, що поддежка реалізація стека на апаратному рівні у мові Сі + + відсутня, команди pop і push реалізуються через функції чи класи (див. приклад використання стека за допомогою класів). [6] До того ж використання масивів більш зручно, ніж використання стека, а так само легко переносимо на інші мови програмування і досить просто для розуміння.
2. Детальний опис використовуваних методів
Розглянемо детальний опис використовуваних методів на прикладі задачі реалізації калькулятора за допомогою методу зворотнього користувача запису.
У програмі вводиться рядок символів
Приклад: (1 +1) / 2 +12 / (8 / 2) =
Програмі необхідно оцінити склад рядка. Це реалізується через різні цикли, які визначають, чи є i-символ цифрою або знаком, потім скомпоновивают цифри в числа і кінцевим результатом цих дій, є 2 масиву.
Приклад:
Далі програма повинна розпізнати всі вирази в дужках і перетворити їх в числове значення.
Приклад: ... + (1 +2 / 2) / ... à ... +2 / ...
Для вирішення даної задачі, необхідно використовувати зрушення (детально описано в розділі 3.5)
Коли ж все дужки будуть перетворені на числові значення, програма починає перетворювати всі вирази "*" - множення, потім "/" - ділення, потім "+" - додавання і, нарешті "-" - віднімання в числові значення.
Приклад:
І в кінці програма видає відповідь.
Детально робота функцій описана в наступному розділі.
3. Опис програми
3.1 Постановка завдання
З клавіатури вводиться математичне вираження у вигляді рядка символів а) числових - 1234567890 і б) спеціальних */+-()=. В кінці вираження ставиться '=' або нічого (/ 0 - термінатор нуль). Програма оцінює вираз і якщо помилок немає - видає цілочисельний результат.
3.2 Інтерфейс користувача
На початку програми виводиться діалог вибору режиму роботи: налагоджувальний або простий:
Do you want to look the debugging information? (Y / Any key)
Якщо ж буде натиснута будь-яка клавіша крім 'y', то включиться простий режим роботи. Налагоджувальний режим розглядатися не буде.
Далі показується логотип та інформація про автора. Після всього цього виводиться рядок нумерації розрахунку:
<<<-------------[ Розрахунок N: 1 ]------------->>>
І на наступному рядку користувач пише деякий вираз:
1 +1 + (555/111) / 5 + (3 / 3 +6 / 6 +9 / 9) =
Або
1 +1 + (555/111) / 5 + (3 / 3 +6 / 6 +9 / 9)
Програма оцінить вираз і в разі відсутності помилок, видасть цілочисельний результат:
----------------------------
OTBET = 10
----------------------------
і виведе діалог повторення:
3 AHOBO? (Any key / n)
Якщо користувач натисне 'n' або 'N', то робота програми завершиться. Якщо ж буде натиснута будь-яка інша клавіша, то цикл повториться:
<<<-------------[ Розрахунок N: 2 ]------------->>>
І так далі.
Висновок результатів проілюстрований у додатку 2.
3.3 Детальний опис основної функції
Перейдемо безпосередньо до розгляду методів вирішення даної проблеми.
У програмі вводиться рядок символів, наприклад: (1 +1) / 2 +12 / (8 / 2) =
Програма сканує дану рядок з допомогою scanf ("% s", & S);
Далі необхідно визначити склад рядки:
for (i = 0; i <(m +1); i + +) {
if (S [i] == "1") {buf [i] = 1; l + +;}
else if (S [i] == '2 ') {buf [i] = 2; l + +;}
else if (S [i] == '3 ') {buf [i] = 3; l + +;}
else if (S [i] == '4 ') {buf [i] = 4; l + +;}
else if (S [i] == '5 ') {buf [i] = 5; l + +;}
else if (S [i] == '6 ') {buf [i] = 6; l + +;}
else if (S [i] == '7 ') {buf [i] = 7; l + +;}
else if (S [i] == '8 ') {buf [i] = 8; l + +;}
else if (S [i] == '9 ') {buf [i] = 9; l + +;}
else if (S [i] == 0 ") {buf [i] = 0; l + +;}
else if (l! = 0)
За допомогою функції ChartoInt перетворимо набір цифр у число, приклад: 1,2,4 у 124.
a [iKol] = ChartoInt (p, i, l);
iKol + +; / / лічильник кол-ва чисел
l = 0; / / обнулення лічильника довгі числа
}}
Далі проводиться виловлювання знака
switch (S [i]) {
case '+': b [k] = 1; k + +; break;
case '-': b [k] = 2; k + +; break;
case '*': b [k] = 3; k + +; break;
case '/': b [k] = 4; k + +; break;
case '\ 0': break; / / Завершення сканування якщо '\ 0'
case '(': b [k] = 5; u1 + +; k + +; break;
case ')': b [k] = 6; u2 + +; k + +; break;
default: break;}
Якщо зустрічаємо "=" то завершуємо сканування
if (S [i ]=='=') {break;} / / Завершення сканування
Якщо кількість відкритих дужок не дорівнює кількості закритих дужок то вихід
if (u 1! = u 2) {goto m 1;} / / Перевірка на к-ть дужок
Якщо все нормально, то використовуємо функцію Scobka
Scobka (a1, b1, iKol, k);
Після розрахунків виразів у дужках продовжуємо розрахунок у функції Sumin
c = Sumin (a1, b1, iKol, k);
Отримуємо результат і переводимо його в ціле значення s = (int) c;
І виводимо результат
printf ("\ r OTBET = [% i] \ n ", s);
Розглянемо роботу функцій: ChartoInt, Scobka, Sumit.
3.4 Детальний опис основної функції ChartoInt
Функція ChartoInt перетворює набір символів з рядка, набраної користувачем у числа. Перетворення відбувається таким чином, маємо деякі символи XYZ, програма перетворить їх так:
Визначається розрядність числа, скажімо сотні, отже, 1 число множиться на 100 + наступне число, помножене на 10 + наступне число, помножене на 1.
Приклад:
x, y, z à x * 100 + y * 10 + z * 1 = xyz
1,2,3 à 1 * 100 +2 * 10 +3 * 1 = 123
3.5 Детальний опис основної функції процедури Scobka
Функція Scobka перетворює всі вирази в дужках у числа, наприклад (2 +4 / 2) буде перетворено в 4.
Отримуємо масив даних і знаків через покажчики, скануємо масив знаків на відкриті та закриті дужки і позначаємо початок дужок через N, а кінець через N 1. Числа і знаки, що входять у цей проміжок, утворюють два нових масиву даних і знаків, але вже без дужок, після чого викликається функція Sumin і повертається чисельне значення дужок, який вставляється у вихідний масив чисел з проведенням зсуву даних та чисел.
Приклад:
Як ми бачимо, спочатку розкривається 1 дужка, вираження в ній розраховується і отже в масивах значень і чисел відбувається зрушення. Потім теж проробляється з другої дужкою. В кінці ми маємо масив значень складається тільки з знаків +, -, * і /.
3.6 Детальний опис основної функції процедури Sumin
Функція Sumin виробляє компонування числових і знакових масивів з використанням пріоритету операцій і последуйщего розрахунку результату.
Тобто у вираженні послідовно виконуються всі операції, спершу з множенням "*", потім з поділом "/", потім з складанням "+" і потім з вирахуванням "-".
Приклад: 12 +2 * 7-10/2 à 12 +14-10/2 à 12 +14-5 à 6-5 à 21
Детально робота функцій описана в додатку 1.
3.7 Загальна структура програмного засобу
4. Блок схема
4.1 Основна блок схема
4.2 Блок схема функції ChartoInt
4.3 Блок схема функції Sumin
4.4 Блок схема функції Scobka
5. Висновок
Даний метод не є оптимальним, тому що:
Не використовує класи.
"Зрушення" не винесено в окрему функцію, що ускладнює модернізацію.
Складність при спробі включення вкладених дужок
Складність при спробі включення математичних операцій таких як cos (), sin (), ступінь та інші.
Строге обмеження числового діапазону розрахунків
Відсутність "дружнього" - віконного інтерфейсу.
Можливе рішення даних проблем - це перехід на іншу платформу, Microsoft ® Visual C + + або Borland ® Delphi.
Додаток 1
Основний код програми
# Include <stdio. H>
# Include <conio.h>
# Include <string.h>
# Include <math.h>
int ChartoInt (int *, int, int);
double Sumin (int *, int *, int, int);
void Scobka (int *, int *, int, int);
char OTLADKA [1];
void main (void)
/*======================[ Початок ]======================= * /
{
char S [125];
int i, iKol, m, buf [125], a [100], b [100], k, * p, l, * a1, * b1, u1, u2, s, ABC;
double c;
mr:
puts ("Do Want to look the debugging information? (y / Any key)");
if (getch ()!=' y ') {puts ("Debugging information OFF"); OTLADKA [1] =' N ';}
else {puts ("Debugging information ON"); printf ("\ a"); OTLADKA [1] = 'Y';}
ABC = 1;
...
m1:
printf ("\ r Е <<<-------------[ Розрахунок N:% i ]------------->>> Е \ n", ABC);
scanf ("% s", & S);
...
if (OTLADKA [1] == 'Y') printf ("\ n **** Налагоджувальна інформація ***** \ n ");
m = strlen (S);
p = buf; a1 = a; b1 = b; / / покажчики
k = 0; iKol = 0; l = 0; u 1 = 0; u 2 = 0;
/ * Отримання числа спомощью функції і запис в масив а, де l-лічильник-довгі числа * /
for (i = 0; i <(m +1); i + +)
{
if (S [i] == "1") {buf [i] = 1; l + +;}
else if (S [i] == '2 ') {buf [i] = 2; l + +;}
else if (S [i] == '3 ') {buf [i] = 3; l + +;}
else if (S [i] == '4 ') {buf [i] = 4; l + +;}
else if (S [i] == '5 ') {buf [i] = 5; l + +;}
else if (S [i] == '6 ') {buf [i] = 6; l + +;}
else if (S [i] == '7 ') {buf [i] = 7; l + +;}
else if (S [i] == '8 ') {buf [i] = 8; l + +;}
else if (S [i] == '9 ') {buf [i] = 9; l + +;}
else if (S [i] == 0 ") {buf [i] = 0; l + +;}
else {if (l! = 0) {
a [iKol] = ChartoInt (p, i, l);
iKol + +; / / лічильник кол-ва чисел
l = 0; / / обнулення лічильника довгі числа
}
}
/ * Виловлювання знака і присвоювання йому номери 1-6 * /
switch (S [i]) {
case '+': b [k] = 1; k + +; break;
case '-': b [k] = 2; k + +; break; / / к-лічильник кол-ва знаків
case '*': b [k] = 3; k + +; break;
case '/': b [k] = 4; k + +; break;
case '\ 0': break; / / Завершення сканування якщо кінець
case '(': b [k] = 5; u1 + +; k + +; break;
case ')': b [k] = 6; u2 + +; k + +; break;
default: break;}
if (S [i ]=='=') {break;} / / Завершення сканування
}
if (u1! = u2) {goto m1;} / / Перевірка на к - ть дужок
Scobka (a 1, b 1, iKol, k); / / отримання відповіді
c = Sumin (a 1, b 1, iKol, k); / / присвоювання відповіді
s = (int) c; / / округлення до цілого числа
if (OTLADKA [1] == 'Y') printf ("\ n ***** OTLADKA INFO [END ]******* \ n");
puts ("Е ---------------------------- Е");
printf ("\ r OTBET = [% i] \ n", s); / / вивід відповіді
puts ("Е ---------------------------- Е");
printf ("\ [3AHOBO? (Any key / n)] \ r"); if (getch ()!==' n ') {goto m1;}
...
}
}
/*==================[ Кінець програми ]==================*/
int ChartoInt (int * p, int i, int l)
{
int a, j, b, b 2, m;
a = 0;
m = i +1- l; / / Обчислення початку роботи з масивом даних xx> [m] YYY> xxx
for (j = m; j <= (i +1); j + +) / / '1 3 лютому '=> 100 +20 +3 = 123
{
b = pow (10, (ij)); / / к - ть нулів
b 2 = p [j -1]; / / видобувають цифра
a = a + (b 2 * b); / / число1 + чісло2 + ... число N = число
}
return (a);
}
double Sumin (int * pa1, int * pb1, int j, int k)
{
int i, buf1, l;
double s;
/ * Початок сканування масиву даних і чисел з Визначення пріорететов * /
for (i = 0; i <= (k +1); i + +)
{
if (pb1 [i] == 3) //"*"
{
buf1 = pa1 [i] * pa1 [i +1]; / / множення x * y
pa 1 [i] = buf 1; / / присвоєння нового числа
for (l = (i +1); l <= (j +1); l + +) / / зрушення на к-ть xxx - cc * dd
{
pa 1 [l] = pa 1 [l +1]; / / зрушення цифр
if (l == j)
{
pa1 [l +1] = 0;
pa1 [j-1] = 0; / / для всіх
l + +;
j -; / / зменшення для того, щоб цикл не з'їв знаки і числа
/ / X * Yu X * Y = a => <a> - <u> "-" з'їв
}
}
for (l = i; l <= (k +1); l + +)
{
pb1 [l] = pb1 [l +1]; / / зрушення знаків
if (l == k)
{
pb1 [l +1] = 0;
l + +;
k -; / / зменшення для того, щоб цикл не з'їв знаки і числа
i -; / / зменшення для того, щоб цикл не з'їв знаки і числа}
}
}
if (pb1 [i] == 4) //"/"
{
buf1 = pa1 [i] / pa1 [i +1];
pa1 [i] = buf1;
for (l = (i +1); l <= (j +1); l + +)
{
pa1 [l] = pa1 [l +1];
if (l == j)
{
pa1 [l +1] = 0;
l + +;
j -;
}
}
for (l = i; l <= (k +1); l + +)
{
pb1 [l] = pb1 [l +1];
if (l == k)
{
pb1 [l +1] = 0;
l + +;
k -;
i -;
}
}
}
}
s = pa1 [0];
l = 0;
for (i = 0; i <= (k +1); i ++)// Виконання дій згідно знаку
{
if (pb1 [l] == 1) //"+"
{
s = s + pa1 [i +1];
l + +;
}
else if (pb1 [l] == 2) //"-"
{
s = s-pa1 [i +1];
l + +;
}
}
int j1 = 0;
return (s);
}
void Scobka (int * a1, int * b1, int l, int k1)
{
int i, n, n1, j, array [126], barray [126], * par, * pbr, iShift, p, j3, iPar, iSk;
double c1;
int as, as1; / / для налагодження
par = array; / / покажчики на масиви для передачі у функцію
pbr = barray;
iPar = 0; iSk = 0;
for (i = 0; i <= k1; i ++)// основний цикл
{
if (b1 [i] == 5) / / пошук дужок відкритих
{
if (iPar == 0) n = i; / / вказує на початок дужок
iPar + +;
}
if (b 1 [i] == 6) / / пошук дужок закритих
{
if (iPar! = 1)
{
iPar -;
iSk + +;
continue;
}
n1 = i; / / вказує на кінець дужок
p = 0; / / індекс для нових масивів
for (j = n; j <n1; j + +)
{
array [p] = a1 [j]; / / створення тимчасових масивів чисел
p + +;
as = p; / / для налагодження
}
p = 0;
for (j = (n +1); j <n1; j + +)
{
barray [p] = b1 [j]; / / створення тимчасових масивів знаків
p + +;
as 1 = p; / / для налагодження
}
if (iSk! = 0)
{
if (OTLADKA [1] == 'Y') Scobka (par, pbr, as, as1);
}
iShift = n 1 - n; / / "Зсув" слід звернути увагу - 1
c 1 = Sumin (par, pbr, iShift, (iShift -1)); / / сума повернення в дужках
if (OTLADKA [1] == 'Y') printf ("\ n Різна кількість дужок N =% f \ n", c 1);
a1 [n] = (int) c1;
for (j3 = 0; j3 <= iShift; j3 + +) / / очищення масивів можливо непотрібна
{
par [j3] = 0;
pbr [j3] = 0;
}
/*====================[ Зрушення ]========================= =* /
if (l> n1) / / l-кількість чисел у масиві a1 якщо за дужками нічого немає то для упращенія не потрібно
{
for (j = (n +1); j <l; j + +)
{
a1 [j] = a1 [j + iShift-1]; / / зрушення чисел
if (j == (l-iShift +1)) / / враховано що масив починається з нуля і точто зсув-1
{
for (j3 = (l-iShift +1); j3 <l; j3 + +) / / обнулення вийшли за межу даних
{
a 1 [j 3] = 0;
}
j = l; / / Вихід з зсуву циклу для масиву чисел
}
} / / Закриття циклу зсуву чисел
l-= (iShift-1); / / кількість чисел зменшилася
for (j = n; j <k 1; j + +)
{
b 1 [j] = b 1 [j + iShift +1]; / / зрушення знаків
if (j == (k 1 - iShift -2))
{
for (j 3 = (k 1 - iShift -1); j 3 <k 1; j 3 + +) / / обнулення вийшли за межу даних
{
b1 [j3] = 0;
}
j = k1; / / Вихід з зсуву масиву}
}
k1-= (iShift +1); / / кількість знаків зменшилася
i = 0; / / пробігти цикл з початку
} / / Закриває дужки перевірки на на необхідність зсуву
else if (l == n1)
{
a1 [n +1] = 0;
b1 [n] = 0;
}
}
}
}
Додаток 2
Виведення результатів.