ONP (Odwrotna Notacja Polska) (RPN) -> priorytety nawiasów

Dzień dobry.

Korzystając z materałow: http://www.infoceram.agh.edu.pl/files/onp.pdf i https://pl.wikipedia.org/wiki/Odwrotna_notacja_polska zakodowałem funkcję do zmiany działania matematycznego na ONP. Jednak nawiasy mi źle działają. Co zrobiłem źle?

https://wklejaj.pl/mojONPmpaw

Dzięki
M.

Wyrażenie 2*(2+3)

Tutaj masz coś co działa: https://github.com/marcin-chwedczuk/shunting-yard-algo/blob/master/app/src/main/java/pl/marcinchwedczuk/shuntingyard/ShuntingYardAlgorithm.java i dodatkowo obsługuje unarne + i -.
Z zestawem testow: https://github.com/marcin-chwedczuk/shunting-yard-algo/blob/master/app/src/test/java/pl/marcinchwedczuk/shuntingyard/ShuntingYardAlgorithmTest.java .

Jeżeli znasz niemiecki to tu jest bardzo dobry opis algorytmu: https://de.wikipedia.org/wiki/Shunting-yard-Algorithmus (z jakiegoś powodu wersja ang jest bardzo słaba).

0xmarcin napisał(a):

Jeżeli znasz niemiecki to tu jest bardzo dobry opis algorytmu: https://de.wikipedia.org/wiki/Shunting-yard-Algorithmus (z jakiegoś powodu wersja ang jest bardzo słaba).

Cudze chwalicie, swego nie znacie Algorytm stacji rozrządowej jest też opisany na polskojęzycznej Wikipedii

Bardzo dziękuję za odpowiedzi. Jednak chciałbym znaleźć błąd w swoim kodzie, a nie kopiować czyjś. Załączam cały skrypt:

https://wklejaj.pl/calyonpmpaw

Dodam, że wyrażenia bez nawiasów kodują się dobrze.

Już wiem, gdzie jest błąd, ale nie wiem do końca jak go naprawić:

function naONP(tokeny) {
    var dzialania = [];
    var wyjscie = [];
    
    var dodajOper = function (oper) {
        if (dzialania.length == 0 || dzialania[dzialania.length - 1].prior < oper.prior)
            dzialania.push(oper);
        
        else if (dzialania.length > 0 && oper.typ !== Typ.NawiasZ) {
            while (dzialania.length > 0 && dzialania[dzialania.length - 1].prior >= oper.prior)
                wyjscie.push(dzialania.pop());
            
            dzialania.push(oper);
        }
        
        else if (dzialania.length > 0 && oper.typ === Typ.NawiasZ) {
            while (dzialania.length > 0 && dzialania[dzialania.length - 1].typ !== Typ.NawiasO) {
                if (dzialania[dzialania.length - 1].typ == Typ.Przecinek)
                    continue;
                
                wyjscie.push(dzialania.pop());
            }
            
            dzialania.pop(); // NawiasO
            
            if (dzialania[dzialania.length - 1].typ == Typ.Funkcja)
                wyjscie.push(dzialania.pop());
        }
    };
    
    var dodajStalaLubZmienna = function (el) {
        wyjscie.push(el);
    };
    
    for (var i = 0; i < tokeny.length; i++) {
        if (tokeny[i].typ === Typ.Liczba || tokeny[i].typ === Typ.Zmienna)
            dodajStalaLubZmienna(tokeny[i]);
        
        else if (tokeny[i].typ === Typ.Operacja || tokeny[i].typ === Typ.Funkcja)
            dodajOper(tokeny[i]);
    }
    
    while (dzialania.length > 0)
        wyjscie.push(dzialania.pop());
    
    return wyjscie;
}

W linii 11, zrzucam ze stosu operatory, bez względu na to, czy był nawias otwierający czy nie.

Jak to można obejść? :/

Dodałem kod z nawiasami do fora wewnątrz funkcji generującej kod RPN ale nadal kicha

Znalezione!

while (dzialania.length > 0 && dzialania[dzialania.length - 1].prior >= oper.prior && oper.typ !== Typ.NawiasO)

Trzeba było dopisać w drugim ifie, we whilu: ... && oper.typ !== Typ.NawiasO)