[EXERCISE] Linear Data Structures - Problem {15} - Infix to Postfix
Привет отново колеги :)
мъча се тука с Infix to Postfix, но честно казано не съм и много наясно какво точно трябва да правя :D
с този код минавам 1 и 2 тест, останалите 3 са грешни.
опитвам се да го направя с тези обяснения и по-точно псевдокода
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
while there are tokens to be read:
read a token.
if the token is a number, then:
push it to the output queue.
if the token is a function then:
push it onto the operator stack
if the token is an operator, then:
while ((there is a function at the top of the operator stack)
or (there is an operator at the top of the operator stack with greater precedence)
or (the operator at the top of the operator stack has equal precedence and is left associative))
and (the operator at the top of the operator stack is not a left bracket):
pop operators from the operator stack onto the output queue.
push it onto the operator stack.
if the token is a left bracket (i.e. "("), then:
push it onto the operator stack.
if the token is a right bracket (i.e. ")"), then:
while the operator at the top of the operator stack is not a left bracket:
pop the operator from the operator stack onto the output queue.
pop the left bracket from the stack.
/* if the stack runs out without finding a left bracket, then there are mismatched parentheses. */
if there are no more tokens to read:
while there are still operator tokens on the stack:
/* if the operator token on the top of the stack is a bracket, then there are mismatched parentheses. */
pop the operator from the operator stack onto the output queue.
exit.
ако някой знае къде бъркам да каже сега или да замълчи завинаги :D
П.С. предполагам че може да е от проверката на операторите hasGreaterPrecedenceOrEqualAndLeft, но....
Благодаря ти за решението, но все пак не разбирам алгоритъма...
От това което обясняваш не разбирам защо при последователни еднакви + или - трябва да се спре пълненето...
явно тука някъде се губя
коригирах кода като махнах в метода проверката с if, тъй като вече е излишна
При последователни + или - си ги слагаш всички (equal or higher precedence). Проблем би възникнал ако вземеш от стека някой с по-малък приоритет като например да имаш оператор *, а да вземеш от стека събиране. Идеята е, че при пресмятането на израз в postfix приоритетът на операциите изцяло зависи от подреждането като първо се изпълняват най-левите оператори. Затова и не можем в алгоритъма да добавяме от стека операции с по-нисък приоритет преди нашия оператор - те биха се изпълнили преди него и да получим грешен резултат.
това с * и / го разбирам, но защо 1+2+3 = 12+3+ а не на 123++? Това ми се губи...
Резултатът и от двете ще е еднакъв, като разликата между тях е дали 1 + 2 + 3 ще го сметнем като (1 + 2) + 3 или 1 + (2 + 3). Тъй като стандартно се смята от ляво на дясно, при еднакъв приоритет си го правим 12+3+, за да се изпълни тази последователност, но чисто като резултат е все едно. Не знам дали има някакви други оптимизационни съображения да се прави по този начин, не съм навлизал в дълбочина за нотациите.
Да мен това ме бъркаше защото и аз си го представях еднакво. Както и да е още веднъж ти благодаря :)
2 godini po-kusno vlizam v razgovora: OK, obache ako 1 + 2 - 3 = "123+-" -> rezultata shteshe da e -4, a kogato imame "12+3-" - > rezultata e 0...