[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 точки)


2

Решението на задачата е по алгоритъма Shunting Yard, както е обяснено тук:

За начало дефинирам един речник от операторите и един хеш с цифри за да проверявам по-бързо и кратко дали имаме число или оператор.

В решението си съм ползвал стек и опашка, като може принципно да се направи и с лист, но е малко по-неудобно и ще работи по – бавно.

Основните стъпки според алгоритъма са следните:

Четем стринга символ по символ:

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

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

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

Накрая последното останало число в опашката е резултата.

Особеното в задачата е че функциите ln, pow и sqrt връщат число. Така че ако срещнем такава функция можем влизаме рекурсивно в основната функция за решение за да получим накрая число – Така би трябвало да работи за вложени изрази. Аз съм го направил по-просто че задачата малко ми омръзна : ), като директно извличам числото, но не трябва да се влагат изрази във функциите.

Решение: Github


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


4

Здравейте,

за решаването на задачата използвам алгоритъма "Shunting Yard" и "Reverse polish notation" и само по един Stack за всеки от тях.

Задачата работи за:

- цели числа

- реални числа

- положителни числа

- отрицателни числа (2 + -3) = (2+-3) = -1

Включени оператори и функции (общо 10):

-> +, -, *, /

-> pow(x,y) или x^y (по избор), sqrt(x), ln(x), sin(x), cos(x), tan(x)

където x и y могат да бъдат цели/реални положителни/отрицателни числа.

ВИЖ RPN КОД-А (Reversed Polish Notation) - прибл. 215 реда без коментари

---------------------------------------------

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

ВИЖ UNIT TEST КОД-А (Unit tests)

---------------------------------------------

Други особености на програмата:

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

- Изразите: (9 - 3 * 4) == (9 - 3*4) == (9 + -3 * 4) == (9- 3*4) са еквивалентни и коректни.

Тъй като прави разлика между положителни и отрицателни числа, изразът:

(9-3*4) е еквивалентен на (9 -3*4) и програмата не знае дали - (минус) е изваждане или показател за отрицателно число. За това извежда некоректен израз.

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


от martin.nikolov (4535 точки)


1

Ето и едно друго решение тук. Използвал съм регулярни изрази за решението на задачата.

Трите стъпки, които се изпълняват са:

1. Израза се проверява за функции. Ако има, техните стойности се изчисляват и заместват в израза.

2. Израза се проверява за изрази оградени със скоби. Ако имар техните стойности се изчисляват и заместват в израза.

3. Изчисляват се останалите операции(+,-,*,/).

Има и някоя друга проверка за некоректност на израза.

Edited: Открих проблем при влагане на изрази в функциите, но вече е отстранен.


от stanchev (197 точки)


2

Задачката наистина беше интересна. Реших я без да гледам shunting yard алгоритъма, но в последствие се оказа че общо взето съм следвал подобни стъпки, всъщност ето ги и тях:

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

2. За функцията pow(x,y) ползвам четвърти метод заради използването на запетая. Същия ползва метода от т.1 за откриване на числа, който в случая прочита x и y.

3. Останалите функции sqrt(x) и ln(x) ги изчислявам в пети метод, чрез проверка за определен символ от името на функцията.

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

Чисто кодът излезе около 170 реда, но съм добавил някои визуални допълнения, както и да може да пресмята sin(x), cos(x), tan(x) и cot(x). Опитах се да я счупя с някой "изкривен" израз но за момента ми пресмята всичко.


от Flystar (1171 точки)


0
Някой дали може да ме светне защо на втория израз от примерните се получава такъв резултат:
pow(2, 3.14) * (3 - (3 * sqrt(2) - 3.2) + 1.5*0.3) = ~ 21.22
Аз го смятам така:
8,815 * (3 - (4,242 - 3,2) + 0,45)
8,815 * (3 - 1,042 + 0,45)
8,815 * (3 - 1,492)
8, 815 * 1,508 = 13,287

от lostm1nd (846 точки)


0
3 - 1.042 + 0.45 = 3.45 - 1.042 а не на 3 - 1,492

от wnvko (3123 точки)

0
1042 е с минус отпред, а 0,45 с плюс, резултата си е съвсем верен в примера. И на мен ми се получи като се опитах да я реша, но защото си мислех, че може и да не правя метод за приоритетите на операторите, ами сметката може да стане и ръчно на един ред, което се оказа накрая доста трудно за осъзнаване къде всъщност е грешката. Така че ако си я написал вече или си тръгнал по този трънлив път, гледай внимателно. ;)

от andrei_pl (247 точки)



0

Здравейте!

Започнах да решавам задачата по инструкциите на това видео https://www.youtube.com/watch?v=QzVVjboyb0s (Polish Reverse Notation), но се закучи работата още когато дописах допълнителни операции след скобите от примера 9 + 24 / (7 - 3).

Това е моето първоначално решение само за +. -, *, /. - http://pastebin.com/GZKxn6nr .

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

Благодаря предварително!

 


от p.penchev (204 точки)


0
Честно казано не ти разбирам въпроса, но щом говориш за скоби и едновременно с това за смятане на числа бъркаш някъде. Тази задача се решава на два етапа: 1. Етап - от нормален израз получаваш израз в Обратен Полски запис - до тук нямаш изчисления. От математическа гледна точка изразът по-горе: 9 + 24 / (7 - 3)
и израза 9, 24, 7, 3, -, /, +
са абсолютно еднакви. Целта на първия етап, shunting yard algorithm, е само да получиш израза в обратен полски запис.
2. Етап - изчисляване на израз записан в обратен полски запис. Най-важното на този запис е, че няма скоби!!!
Така, че просто не може да имаш проблем с пресмятането на числата, които са били в скобите - на първия етап не ги пресмяташ а "подреждаш"; на втория етап нямаш скоби.

от wnvko (3123 точки)

0
Аз точно така съм я направил. Примерът ми работи, но, ако отзад след него сложа + 5 * 5 нещата почват да се оплескват. Става 25 + 3 - 7, вместо 25 + 4

от p.penchev (204 точки)