Пресмятане на аритметичен израз
Задача: Да се направи програма, която изчислява израз, записан на език за прости аритметични изрази.
Езикът за аритметични изрази е следният:
операнди: цели числа от 0 до 9
оператори (всичките двуаргументни):
„+“ - събиране „-“ - изваждане „*“ - умножение „/“ - деление
кръгли скоби „()“ - указващи последователността на изпълнение.
Приоритетът на операторите е следният:
оператор приоритет *, / 2 +, - 1
Операндите, операторите и кръглите скоби са символи (tokens) от нашия език за прости аритметични изрази.
Три примерни израза:
3 - 2 + 1 стойност: 2 3 - (2 + 1) стойност: 0 5 - 2 / ((3 + 4 * 5 - 6 * 7) - 1) стойност: 5.1
Можем да решим задачата използвайки обратен полски запис.
Обратен полски запис
Когато има няколко оператора с еднакъв приоритет е нужно те да имат и еднаква асоциативност - лява или дясна. Примерно за израза 1 − 2 + 3 ако операторите са ляво-асоциативни резултатът ще е (1 − 2) + 3, докато ако са дясно асоциативни резултатът ще е 1 − (2 + 3). Операторът за повдигане на степен ^ е дясно асоциативен затова 2^3^4^5 се изчислява, като 2^(3^(4^5)).
В нашия език за прости аритметични изрази, всички оператори са ляво-асоциативни.
Прилагането на оператора + върху две числа, може да се запише по 3 начина:
с префиксен запис: + 1 2 с инфиксен запис: 1 + 2 с постфиксен запис: 1 2 +
Постфиксният запис се нарича още обратен полски запис (ОПЗ). Неговото предимство е, че не се нуждаем от скоби и не е нужно да знаем приоритета на операторите, за да извършим операциите.
Изразът 1 − (2 + 3) записан в обратен полски запис изглежда така: 1 2 3 + -
Изразът 9 - 3 * 4 - 2 * 5 записан в обратен полски запис изглежда така: 9 3 4 * - 2 5 * -
Ето алгоритъм за изчисляване на ОПЗ, използвайки стек:
Докато има символи в ОПЗ Прочитаме един символ Ако е операнд: Поставяме го в стека Иначе е оператор: Ако на върха на стека има по-малко от 2 операнда Грешка: Некоректни входни данни Иначе: Изваждаме 2 операнда от стека Прилагаме оператора върху тях. Първият изваден операнд е втори аргумент, а вторият - първи Поставяме получената стойност в стека Ако във стека има само един елемент: Това е резултатът Иначе: Грешка: Некоректни входни данни Край.
Трябва да внимаваме, когато прилагаме оператор върху измъкнатите от стека операнди, защото за някои оператори има значение кой операнд е първи и кой втори аргумент. Такива са операторите изваждане и деление. 1 - 2 е различно от 2 - 1.
Горният алгоритъм работи само ако всички оператори са двуаргументни. Ако имаме оператори с друг брой аргументи трябва вместо два, да извадим съответния брой операнди от стека.
Още за алгоритъма и ОПЗ в Wikipedia.
За да използваме горния алгоритъм първо трябва да приведем аритметичния израз от инфиксен в постфиксен запис (ОПЗ). Ето алгоритъм, който прави това, отново използвайки стек:
Докато има символи в израза: Прочитаме един символ. Ако символът е операнд (число) го добавяме в изходния запис. Ако символът е оператор, примерно оп1: Докато има оператор, оп2, на върха на стека, и той е с по-голям или равен приоритет от оп1: Измъкваме оп2 от стека и го поставяме в изходния запис. Поставяме оп1 в стека. Ако символът е отваряща скоба я поставяме в стека. Ако символът е затваряща скоба: Докато символът на върха на стека не стане отваряща скоба, измъкваме оператори от стека и ги поставяме в изходния запис. Премахваме отварящата скоба от стека, без да я поставяме в изходния запис. Ако стекът се изпразни без да е намерена отваряща скоба в него, значи има несъответствие на скобите в израза. Когато символите от входния израз свършат: Докато има символи в стека, измъкваме един: Ако символът на върха на стека е скоба (отваряща) значи има несъответствие на скобите в израза. Измъкваме оператор от стека и го поставяме в изходния запис. Край.
Разширен алгоритъм може да намерите в Wikipedia.
Програмата polish.cpp реализира двата алгоритъма и пресмята аритметичен израз. Тя използва файла queue.h от миналото упражнение и файла stack_no_elem.h. Във stack_no_elem.h е добавен методът peek, който взема елемента на върха на стека без да го премахва, и е премахната структурата Elem, защото тя вече е дефинирана веднъж във файла queue.h.
Сортиране чрез сливане
Процесът на съчетаване на две сортирани редици в една се нарича сливане.
Ако имаме сортираните списъци l1 и l2 и искаме да ги слеем в трети списък l, който също да бъде сортиран, можем да направим следното:
Докато има елементи в l1 и има елементи в l2: Ако l1.pStart->data < l2.pStart->data премахваме първия елемент на l1 и го поставяме в края на l Иначе премахваме първия елемент на l2 и го поставяме в края на l Като излезем от горния цикъл или l1 или l2 е празен Ако l1 е празен долепяме l2 към l Ако l2 е празен долепяме l1 към l Край.
За да сортираме един списък чрез сливане:
Ако списъкът има 0 или 1 елемент, то той е сортиран - Край Иначе го разделяме на 2 части Сортираме първата част - като използваме отново тази функция Сортираме втората част - като използваме отново тази функция Сливаме двете части в стария списък. Край.
Недостатъкът на този алгоритъм е, че не сортира на място и ако сортирахме масив щеше да ни е нужна допълнителна памет за още един масив. Разпределението на паметта за новия масив е бавна операция. Това обаче не важи за свързаните списъци. Също така при тях намирането на оста нужна при бързото сортиране (quick sort) не е толкова лесно. Затова за сортиране на списъци ще използваме сортирането чрез сливане.
В програмата merge_sort.cpp е реализирано сортирането чрез сливане. В нея е описан олекотен вариант на списък с метод void appFirstElem(List &aList), който премахва първия елемент от текущия списък и го добавя към края на списъка подаден, като параметър.
Самото сортиране се извършва в метода sort(), който изглежда така:
template <class T> void List<T>:: sort() { // сортира списъка, чрез сливане if(!pStart || !pStart->next) return; // ако е празен или само с 1 ел. е сортиран - излизаме List<T> l1, l2; // декларираме два помощни списъка // разделяне while(pStart) { // докато има нещо в текущия списък appFirstElem(l1); // добавяме първия му ел. в l1, if(pStart) appFirstElem(l2); // а следващия в l2 } // тук текущият списък вече е празен l1.sort(); l2.sort(); // сортираме двата списъка // сливане while(l1.pStart && l2.pStart) { // докато някой списък не свърши if(l1.pStart->data < l2.pStart->data) // добавяме по-малкия първи в текущия l1.appFirstElem(*this); // data трябва или да е от прост тип else l2.appFirstElem(*this); // или да има предефиниран оператор '<' } // единият списък е свършил, затова долепяме другия към текущия if(l1.pStart) { // ако l1 не е свършил, долепяме него pEnd->next = l1.pStart; pEnd = l1.pEnd; l1.pStart = l1.pEnd = NULL; } else { // иначе долепяме l2 pEnd->next = l2.pStart; pEnd = l2.pEnd; l2.pStart = l2.pEnd = NULL; } }
За да тествате времето за сортиране може да ползвате файла stopwatch.h. В него има 2 функции:
void stopwatchCalculateTime(unsigned time) - приема, като параметър време в наносекунди и го отпечатва в подходящ формат;
void stopwatchStart(void (*function)()) - приема, като параметър указател към функция и засича и отпечатва времето за нейното изпълнение.
След, като включим stopwatch.h в нашия код, ако имаме декларирана функция sort(), за да тестваме времето за нейното изпълнение е нужно да напишем: stopwatchStart(sort);. Ако sort() е метод на клас е нужно да напишем:
unsigned startTime, endTime; startTime = clock(); list.sort(); endTime = clock(); stopwatchCalculateTime(endTime - startTime);
Това е направено във файла merge_sort_test.cpp, който засича времето за сортиране на свързания списък.
Проблем: Искаме да направим програма, чрез която да обслужваме студентите, от някой голям университет, примерно някой от групата „redbrick“.
За целта сме направили клас Student, който съдържа следните данни: факултетен номер, име и фамилия на студента. Факултетният номер е уникален и чрез него ще идентифицираме студента. С нашата програма трябва да можем да добавяме и премахваме студенти и да променяме техните данни. За целта ще съхраняваме обекти от тип Student в някаква структура от данни. Каква да бъде тя? За да променим данни или да премахнем студент първо трябва да го намерим в структурата от данни. Търсенето трябва да става по факултетен номер, защото чрез него идентифицираме студентите.
Първата мисъл, която ни идва е да съхраняваме студентите в масив. Ако факултетните номера са индексите на масива, търсене реално няма да има, защото директно ще знаем кой студент, къде е разположен в масива. Факултетните номера, обаче не са последователни числа. Последният студент записан през 2007 г. е с номер 701261146, а първият записан през 2008 е 801261001. Това означава, че за индекси на масив не можем да използваме директно факултетните номера, тъй като голяма част от масива ще стои празен. Примерно на позициите от 790000000 до 800000000 няма да има нищо, също както на позиции от 1 до 100000. Освен това лесно се пресмята, че за масив с 800000000 елемента, всеки от по 20 байта са нужни повече от 100GB памет. Ако обаче напишем функция, която на факултетен номер еднозначно съпоставя индекс от масива, този проблем се решава.
Използването на масив обаче има недостатъци, а именно ниската скорост при добавянето и премахването на студент. При тези операции се налага да преоразмеряваме и преместваме масива, което отнема много време.
Друг вариант е да съхраняваме студентите в свързан списък. Добавянето на нов и премахването на студент от него става бързо. Търсенето обаче отнема много време, защото трябва да претърсим списъка (в най-лошия случай целия) докато намерим дадения студент.
Можем да обобщим нещата в следната таблица:
| Структура | Предимство | Недостатък |
|---|---|---|
| Масив | Директен достъп | Бавно добавяне и премахване |
| Свързан списък | Бързо добавяне и премахване | Бавно търсене |
Трябва да направим структура от данни, в която търсенето да е бързо и едновременно с това добавянето и премахването на елементи да не е толкова бавно. С други думи ще направим компромис по отношение и на двата вида операции, за да получим някакъв среден, задоволителен вариант.
Това може да стане ако вместо един голям списък имаме много на брой, но малки списъци. Можем да съхраняваме тези списъци в масив. Добавянето и премахването на студенти от тях ще става бързо. Търсенето в малък списък също не е толкова бавно. Но как ще разбираме кой студент, в кой списък се намира, за да знаем, в кой списък да го търсим? Трябва по някакъв точно определен начин да разпределим студентите в списъците.
Идеята за функция, която на факултетен номер съпоставя индекс от масива не е лоша, но този път няма да искаме това съпоставяне да е еднозначно, т.е. на два или повече факултетни номера, функцията ще съпоставя един и същ индекс от масива. Елементът с този индекс ще е списък, в който се намира студентът с дадения факултетен номер.
Сега за да намерим студент, остава просто да претърсим посочения от функцията списък. Тя ще ни посочва точния списък и когато искаме да добавим или премахнем студент.
Описаната по-горе структура от данни се нарича хеш таблица или хеш карта (hash map). Функцията, която на факултетен номер съпоставя индекс се нарича хеш функция. Индексът, който връща нашата хеш функция се нарича хеш стойност, хеш сума или просто хеш. Съпоставянето на едно и също число (индекс) на различни факултетни номера се нарича колизия. Целият процес на съхраняване и ефективно търсене и извличане на данни се нарича хеширане.
От съществено значение за хеширането е хеш функцията. Тя трябва да бъде избрана така, че списъците в хеш таблицата да бъдат с равна или близка дължина, защото ако имаме много дълги списъци, търсенето в тях ще бъде бавно.
Освен чрез масив от списъци са възможни и други реализации на хеш таблица.
Забележете, че ако имаме хеш таблица с 1000 списъка, при търсене на студент, хеш функцията ни посочва директно, в кой от тези списъци се намира студентът. 999 списъка веднага отпадат от областта за търсене. Аналогия може да се направи с двоичното търсене, при което на всяка стъпка, отпадат половината от елементите. Това ни подсеща за идеята да имаме хеш таблица от хеш таблици.
Реализация
Във файла student.h е поместен класът Student. Той име следните полета:
string fn;
string firstName;
string lastName;
Във файла student_list.h е класът List, който съдържа следните методи:
void add(Student aData); // добавя студент void remove(string fn); // премахва студента с ф.н. fn Student find(string fn); // намира и връща студента с ф.н. fn
Във файла hash.h е реализиран класът HashTable. Той има:
метод за добавяне на студент:
void add(Student student) { // добавя нов студент a[hash(student.fn)].add(student); }
метод за премахване на студент:
void remove(string fn) { // премахва студента с ф.н. fn a[hash(fn)].remove(fn); }
метод, който намира и връща студент:
Student find(string fn) { // намира и връща студента с ф.н. fn return (a[hash(fn)]).find(fn); }
За всеки символ от факултетния номер, хеш функцията умножава номера на неговата позиция по ASCII стойността му, след което събира тези произведения. Получената сума се дели на броя на списъците в хеш таблицата и се взема остатъкът от делението. Идеята с остатъка върши нелоша работа, когато входните данни са сравнително равномерно разпределени.
unsigned hash(string fn) { // хеш функция unsigned sum = 0; for(int i = 0; i < fn.length(); i++) { sum += (i+1) * fn[i]; } return sum % n; }
В програмата hash.cpp се демонстрира използването на хеш таблицата.
Други алгоритми за хеш функции може да намерите в Wikipedia.
За тези, на които им е интересно, могат да свалят файла hash_test.cpp в който се засича времето за търсене в хеш таблицата. Най-напред за броя на списъците въведете 1, което е все едно да имате списък вместо хеш таблица. За броя на студентите въведете 1 000 000 и вижте, за колко време се извършва търсенето. След това въведете 1000 за броя на списъците и отново 1 000 000 за броя на студентите. Сравнете двете времена за търсене.
