[C#] Using Classes and Objects - 7 задача


20

Здравейте, колеги!

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

Условието:

7.* Write a program that calculates the value of given arithmetical expression. The expression can contain the following elements only:
 
- Real numbers, e.g. 5, 18.33, 3.14159, 12.6
- Arithmetic operators: +, -, *, / (standard priorities)
- Mathematical functions: ln(x), sqrt(x), pow(x,y)
- Brackets (for changing the default priorities)

  Examples:

  (3+5.3) * 2.7 - ln(22) / pow(2.2, -1.7) -> ~ 10.6

  pow(2, 3.14) * (3 - (3 * sqrt(2) - 3.2) + 1.5*0.3) -> ~ 21.22

Hint: Use the classical "shunting yard" algorithm and "reverse Polish notation".


След щателно четене за тези алгоритми, осъзнах че нямам никаква идея що е стек, що е опашка и за чий ч*п се ползват, но пък плюса от цялата ситуация е, че вече ги разбрах. Не претендирам, че решението е перфектно, но пък като че ли работи добре и решава вярно. Може да има някой бъг тук-там, но се постарах да пробвам почти всичко възможно. Ако някой намери нещо, да казва и ще го оправя.

ЗАБЕЛЕЖКА: Тъй като не можах да разгранича отрицателните числа от знака за изваждане, те се въвеждат с тилда, а не с тире. Пример:

~5.6 == -5.6

~.6 == -0.6

~3 == -3

Също така се постарах програмата при грешки да извежда съобщения по културния начин, а не да хвърля exception-и, но може да съм изпуснал някоя. Отделно исках да приема всякакъв вход с каквито и да е интервали между елементите, стига математически да е коректно и възможно. Пример:

5 +     (60/     79    )-4.9    * 10 + pow (    3.14, ~2) => Валиден вход!

Сорс код тук (493 реда): CLICK!!!

Какво може да се добави: да се оптимизира малко тук и там, да се добавят още функции като синус, косинус и т.н., да се сложат Pi = 3.141592 и e = 2,718281 като константи.

Обяснения:

1. Дефинирам два масива от стрингове, единия съдържа цифрите, ".", "~", другия аритметичните операции.

2. Дефинирам методи:

  • първия проверява дали дадед стринг е число
  • втория дали даден стринг е аритметична операция
  • третия определя последователността на операциите (умножение е преди събиране)
  • четвъртия конвертира в децимал (превръща ~ в -)
  • петия добавя скоби около фунциите, за да се изпълнят в правилна последователност

3. Създавам стек и опашка и приемам входа, след което около всеки отделен елемент слагам празен интервал, за да може в последствие входа да бъде разцепен на стрингове от елементи. Пример:

(3+4) => ( 3 + 4 )

На получения резултат извиквам метода да добави скоби около функциите.

4. Разделям на масив от стрингове с Split(' '), като отделям всяко число, функция или оператор в отделен елемент (token).

5. Следва този алгоритъм, който превръща входа от нормален към Reverse Polish Notation:

While there are tokens to be read:

  • Read a token.
  • If the token is a number, then add it to the output queue.
  • If the token is a function token, then push it onto the stack.
  • If the token is a function argument separator (e.g., a comma):
  • Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
  • If the token is an operator, o1, then:
  • while there is an operator token, o2, at the top of the stack, and either o1 is left-associative and its precedence is less than or equal to that of o2, or o1 has precedence less than that of o2,pop o2 off the stack, onto the output queue;
 
  • push o1 onto the stack.
  • If the token is a left parenthesis, then push it onto the stack.
  • If the token is a right parenthesis:
  • Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
  • Pop the left parenthesis from the stack, but not onto the output queue.
  • If the token at the top of the stack is a function token, pop it onto the output queue.
  • If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
  • When there are no more tokens to read:
  • While there are still operator tokens in the stack:
  • If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
  • Pop the operator onto the output queue.
  • Exit.

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

7. Печата изхода като единствения останал елемент от стека.

Надявам ви е било интересно и полезно!




Отговори



4

Здравейте,

Това решение, което съм дал тук е старо. 

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

Теория

Практика

Видеата ги има и в курса C# Част 2.

Поздрави,

Ивайло


от ivaylo.kenov (30760 точки)


4

Ето двойно по-кратко решение: http://pastebin.com/z776wiyz  като съм го направил така, че фунцкиите от израза да могат да приемат като параметри, други изрази и т.н. Идеята е следната:
Правим си функция CalculateExpression, която приема като стойност израз и връща стойност double - стойността на израза. Зада си улесним сметките, алгоритъмът премахва всички празни места във израза и го огражда със скоби, за да не е нужно да разглеждаме частни случаи .

Например изразът:

sqrt(432.43 *     ln(pow(32.3,5 * 32)   )   - pow(pow(1, 5), pow ( pow (31,4 .3213  ) , sqrt (43.23334) )             )        

ще бъде превърнат в: 

(sqrt(432.43*ln(pow(32.3,5*32))-pow(pow(1, 5),pow(pow(31, 4.3213),sqrt(43.23334))))

Правим си функция, която по даден израз, връща Reverse Polish Notation на този израз. Зада улесним смятането имаме и функции, които по даден индекс на начало на функция, пресмятат стойността на функцията, като те самите използват отделна функция за определянето на параметрите си. Пресмятането на стойността на функциите става отново чрез CalculateExpression и по този начин се получава много елегантна рекурсия. Функциите, които търсят параметри на функции в израза, връщат 2 стойности- 1 вата е резултата от пресмятането на функцията, 2 рата е индекса във израза, където е края на функцията. Реализяцията няма да бъде ясна на хора, който не разбират добре рекурсия, и нямат познания по структури от данни като List,  Stack  но все пак могат да го прегледат и сами да преценят дали им хрумват някакви идеи за тяхно си решение. Който има подробни въпроси да ме пита. :)


от zlatkov (580 точки)


6

Решение: source (80 SLOC по моя стил или реално към 180 някъде).

Разделил съм задачата на три части в три отделни метода.

Например за "1 + 2 * 3":

  • Разделям стринга на части: "1", "+", "2", "*", "3"
  • Обръщам израза в постфиксна форма: "1", "2", "3", "*", "+"
  • Пресмятам стойността на израза: 7

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

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


от jasssonpet (6814 точки)


0
Твоят код от source ми дава:
Unhandled Exception: System.FormatException: Input string was not in a correct f ormat. at System.Number.ParseDouble(String value, NumberStyles options, NumberFormat Info numfmt) at System.Double.Parse(String s) at Program.Evaluate(List`1 postfix) in c:\Users\Kiril\Documents\Visual Studio 2012\Projects\II - 06 - Използване на класове и обекти\07.AritgmeticalExpressio n\Program.cs:line 104 at Program.Main() in c:\Users\Kiril\Documents\Visual Studio 2012\Projects\II - 06 - Използване на класове и обекти\07.AritgmeticalExpression\Program.cs:line 111 Press any key to continue . . .

от webmatrix (825 точки)

0
Смени си точките със запетайки.

от jasssonpet (6814 точки)



5

Ето го и моето решение.

Edit: ver.2 release

Алгоритъма ми е следния:

имам 7 метода:

Извличане на число по дадена позиция (наляво или надясно);

Изчисляване на прост израз (а+б, а+в и т.н.);

Замяна на израза с резултата му;

Изчисляване на функция (корен квадратен, логаритъм  и на степен);

Търсене на най-вътрешните скоби;

Изчисляване на израз в скоби;

Търсене на изчислителен знак;

 

Такааа работата е следната: Взимаме стринга от конзолата, махаме празните полета (нужно е израза да е правилно написан математически - броя отворени скоби да е равен на броя затворени). Прибавям от едната страна (( и от другата )) - поради естеството на алгоритъма ;)

След това:

Докато не останат само един чифт скоби изпълняваме:

1 търсим най-вътрешните скоби

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

3 ако 2 го пропуснем - извикваме изчисляване на израз в скоби като той от своя страна извиква колкото пъти е нужно изчисляване на прост израз (като спазва реда на знаците *, /, +, -) след което върнатия резултат го презаписваме на мястото на израза който смятахме.

изпълняваме 1.

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

 

Доста я мъчих да я накарам да сгреши (почти съм сигурен че не перфектна) но не успях. Ще се радвам на всякакви тестове, препоръки и забележки от ваша страна. Благодаря за вниманието!


от stoyanov (2483 точки)


1

0
Мисля и аз да се разпиша във форума с едно оригинално решение на проблема от тип мързел. Тъй като съм работил с матлаб и знам, че там това нещо го има по-подразбиране предположих, че вече е направено и за С#. Оказа се че вече има поне няколко решения и едно от тях се казва се Ncalc:
http://ncalc.codeplex.com/downloads/get/283228
Разбира се това е за хора, които не им се занимава да четат подробно за
"shunting yard" algorithm and "reverse Polish notation".
Единствения проблем е че ще трябва да обработим стринга при наличие на степен, логаритъм или корен тъй като в Ncalc имаме:
Pow(x,y) с главна буква P,
Sqrt(x) с главна буква S и
Log(x,y) с главна буква L и два аргумента ("y" в случая ще е неперовото число)
p.s. y = Exp(1) поздрави Красимир

от machine (0 точки)


1
Някой може ли да каже точно какъв материал(различни методи, фунции,структури) трябва да прочетем за да ни стане горе - долу ясна задачата, естествено освен тези двама алгоритъма, които са спеменати, че така като разглеждам някои от решенията има доста неща, които не съм срещал.. а не може така, трябва да се направи нещо по въпроса.
Мерси! :)

от boncho.vylkov (1923 точки)


0
Когато срещаш нещо непознато, а това е съвсем нормално да се случва постоянно :-), потърси го в Google. Там винаги има мнооооого информация. Специално за тази задача, освен двата споменати алгоритъма, ще трябва да се прочетат и някои нови структури от данни като стек и опашка (самите алгоритми те водят към тях). Специално за моето предложено решение ще се наложи да хвърлиш поглед и на регулярните изрази, които са си малко гаднички, поне за мен.



4

http://pastebin.com/BSg53Mah
Остана ми време да разпиша малко:

- Използвам shunting yard.

- още в началаото премахвам всички празни интервали

- когато имам число започващо с - например(-5*4) го правя на (0-5) за да различа unary sign

- за пресмятането на фунцкиите не изпозлвам shunting yard, оставих го за по-нататък да го разгледам, а създадох мои методи

- разглеждам случаи в  които във функциите може да има нужда от аритметични действия, например:
pow(2, (3.14-10)*4*(-1))
Това го постигнах с рекурсия като извиквам отново ShuntingYard за параметрите.

- минус на тоя етап, че че не проверявам числото дали е отрицателно например за Sqrt(); и не правя всички проверки.

 

p.S. Задължително мисля да мина през решението на jasssonpet и на dess.yordanova Който има време и е начинаещ като мен може да научи доста от тях!


от vlad0 (6103 точки)


3

 

Здравейте,
 
Започнах да програмирам на скиптови езици и още не мога да се освободя от тази концепция. Видях условието (3+5.3) * 2.7 - ln(22) / pow(2.2, -1.7) и си викам "Ама то си готов код просто го пускам и тръгва". Но на десетия ред код ми светна, че имаме един процес наречен компилиране,  и реално не може да "execute"-нем този код. И тогава дойде въпроса. Може ли да компилираме по време на изпълнение на самата програма. Потърсих малко в интернет и се натъкнах на това . След малко играчка с това направих ето този калкулатор: LINK
Реално пускам програмата, въвеждам стринга с математическия израз, поставям Math. пред имената на функцията, компилирам целия ред и готово. 
Осъзнавам, че идеята на тази задача изобщо не е била това и че този вариант е доста глупав, но научих доста интересни неща докато го правих.
 
Надявам се да съм бил полезен на някой. smiley

 


от Ivaylo (696 точки)


0
Само на мен ли ми дава на 6 местта твоя код ?:
Error 1 Using the generic type 'System.Collections.Generic.Stack

от webmatrix (825 точки)


0
При мен проблема е, че не мога да разделя стринга на float числа и оператори

от bgatev (1491 точки)


0
Предполагам говориш за минуса. Можеш да проверяваш дали преди и след минуса има цифра (първи валиден знак, без ' ') - тогава е изваждане(операция), ако има само отзад число значи е минус. Иначе и аз не съм го разгледал този случай, по-важното според мен е принципа на решение. Edit: Допълнение ако имаш нещо от типа (3 - (3 * (-3)). При проверката дали е операция разглеждаш отварящата скоба като символ при който е число, а затваряща скоба като символ за операция.

от stanev.plamen (1143 точки)