Глава 24. Примерна тема от изпит по програмиране – 8.04.2006 г.

Автор

Радослав Иванов

В тази тема...

В настоящата тема ще разгледаме условията и ще предложим решения на няколко примерни задачи от изпит в НАРС, проведен на 8.04.2006 г. При решаването на задачите ще се придържаме към съветите от темата "Как да решаваме задачи по програмиране" и ще онагледим прилагането им в практиката.

Съдържание

• Автор
• В тази тема...
• Задача 1: Броене на думи в текст
• Задача 2: Матрица с прости числа
• Задача 3: Аритметичен израз
• Упражнения
• Решения и упътвания
• Дискусионен форум

Задача 1: Броене на думи в текст

Напишете програма, която преброява думите в даден текст, който се въвежда от конзолата. Програмата трябва да извежда общия брой думи, броя думи, изписани изцяло с главни букви и броя думи, изписани изцяло с малки букви. Ако дадена дума се среща няколко пъти на различни места в текста, всяко срещане се брои като отделна дума. За разделител между думите се счита всеки символ, който не е буква.

Примерен вход:

Добре дошли в Национална академия по разработка на софтуер (НАРС)!

Примерен изход:

Общо думи: 10 Думи с главни букви: 1 Думи с малки букви: 7

Намиране на подходяща идея за решение

Интуитивно ни идва наум, че можем да решим задачата, като разделим текста на отделни думи и след това преброим тези, които ни интересуват.

Тази идея очевидно е вярна, но е прекалено обща и не ни дава конкретен метод за решаването на проблема. Нека се опитаме да я конкретизираме и да проверим дали е възможно чрез нея да реализираме алгоритъм, който да доведе до решение на задачата. Може да се окаже, че реализа­ци­ята е трудна и да се наложи да търсим друга идея.

Разбиване на задачата на подзадачи

Да се опитаме да дефинираме стъпките, които са ни необходими, за реша­ва­нето на проблема.

Най-напред, трябва да разделим текста на отделни думи. Това, само по себе си, не е проста стъпка, но е първата ни крачка към разделянето на проблема на по-малки, макар и все още сложни подзадачи.

Следва преброяване на интересуващите ни думи. Това е втората голяма подзадача, която трябва да решим. Да разгледаме двата проблема по отделно и да се опитаме да ги раздробим на още по-прости задачи.

Как да разделим текста на отделни думи?

За да разделим текста на отделни думи, първо трябва да намерим начин да ги идентифицираме. В условието е казано, че за разделител се счита всеки символ, който не е буква. Следователно първо трябва да идентифи­ци­раме разделителите и след това да ги използваме за разделянето на текста на думи.

Ето, че се появиха още две подзадачи – намиране на разделителите в текста и разделяне на текста на думи спрямо разделителите. Решения на тези подзадачи можем да реализираме директно.

За намиране на разделителите е достатъчно да обходим всички символи и да извлечем тези, които не са букви.

След като имаме разделителите, можем да реализираме разделянето на текста на думи чрез метода split(…) на класа String.

Как да броим думите?

Да предположим, че вече имаме списък с всички думи от текста. Искаме да намерим броя на всички думи, на тези изписани само с главни букви и на тези изписани само с малки букви.

За целта можем да обходим всяка дума от списъка и да проверим дали отговаря на някое от условията, които ни интересуват. На всяка стъпка увеличаваме броя на всички думи. Проверяваме дали текущата дума е изписана само с главни букви и ако това е така увеличаваме броя на думите с главни букви. Аналогично правим проверка и дали думата е изписана само с малки букви.

Така се появяват още две подзадачи – проверка дали дума е изписана само с главни букви и проверка дали е изписана само с малки букви? Те изглеждат доста лесни. Може би дори е възможно класът String да ни предоставя наготово такава функционалност. Проверяваме, но се оказва, че не е така. Все пак забелязваме, че имаме методи, които ни позволяват да преобразуваме символен низ в такъв съставен само от главни или само от малки букви. Това може да ни помогне.

За да проверим дали една дума е съставена само от главни букви е достатъчно да сравним думата с низа, който се получава след като я преобразуваме в дума съставена само от главни букви. Ако са еднакви, значи резултатът от проверката е истина. Аналогична е и проверката за малките букви.

Проверка на идеята

Изглежда, че идеята ни е добра. Разбихме задачата на под­за­да­чи и знаем как да решим всяка една от тях. Дали да не преминем към импле­ментацията? Пропуснахме ли нещо?

Не трябваше ли да проверим идеята, разписвайки няколко примера на хартия? Може би ще намерим нещо, което сме пропуснали? Можем да започнем с примера от условието:

Добре дошли в Национална академия по разработка на софтуер (НАРС)!

Разделителите ще са: интервали, (, ) и !. За думите получаваме: Добре, дошли, в, Национална, академия, по, разработка, на, софтуер, НАРС. Последните два разделителя са един след друг. Какво правим в този случай?

Открихме нещо, за което не бяхме помислили. Изглежда, че когато имаме няколко разделителя един след друг, трябва да ги третираме като един при разделянето на думите.

Преброяваме думите и получаваме коректен резултат. Пробваме още един пример съдържащ няколко последователни разделителя. Ако ги третираме като един, резултатът е коректен.

Изглежда идеята е добра и работи. Можем да пристъпим към импле­мен­та­цията. За целта ще имплементираме алгоритъма стъпка по стъпка, като на всяка стъпка ще реализираме по една подзадача.

Да помислим за структурите от данни

Задачата е проста и няма нужда от кой знае какви сложни структури от данни.

За разделителите в текста можем да ползваме String. При намирането им трябва да ползваме StringBuilder, тъй като построяваме низа чрез долепяне на символи.

За думите от текста можем да ползваме масив от низове String[] или ArrayList<String>.

Да помислим за ефективността

Има ли изисквания за ефективност? Колко най-дълъг може да е текстът? Понеже текстът се въвежда от конзолата, той едва ли ще е много дълъг. Никой няма да въведе 1 MB текст от конзолата. Можем да приемем, че ефективността на решението в случая не е застрашена.

Стъпка 1 – Намиране на разделителите в текста

Ще дефинираме метод, който извлича от текста всички символи, които не са букви и ги връща като символен низ, който след това можем да изпол­зва­ме за разделяне на текста на отделни думи:

static String extractSeparators(String text) {     StringBuilder separators = new StringBuilder();       int textLength = text.length();     for (int index = 0; index < textLength; index++) {         char character = text.charAt(index);           if (!Character.isLetter(character)) {             separators.append(character);         }     }       return separators.toString(); }

В началото на метода дефинираме обект от класа StringBuilder, в който ще натрупваме намерените разделители. Както споменахме в главата "Символни низове", този клас служи за построяване и промяна на символни низове и премахва проблемите с бързодействието при конка­тениране на низове.

В цикъл обхождаме всеки един от символите в текста. С по­мощ­та на метода isLetter(…) на класа Character, определяме дали текущия сим­вол е буква и ако не е, го добавяме към разделителите.

Накрая връщаме разделителите като символен низ.

Изпробване на метода extractSeparators(…)

Преди да продължим нататък е редно да изпробваме дали намирането на разделителите работи коректно:

public static void main(String[] args) {     String text = "This is wonderful!!! All separators like " +                 "these ,.(? and these /* are recognized. It works.";     String separators = extractSeparators(text);     System.out.println(separators); }

Стартираме програмата и виждаме дали разделителите са намерени коректно. Резултатът е следният:

!!!     ,.(?   /*  .  .

Изпробваме метода и в някои от граничните случаи – текст състоящ се от една дума без разделители, текст съставен само от разделители, празен низ. Изглежда, че методът работи и можем да продължим към реали­за­цията на следващата стъпка.

Стъпка 2 – Разделяна на текста на думи

За разделянето на текста на отделни думи ще използваме разделителите и с помощта на метода split(…) на класа String ще извършим разделянето.

Преди да подадем разделителите на метода split(…) трябва да добавим преди и след тях съответно [\\Q и \\E]+, понеже методът очаква като параметър регулярен израз.

На езика на регулярните изрази, квадратните скоби следвани от знак +, указват да бъде разпознато всяко срещане на последователност от един или повече от символите заградени в скобите. С \\Q и \\E указваме, че символите между тях трябва да бъдат третирани като обикновени символи, дори някой от тях да е със специално значение в езика на регулярните изрази. Това е наложително, понеже някой от нашите разделители може да се окаже специален символ, а ние искаме да го третираме като разделител.

Ето как изглежда нашият метод:

static String[] extractWords(String text) {     String separators = extractSeparators(text);       separators = "[\\Q" + separators + "\\E]+";             String[] words = text.split(separators);     return words; }

Преди да преминем към следващата стъпка остава да проверим дали методът работи коректно:

public static void main(String[] args) {     String text =         "Check it! Separators like $ and ^ should be recognized.";     String[] words = extractWords(text);     for (String word : words) {         System.out.print(word + " ");     } }

Резултатът е коректен:

Check it Separators like and should be recognized

Тук всичко е наред, но когато опитаме да тестваме метода с низ съдържащ само една дума и никакви разделители се хвърля изключение:

Exception in thread "main" java.util.regex.PatternSyntaxException: Unclosed character class near index 2 [\Q\E]+   ^     at java.util.regex.Pattern.error(Unknown Source)     at java.util.regex.Pattern.clazz(Unknown Source)     at java.util.regex.Pattern.sequence(Unknown Source)     at java.util.regex.Pattern.expr(Unknown Source)     at java.util.regex.Pattern.compile(Unknown Source)     at java.util.regex.Pattern.<init>(Unknown Source)     at java.util.regex.Pattern.compile(Unknown Source)     at java.lang.String.split(Unknown Source)     at java.lang.String.split(Unknown Source)     at WordsCounter.extractWords(WordsCounter.java:25)     at WordsCounter.main(WordsCounter.java:82)

Оказва се, че когато нямаме разделители, нашият регулярен израз е некоректен. Ако не бяхме тествали метода, грешката щеше да се прояви едва когато някой случайно въведе текст без разделители.

Можем лесно да решим проблема, като веднага след извличането на разделителите проверим дали има такива и ако няма, просто върнем като резултат масив съдържащ един елемент – целият текст:

String separators = extractSeparators(text);         if(separators.equals("")){     String[] words = new String[1];     words[0] = text;     return words; }

Проблемът е решен. Тестваме и други гранични случаи като низ съдържащ само разделители и празен низ. Резултатите са коректни.

Стъпка 3 – Определяне дали дума е изписана изцяло с главни или изцяло с малки букви

Вече имаме идея как да имплементираме тези проверки и можем директно да реализираме методите:

static boolean isUpperCase(String word) {     boolean result = word.equals(word.toUpperCase());     return result; }   static boolean isLowerCase(String word) {     boolean result = word.equals(word.toLowerCase());     return result; }

Изпробваме ги подавайки им думи съдържащи само главни, само малки и такива съдържащи главни и малки букви. Резултатите са коректни.

Стъпка 4 – Преброяване на думите

Вече можем да пристъпим към решаването на проблема – преброяването на думите. Трябва само да обходим списъка с думите и в зависимост каква е думата да увеличим съответните броячи, след което да отпечатаме резултата:

static void countWords(String[] words) {     int totalCount = 0;     int allUpperCaseCount = 0;     int allLowerCaseCount = 0;       for (String word : words) {         totalCount++;         if (isUpperCase(word)) {             allUpperCaseCount++;         } else if (isLowerCase(word)) {             allLowerCaseCount++;         }     }       System.out.printf("Total words count: %s\n", totalCount);     System.out.printf("Upper case words count: %s\n",             allUpperCaseCount);     System.out.printf("Lower case words count: %s\n",             allLowerCaseCount);      }

Нека проверим дали броенето работи коректно:

public static void main(String[] args) {     String[] words = {"This", "is", "our", "TEST", "case"};     countWords(words); }

Стартираме приложението и получаваме верен резултат:

Total words count: 5 Upper case words count: 1 Lower case words count: 3

Проверяваме резултатите и в граничните случаи, когато списъкът съдържа думи само с главни или само с малки букви, както и когато списъкът е празен.

Стъпка 5 – Вход от конзолата

Остава да реализираме и последната стъпка, даваща възможност на потребителя да въвежда текст:

static String readText() {     Scanner input = new Scanner(System.in);     System.out.println("Enter text:");     String text = input.nextLine();       return text; }

Проверката е лесна. Трябва само да въведем текст, след което да го отпечатаме в конзолата и да се уверим, че двата текста са еднакви:

public static void main(String[] args) {     String text = readText();     System.out.println(text); }

Резултатът е коректен:

Enter text:  This is our text.  This is our text.

Стъпка 6 – Сглобяване на всички части в едно цяло

След като сме решили всички подзадачи, можем да пристъпим към пълното решаване на проблема. Остава да добавим main(…) метод, в който да съединим отделните парчета:

public static void main(String[] args) {     String text = readText();     String[] words = extractWords(text);     countWords(words); }

Тестване на решението

Макар внимателно да сме тествали решението на всяка подзадача, все още ни предстои тестване на цялостното решение. Трябва да направим това, за да проверим дали отделните части си пасват добре.

Започваме от общия случай, подавайки примерен текст, съдържаш последователност от думи, измежду които такива само с главни и само с малки букви, както и последователност от няколко разделителя един след друг:

public static void main(String[] args) {     String text = "We need several separators " +             "like ! , ? and UPPER CASE words " +             "and lower case words. This is all.";     String[] words = extractWords(text);     countWords(words); }

Изпълняваме програмата и се уверяваме, че резултатът е коректен:

Total words count: 16 Upper case words count: 2 Lower case words count: 12

Изпробваме с още няколко подобни примера и след като сме сигурни, че всичко е наред в този случай, преминаваме към тестването на граничните случаи. Проверяваме какви са резултатите, когато текста съдържа само думи с главни букви или само думи с малки букви. Пробваме да въведем само разделители или само една дума без разделители. Тестваме и случай, когато текстът е празен низ.

Оказва се, че във всички случай, с изключение на този, в който подаваме празен низ, резултатите са коректни. Трябва да намерим от къде идва грешката.

Оказва се, че когато подадем празен низ, резултатния списък, получен след разделянето му на думи, съдържа един елемент, който е празен низ. Когато броим думите, ние го броим като дума с главни букви, защото при преобразуването му към горен регистър и сравнението двата низа съвпадат.

Можем да решим проблема по различни начини. Възможно решение е, при разделянето на думите да връщаме празен списък, ако низът е празен. Друг вариант е директно да извеждаме резултата, без да броим, ако въведеният низ е празен. Трети вариант е да не броим думите, състоящи се от празен низ.

Понеже грешката идва от неправилно броене на празния низ като дума, можем да се спрем на третия вариант и да направим съответните промени в кода за броене на думите. Когато срещнем дума състояща се от празен низ, няма да я броим:

for (String word : words) {     if (word.equals("")) {         continue;     }       totalCount++;     if (isUpperCase(word)) {         allUpperCaseCount++;     } else if (isLowerCase(word)) {         allLowerCaseCount++;     } }

Вече програмата ни работи и в този случай. Повтаряме отново и другите тестове, за да се уверим, че с оправянето на този проблем не сме създали други. Оказва се, че всичко е наред. Можем да направим тест и с по-голям текст от няколко страници, за де се уверим, че нямаме проблем с бързо­действието.

Ето как изглежда кодът на цялостното решение след приложените корекции:

WordsCounter.java

import java.util.Scanner;   public class WordsCounter {       static String extractSeparators(String text) {         StringBuilder separators = new StringBuilder();           int textLength = text.length();         for (int index = 0; index < textLength; index++) {             char character = text.charAt(index);               if (!Character.isLetter(character)) {                 separators.append(character);             }         }           return separators.toString();     }       static String[] extractWords(String text) {         String separators = extractSeparators(text);           if (separators.equals("")) {             String[] words = new String[1];             words[0] = text;             return words;         }           separators = "[\\Q" + separators + "\\E]+";           String[] words = text.split(separators);         return words;     }       static boolean isUpperCase(String word) {         boolean result = word.equals(word.toUpperCase());         return result;     }       static boolean isLowerCase(String word) {         boolean result = word.equals(word.toLowerCase());         return result;     }       static void countWords(String[] words) {         int totalCount = 0;         int allUpperCaseCount = 0;         int allLowerCaseCount = 0;           for (String word : words) {             if (word.equals("")) {                 continue;             }               totalCount++;             if (isUpperCase(word)) {                 allUpperCaseCount++;             } else if (isLowerCase(word)) {                 allLowerCaseCount++;             }         }           System.out.printf("Total words count: %s\n", totalCount);         System.out.printf("Upper case words count: %s\n",                 allUpperCaseCount);         System.out.printf("Lower case words count: %s\n",                 allLowerCaseCount);     }       static String readText() {         Scanner input = new Scanner(System.in);         System.out.println("Enter text:");         String text = input.nextLine();           return text;     }       public static void main(String[] args) {         String text = readText();         String[] words = extractWords(text);         countWords(words);     } }

Дискусия за производителността

Тъй като въпросът за производителността в тази задача не е явно поставен, само ще дадем идея как бихме могли да реагираме, ако евенту­ално се окаже, че нашият алгоритъм е бавен. Понеже разделянето по регулярен израз предполага, че целият текст трябва да бъде прочетен в паметта и думите, получени при разделянето също трябва да се запишат в паметта, то програмата ще консумира голямо количество памет, ако входният текст е голям. Например, ако входът е 200 MB текст, програмата ще изразходва най-малко 800 MB памет, понеже всяка дума се пази 2 пъти по 2 байта за всеки символ.

Ако искаме да избегнем консумацията на голямо количество памет, трябва да не пазим всички думи едновременно в паметта. Можем да измислим друг алгоритъм: сканираме текста символ по символ и натрупваме буквите в някакъв буфер (примерно StringBuilder). Ако срещнем в даден момент разделител, то в буфера би трябвало да стои поредната дума. Можем да я анализираме дали е с малки или главни букви и да зачистим буфера. Това можем да повтаряме до достигане на края на файла. Изглежда по-ефек­тивно, нали?

За по-ефективно проверяване за главни/малки букви можем да направим цикъл по буквите и проверка на всяка буква. Така ще си спестим преоб­разуването в горен/долен регистър, което заделя излишно памет за всяка проверена дума, която след това се освобождава и в крайна сметка това отнема процесорно време.

Очевидно второто решение е по-ефективно. Възниква въпросът трябва ли след като сме написали първото решение да го изхвърлим и да напишем съвсем друго решение. Всичко зависи от изискванията за ефективност. В условието на задачата няма предпоставки да смятаме, че ще ни подадат като вход стотици мегабайти. Следователно решението с регулярните изрази също е коректно и ще ни свърши работа.

Задача 2: Матрица с прости числа

Напишете програма, която прочита от стандартния вход цяло положително число N и отпечатва първите N² прости числа в квадратна матрица с размери N x N. Запълването на матрицата трябва да става по редове от първия към последния и отляво надясно.

Забележка: Едно естествено число наричаме просто, ако няма други делители освен 1 и себе си. Числото 1 не се счита за просто.

Примерен вход:

2                                 3                                   4

Примерен изход:

2 3                             2 3 5                         2 3 5 7 5 7                             7 11 13                           11 13 17 19                                   17 19 23                      23 29 31 37                                                                     41 43 47 53

Намиране на подходяща идея за решение

Можем да решим задачата, като с помощта на два вложени цикъла отпечатаме редовете и колоните на резултатната матрица. За всеки неин елемент ще извличаме и отпечатваме поредното просто число.

Разбиване на задачата на подзадачи

Трябва да решим поне две подзадачи – намиране на поредното просто число и отпечатване на матрицата. Отпечатването на матрицата можем да направим директно, но за намирането на поредното просто число, ще трябва да помислим малко. Може би най-интуитивният начин, който ни идва наум за това е започ­вайки от предходното намерено просто число, да проверяваме всяко следващо дали е просто и в момента, в който това се окаже истина, да го върнем като резултат. Така на хоризонта се появява още една подзадача – проверка дали дадено число е просто.

Проверка на идеята

Нашата идея за решение на задачата директно получава търсения в условието резултат. Разписваме 1-2 примера на хартия и се убеждаваме, че работи.

Да помислим за структурите от данни

В тази задача се ползва една единствена структура от данни – матрицата. Естествено е да ползваме двумерен масив.

Да помислим за ефективността

Понеже изходът е на конзолата, при особено големи матрици (примерно 1000 x 1000) резултатът няма да може да се визуализира добре. Това означава, че задачата трябва да се реши за разумно големи матрици, но не прекалено големи, примерно за N ≤ 200. При нашия алгоритъм при N=200 ще трябва да намерим първите 40 000 прости числа, което не би трябвало да е бавно.

Стъпка 1 – Проверка дали дадено число е просто

За проверката дали дадено число е просто, можем да дефинираме метод isPrime(…). За целта е достатъчно да проверим, че то не се дели без оста­тък на никое от предхождащите го числа. За да сме още по-точни, дос­татъчно е да проверим, че то не се дели на никое от числата между 2 и корен квадратен от числото. Това е така, защото, ако числото p има дели­тел х, то р = х.у и поне едно от числата х и у ще е по-малко или равно на корен квадратен от р. Следва реализация на метода:

static boolean isPrime(int number) {     int maxDivider = (int) Math.sqrt(number);         for (int divider = 2; divider <= maxDivider; divider++) {         if (number % divider == 0) {             return false;         }     }         return true; }

Можем да се уверим, че методът работи коректно, подавайки му после­до­ва­телно различни числа, някои от които прости, и проверявайки върнатия резултат.

Стъпка 2 – Намиране на следващото просто число

За намирането на следващото просто число можем да дефинираме метод, който приема като параметър число, и връща като резултат първото, по-голямо от него, просто число. За проверката дали число е просто, ще използваме методът от предишната стъпка. Следва реализацията на метода:

static int findNextPrime(int startNumber) {     int number = startNumber;     while (!isPrime(number)) {         number++;     }     return number; }

Отново трябва да изпробваме метода подавайки му няколко числа и проверявайки, дали резултатът е правилен.

Стъпка 3 – Отпечатване на матрицата

След като дефинирахме горните методи, вече сме готови да отпечатаме и цялата матрица:

static void printMatrix(int dimension){     int lastPrime = 1;     for (int row = 0; row < dimension; row++) {         for (int col = 0; col < dimension; col++) {             int nextPrime = findNextPrime(lastPrime + 1);             System.out.printf(" %d", nextPrime);             lastPrime = nextPrime;         }         System.out.println();     }       }

Стъпка 4 – Вход от конзолата

Остава да добавим възможност за прочитане на N от конзолата:

static int readN() {     Scanner input = new Scanner(System.in);     System.out.print("N = ");     int n = input.nextInt();     return n; }   public static void main(String[] args) {     int n = readN();     printMatrix(n); }

Тестване на решението

След като всичко е готово, можем да пристъпим към проверка на решението. За целта можем да намерим примерно първите 25 прости числа и да проверим изхода на програмата за стойности на N от 1 до 5. Не трябва да пропускаме случая за N=1, понеже това е граничен случай и вероятността за допусната грешка при него е значително по-голяма.

В конкретния случай, при условие че сме тествали добре методите на всяка стъпка, можем да се задоволим и с примерите от условието на задачата. Ето как изглежда изходът от програмата за стойности на N съответно 1, 2, 3 и 4:

2               2 3                     2 3 5                         2 3 5 7                 5 7                     7 11 13                          11 13 17 19                                           17 19 23                      23 29 31 37                                                                             41 43 47 53

Можем да се уверим, че решението на задачата работи сравнително бързо и за по-големи стойности на N. Примерно при N=200 не се усеща някакво забавяне.

Следва пълната реализация на решението:

PrimesMatrix.java

import java.util.Scanner;   public class PrimesMatrix {       static boolean isPrime(int number) {         int maxDivider = (int) Math.sqrt(number);           for (int divider = 2; divider <= maxDivider; divider++) {             if (number % divider == 0) {                 return false;             }         }         return true;     }       static int findNextPrime(int startNumber) {         int number = startNumber;         while (!isPrime(number)) {             number++;         }         return number;     }       static void printMatrix(int dimension) {         int lastPrime = 1;         for (int row = 0; row < dimension; row++) {             for (int col = 0; col < dimension; col++) {                 int nextPrime = findNextPrime(lastPrime + 1);                 System.out.printf(" %d", nextPrime);                 lastPrime = nextPrime;             }             System.out.println();         }     }       static int readN() {         Scanner input = new Scanner(System.in);         System.out.print("N = ");         int n = input.nextInt();         return n;     }       public static void main(String[] args) {         int n = readN();         printMatrix(n);     } }

Дискусия за производителността

Трябва да отбележим, че посоченото решение не търси простите числа по най-ефективния начин. Въпреки това, с оглед яснотата на изложението и поради очаквания малък размер на матрицата, можем да използваме този алгоритъм, без да имаме проблеми с производителността.

Ако трябва да подобрим производителността, можем да намерим първите N² числа с "решето на Ератостен" (sieve of Eratosthenes) без да проверя­ваме дали всяко число е просто до намиране на N² прости числа.

Задача 3: Аритметичен израз

Напишете програма, която изчислява стойността на прост аритметичен из­раз, съставен от цели числа без знак и аритметичните операции "+" и "-". Между числата няма интервали.

Изразът се задава във формат:

<число><операция>...<число>

Примерен вход:

1+2-7+2-1+28+2+3-37+22

Примерен изход:

15

Намиране на подходяща идея за решение

За решаване на задачата можем да използваме факта, че формата на израза е стриктен и ни гарантира, че имаме последователност от число, операция, отново число и т.н.

Така можем да извлечем всички числа участващи в израза, след това всички оператори и накрая да изчислим стойността на израза, ком­би­ни­рай­ки числата с операторите.

Проверка на идеята

Наистина, ако вземем лист и химикал и изпробваме подхода с няколко израза, получаваме верен резултат. Първоначално резултатът е равен на първото число, а на всяка следващата стъпка добавяме или изваждаме следващото число в зависимост от текущия оператор.

Структури от данни и ефективност

Задачата е прекалено проста, за да ползваме сложни структури от данни. Числата и значите можем да запишем в масив или ArrayList. За проблеми с ефективността не можем да говорим, тъй като всеки знак и всяко число се обработват точно по веднъж, т.е. имаме линейна сложност на алгори­тъма.

Разбиване на задачата на подзадачи

След като сме се убедили, че идеята работи можем да пристъпим към разбиването на задачата на подзадачи. Първата подзадача, която ще трябва да решим е извличането на числата от израза. Втората ще е извличането на операторите. Накрая ще трябва да изчислим стойността на целия израз, използвайки числата и операторите, които сме намерили.

Стъпка 1 – Извличане на числата

За извличане на числата е необходимо да разделим израза, като за разделители използваме операторите. Това можем да направим лесно чрез метода split(…) на класа String. След това ще трябва да преобра­зу­ваме получения масив от символни низове в масив от цели числа:

static int[] extractNumbers(String expression) {     String[] splitResult = expression.split("[+-]");       int numbersCount = splitResult.length;     int[] numbers = new int[numbersCount];       int currentNumber;     for (int index = 0; index < numbersCount; index++) {         currentNumber = Integer.parseInt(splitResult[index]);         numbers[index] = currentNumber;     }       return numbers; }

За преобразуването на символните низове в цели числа използваме метода parseInt(…) на класа Integer. Той приема като параметър сим­во­лен низ и връща като резултат целочислената стойност, представена от него.

Защо използваме масив за съхранение на числата? Не можем ли да използваме свързан списък или ArrayList? Разбира се, че можем, но в случая е нужно единствено да съхрани числата и след това да ги обходим при изчисляването на резултата. Ето защо масивът ни е напълно доста­тъчен.

Преди да преминем към следващата стъпка проверяваме дали извли­ча­не­то на числата работи коректно:

public static void main(String[] args) {     String expression = "1+2-7+2-1+28";     int[] numbers = extractNumbers(expression);     for (int number : numbers) {         System.out.printf("%s ", number);     } }

Резултатът е точно такъв, какъвто трябва:

1 2 7 2 1 28

Проверяваме и граничния случай, когато изразът се състои само от едно число без оператори и се уверяваме, че и той се обработва добре.

Стъпка 2 – Извличане на операторите

Извличането на операторите може да направим аналогично на извлича­нето на числата, но като вземем предвид, че разделител може да е последователност от няколко цифри:

static String[] extractOperators(String expression) {     String[] operators = expression.split("[0123456789]+");     return operators; }

Следва проверка, дали методът работи коректно:

public static void main(String[] args) {     String expression = "1+2-7+2-1+28";     String[] operators = extractOperators(expression);     for (String operator : operators) {         System.out.printf("'%s' ", operator);     } }

Забелязваме, че в резултата получаваме един празен низ, който е излишен:

'' '+' '-' '+' '-' '+'

Това е така, понеже на първа позиция винаги стои цифра и разделяйки низа спрямо последователност от цифри, получаваме празния низ в нача­лото. Можем да решим лесно проблема, като премахнем първия елемент от списъка, преди да върнем резултата:

static String[] extractOperators(String expression) {     String[] operators = expression.split("[0123456789]+");       int operatorsCount = operators.length;     if (operatorsCount > 0) {         operators = Arrays.copyOfRange(operators,1,operatorsCount);     }     return operators; }

Проверяваме отново резултата и този път е коректен. Правим проверка и за граничния случай, когато изразът не съдържа оператори, а се състои само от едно число. В този случай получаваме празен низ, което е очаква­но­то поведение.

Стъпка 3 – Изчисляване на стойността на израза

За изчисляване на стойността на израза, можем да използваме факта, че числата винаги са с едно повече от операторите и с помощта на един цикъл да изчислим стойността на израза, при условие че са ни дадени списъците с числата и операторите:

static int calculateExpression(int[] numbers,String[] operators) {     int result = numbers[0];       for (int i = 1; i < numbers.length; i++) {         String nextOperator = operators[i - 1];         int nextNumber = numbers[i];           if (nextOperator.equals("+")) {             result += nextNumber;         } else if (nextOperator.equals("-")) {             result -= nextNumber;         }     }     return result; }

Проверяваме работата на метода:

public static void main(String[] args) {     // Expression: 1 + 2 - 3 + 4     int[] numbers = { 1, 2, 3, 4 };     String[] operators = { "+", "-", "+" };       // Expected result: 4     int result = calculateExpression(numbers, operators);     System.out.printf("Result is: %s", result); }

Резултатът е коректен:

Result is: 4

Стъпка 4 – Вход от конзолата

Ще трябва да дадем възможност на потребителя да въвежда израз:

static String readExpression() {     Scanner input = new Scanner(System.in);     System.out.print("Enter expression: ");     String expression = input.nextLine();       return expression; }

Стъпка 5 – Сглобяване на всички части в едно цяло

Остава ни само да накараме всичко да работи заедно:

public static void main(String[] args) {     String expression = readExpression();       int[] numbers = extractNumbers(expression);     String[] operators = extractOperators(expression);       int result = calculateExpression(numbers, operators);     System.out.printf("%s = %d \n", expression, result); }

Тестване на решението

Можем да използваме примера от условието на задачата, при тестването на решението. Получаваме коректен резултат:

Enter expression: 1+2-7+2-1+28+2+3-37+22 1+2-7+2-1+28+2+3-37+22 = 15

Трябва да направим още няколко теста с различни примери, включително и случаят, когато изразът се състои само от едно число, за да се уверим, че решението ни работи.

Можем да тестваме и празен низ. Не е много ясно това дали е коректен вход, но може да го предвидим за всеки случай. Освен това не е ясно какво става, ако някой въведе интервали в израза, примерно вместо "2+3" въведе "2 + 3". Хубаво е да предвидим тези ситуации.

Друго, което забравихме да тестваме, е какво става при число, която не се събира в типа int. Какво ще стане, ако ни бъде подаден изразът "11111111111111111111111111111+222222222222222222222222222222"?

Дребни поправки и повторно тестване

Във всички случаи, когато изразът е невалиден, ще се получи някакво изключение (най-вероятно NumberFormatException). Достатъчно е да при­хванем изключенията и при настъпване на изключение да съобщим, че е въведен грешен израз. Следва пълната реализация на реше­нието след тази корекция:

SimpleExpressionEvaluator.java

import java.util.Arrays; import java.util.Scanner;   public class SimpleExpressionEvaluator {       public static void main(String[] args) {         String expression = readExpression();         try {             int[] numbers = extractNumbers(expression);             String[] operators = extractOperators(expression);                 int result = calculateExpression(numbers, operators);             System.out.printf("%s = %d \n", expression, result);         } catch (Exception ex) {             System.out.println("Invalid expression!");         }     }         private static int[] extractNumbers(String expression) {         String[] splitResult = expression.split("[+-]");           int numbersCount = splitResult.length;         int[] numbers = new int[numbersCount];           int currentNumber;         for (int index = 0; index < numbersCount; index++) {             currentNumber = Integer.parseInt(splitResult[index]);             numbers[index] = currentNumber;         }           return numbers;     }         private static String[] extractOperators(String expression) {         String[] operators = expression.split("[0123456789]+");           int operatorsCount = operators.length;         if (operatorsCount > 0) {             operators=Arrays.copyOfRange(operators,1,operatorsCount);         }         return operators;     }       private static int calculateExpression(int[] numbers,             String[] operators) {         int result = numbers[0];           for (int i = 1; i < numbers.length; i++) {             String nextOperator = operators[i - 1];             int nextNumber = numbers[i];               if (nextOperator.equals("+")) {                 result += nextNumber;             } else if (nextOperator.equals("-")) {                 result -= nextNumber;             }         }         return result;     }       private static String readExpression() {         Scanner input = new Scanner(System.in);         System.out.print("Enter expression: ");         String expression = input.nextLine();           return expression;     } }

Упражнения

1.    Решете задачата "броене на думи в текст", без да ползвате регулярни изрази, само с един буфер (StringBuilder).

2.    Реализирайте по-ефективно решение на задачата "матрица с прости числа" като търсите простите числа с "решето на Ератостен": http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

3.    Добавете поддръжка на операциите умножение и целочислено деление в задачата "аритметичен израз". Имайте предвид, че те са с по-висок приоритет от събирането и изваждането!

4.    Добавете поддръжка на реални числа, не само цели.

5.    Направете възможни пресмята­нията с числа, които не се събират в стандартните типове float и double, примерно числа със 100 цифри преди и 200 цифри след десетичната запетая.

6.    Добавете поддръжка на скоби в задачата "аритметичен израз".

7.    Напишете програма, която валидира аритметичен израз. Например "2*(2.25+5.25)-17/3" е валиден израз, докато "*232*-25+(33+а" е невалиден.

Решения и упътвания

1.    Можете да четете входния файл символ по символ. Ако поредният сим­вол е буква, го добавяте към буфера, а ако е разделител, анализирате буфера (той съдържа поредната дума) и след това зачиствате буфера. Когато свърши входния файл, трябва да анализирате последната дума, която е в буфера (ако файлът не завършва с разделител). Изглежда лесно и просто.

2.    Помислете първо колко прости числа ви трябват. След това помислете до каква стойност трябва да пускате решето на Ератостен, за да ви стигнат простите числа за запълване на матрицата. Можете опитно да измислите някаква формула.

3.    Достатъчно е да изпълните първо всички умножения и деления, а след тях всички събирания. Помислихте ли за деление на нула?

4.    Работата с реални числа можете да осигурите като разре­шите използ­ването на символа "." и заместите int с double.

5.    Разгледайте как работи класа BigDecimal и нанесете необходимите корекции, за да използвате този клас вместо типа double за съхране­ние на числата и междинните резултати при пресмятането на израза.

6.    Можете да направите така: намирате първата затваряща скоба и търсите наляво съответната й отваряща скоба. Това, което е в скобите е аритметичен израз без скоби, за който вече имаме алгоритъм за изчисление на стойността му. Можем да го заместим със стойността му. Повтаряме това за следващите скоби докато скобите свършат. Накрая ще имаме израз без скоби.

Например, ако имаме "2*((3+5)*(4-7*2))", ще заместим "(3+5)" с 8, след това "(4-7*2)" с -10. Накрая ще заместим (8*-10) с -80 и ще сметнем 2*-80, за да получим резултата -160. Трябва да предвидим аритметични операции с отрицателни числа, т.е. да позволяваме числата да имат знак.

Другият алгоритъм много по-лесен. Използва се стек и преобразуване на израза до "обратен полски запис". Можете да потърсите в Интернет за фразата "postfix notation" и за "shunting yard" algorithm.

7.    Ако изчислявате израза с обратен полски запис, можете да допълните алгоритъма, така че да проверява за валидност на израза. Добавете следните правила: когато очаквате число, а се появи нещо друго, изразът е невалиден. Когато очаквате аритметична операция, а се появи нещо друго, изразът е невалиден. Когато скобите не си съответ­стват, ще препълните стека или ще останете накрая с недоизпразнен стек. Помислете за специални случаи, примерно "-1", "-(2+4)" и др.

 

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.