Професионална програма
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 1074 Точки
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 1074 Точки

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

0
lapd87 avatar lapd87 103 Точки

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

0