Loading...
lapd87 avatar lapd87 103 Точки

[EXERCISE] Linear Data Structures - Problem {15} - Infix to Postfix

Привет отново колеги :)

мъча се тука с Infix to Postfix, но честно казано не съм и много наясно какво точно трябва да правя :D

с този код минавам 1 и 2 тест, останалите 3 са грешни.

https://pastebin.com/Z0L4TNKF

опитвам се да го направя с тези обяснения и по-точно псевдокода 

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, но....

0
Java Advanced
k.sevov avatar k.sevov 1077 Точки
Best Answer

Да, в методът беше проблема. Идеята на алгоритъма е, че ако имаме + или - си пълним всичко от стека докато стигнем до скобата, а ако има * или / пълним докато срещнем +, - или скоба. Ето ти твоя код с поправен метод и моя вариант за решение ако искаш да разгледаш.

0
lapd87 avatar lapd87 103 Точки

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

От това което обясняваш не разбирам защо при последователни еднакви + или - трябва да се спре пълненето...

(the operator at the top of the operator stack has equal precedence and is left associative)

явно тука някъде се губя

 

коригирах кода като махнах в метода проверката с if, тъй като вече е излишна

0
k.sevov avatar k.sevov 1077 Точки

При последователни + или - си ги слагаш всички (equal or higher precedence). Проблем би възникнал ако вземеш от стека някой с по-малък приоритет като например да имаш оператор *, а да вземеш от стека събиране. Идеята е, че при пресмятането на израз в postfix приоритетът на операциите изцяло зависи от подреждането като първо се изпълняват най-левите оператори. Затова и не можем в алгоритъма да добавяме от стека операции с по-нисък приоритет преди нашия оператор - те биха се изпълнили преди него и да получим грешен резултат. 

0
lapd87 avatar lapd87 103 Точки

това с * и / го разбирам, но защо 1+2+3 = 12+3+ а не на 123++? Това ми се губи...

0
k.sevov avatar k.sevov 1077 Точки

Резултатът и от двете ще е еднакъв, като разликата между тях е дали 1 + 2 + 3 ще го сметнем като (1 + 2) + 3 или 1 + (2 + 3). Тъй като стандартно се смята от ляво на дясно, при еднакъв приоритет си го правим 12+3+, за да се изпълни тази последователност, но чисто като резултат е все едно. Не знам дали има някакви други оптимизационни съображения да се прави по този начин, не съм навлизал в дълбочина за нотациите. 

0
24/05/2018 14:09:51
lapd87 avatar lapd87 103 Точки

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

0
NickShalamov avatar NickShalamov 0 Точки

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...

0
30/08/2020 12:50:24
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.