[C#] Домашно Strings and Text Processing - 3 задача


6

Условие: Write a program to check if in a given expression the brackets are put correctly.

Example of correct expression: ((a+b)/5-d).
Example of incorrect expression: )(a+b)).

Решениеsource.

Обяснение: Четем стринга символ по символ. Имаме променлива, която ни следи колко скоби сме отворили досега. Ако на дадена стъпка сме затворили скоба, която не е отваряна, резултатът е грешен. Ако сме стигнали до края и променливата е 0, следователно всички са затворени.

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

Edit: Проверете решенията си за израза ")a + b("!




Отговори



6

Решение:

http://pastebin.com/2zkPQSXa.

Обяснение:

1. Преобразувам string-a в char масив

2. Създавам си 1 променлива, ако скобата е отваряща добавам 1 , аналогично ако е затваряща -1. Тънкият момент е, че ако имаме израз започващ с затваряща скоба веднага го приемаме за невалидно и break;, също така ако брояча накрая НЕ е равен на НУЛА пак е невалидно

3. Накрая проверявам дали броят на отворените скоби е равен на броя на затворените скоби, един вид ако брояча накрая НЕ е равен на НУЛА пак е невалидно.

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

ЕДИТ: Оправено е, а цитатът на Наков не е много валиден вече, но ще го оставя :)


от Assi.NET (3050 точки)


0
Здравей, само една забележка, че губиш наредбата. Примерно за ")(2+3)/2(", трябва да даде грешен резултат. Оправих условието, благодаря.

от jasssonpet (6814 точки)

0
моето решение е същото, но добавих и проверка ако затварящата скоба е непосредствено след или отварящата непосредствено преди някакъв знак. jasssonpet, има 2 проверки за отрицателни стойности, едната от тях е вътре в цикъла - тя прекъсва цикъла веднака щом се появи отрицатената стойност (при първи случай когато затварящите скоби са повече от отварящи)

от mvgmvg (296 точки)



1

Днес след лекцията, седнахме с един колега да решим тази задача. Получи се много интересно решение. 

Решение

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

Поздрави,


от nikola76 (1250 точки)


4
Ето едно решение с лист, преобразувам стринга в чар масив и го обхождам, записвам отварящата скоба в лист и я изтривам когато дойде затваряща, ако дойде затваряща скоба и листа е празен е грешно и ако накрая листа не е празен пак е грешно.
Код: http://pastebin.com/Nxm1HA0s



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

от Nevencheto (587 точки)


0

http://pastebin.com/8GJMiEUU

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


от Mitko_Mitev (1276 точки)


0
Така програмата ти няма да работи коректно за израз като "(a+b))(" примерно,защото броиш само срещанията.Аз съм решила проблема като проверявам освен броя срещания с IndexOf дали първата скоба, която се среща е отваряща и с LastIndexOf дали последната ,която се среща е затваряща.Това е един вариант:)


0
+1 mariaendarova :)



0

Броят се отварящите и затварящите скоби и трябва броят им да е равен.

решение




0
Здравей, само една забележка, че губиш наредбата. Примерно за ")(2+3)/2(", трябва да даде грешен резултат.

от jasssonpet (6814 точки)

0
Знаех си, че е прекалено лесно, за да работи перфектно :) Мерси за забележката.



1

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

http://pastebin.com/gAysuDwQ


от sylviapsh (302 точки)


1
Аз го направих с една булева променлива:
http://pastebin.com/cTMVMzGe

от iwitass (3695 точки)


0
Ей батко ти колко хитро си го направил не истина. Точно си викам тая програма нема как да разтака вярно и се усетих. Браво, ак сложиш и едно брейкче да не върти докрай като стане false ще е страшно :D

от Al.polichronov (1567 точки)

0
Трябва още малко да се пипне решението, за да е вярно. След цикъла сложи една проверка, ако броячът е != 0 да дава пак false. Иначе при вход "( ( dasd ) ( ( dasd )" пак дава True. ;)

от DIMITAR_GOSHEV (0 точки)


5

Решение:

Цък

Обяснение:

Какво е стек ?

Основната ми логика тук се базира на структурата - Stack. Ако си нямате и представа що е това стек ви препоръчвам да хвърлите едно око тук. На кратко - стека е LIFO ( Last In First Out ) структура т.е. когато използваме .Push слагаме най-отгоре, а когато използваме .Pop взимаме най-отговре. Или графично изглежда горе-долу така:

Stack

Червения елемент е пръв в структурата и пръв излиза от нея.

Относно задачата:

1. За реализиацията на задачата ни трябва 2 променливи:

input - в който пазим входа си.

areCorrect - тук следим дали скобите са поставени грешно.

2. С for цикъл обикаляме стринга си от лявно на дясно и ако попаднем на "(" я .Push() - ваме в стека.

3. Ако попаднем на ")" съответно проверяваме дали дължината на стека е равна на 0, ако то значи че тази скоба е поставена грешно от което следва че скобите са поставени неправилно. Присвояваме false на areCorrect и break-ваме цикъла. В противен случай просто .Pop() ваме стека.

4. След като свърши цикъла правим една последна проверка - дали дължината на стека е 0, ако не е то следователно има незатворени скоби -> присвояваме false на areCorrect

5. Принтираме резулата на кознолата.


от Teodor92 (13062 точки)


0
Здравей, малка грешка от разсеяност - LIFO е "last in first out". Всичко останало е вярно и много добре обяснено.

от ellapt (6303 точки)

0
Вярно, обърнал съм наредбата :D Мерси за забележката :)

от Teodor92 (13062 точки)



1
Едно решение и от мен с изчерпване на стринга: http://pastebin.com/6LhU09qC
1.Чета стринга и първо проверявам дали броя на отварящите и затварящите скоби е равен. Ако да завъртам цикъл, толкова пъти колкото е бройката на двойките отв. и затв. скоби.
2.Всеки път търся най-вътрешната двойка, по отвяраща скоба и проверявам дали от нейният индекс напред има затваряща такава. Ако да премахвам цялата двойка от стринга. Ако не значи стринга е невалиден..

от petromaxa (577 точки)


0
Същата логика, само, че с рекурсия и StringBuilder:
http://pastebin.com/mek0b9Au

от neofitov (235 точки)


0
И още едно решение... :) http://pastebin.com/wyB3chwX