Dzień dobry.
Mam już napisany parser wyrażenia, który liczy wartość działania na liczbach całkowitych. Jednak jest jeden problem. Podobno potęga ma łączność prawostronną. Jak można to zaimplementować? Bo mi liczy 2^2^2^2 jako 256 a powinno 65536. Jak można to wyrazić?
Dzięki
M.
No to zależy od tego jak zaimplementowałeś parser. Jak masz wyrażenie 2+2*7 to wychodzi Ci 28 czy 16? Problem dość podobny. Zgaduję, że zamiast zrobić najpierw drzewo parsowania takiej składni, od razu wykonujesz ewaluację?
W ONP właśnie o to chodzi, żeby nie robić drzewa, 2 + 2 * 7, to nie jest kwestia priorytetu operatorów?
Wychodzi mi 16. Mam funkcje:
var dzialanie = "2+2*7";
var tok = rozczlonkuj(dzialanie);
var onp = naONP(tok);
var wyn = obliczZONP(onp);
Najpierw usuwam spacje i dziele stringa na pojedyncze znaki, które następnie zamieniam na Tokeny, z informacją, czy to liczba, czy zmienna, czy operator, czy funkcja.
Potem Tokeny zamieniam na ONP
Potem obliczam.
Listing kolejnych etapów:
2*(3+7*2)^2
---- PRZED ONP
0: Token {typ: "Liczba", wartosc: "2", prior: -1}
1: Token {typ: "Operacja", wartosc: "*", prior: 2}
2: Token {typ: "NawiasO", wartosc: "(", prior: 0}
3: Token {typ: "Liczba", wartosc: "3", prior: -1}
4: Token {typ: "Operacja", wartosc: "+", prior: 1}
5: Token {typ: "Liczba", wartosc: "7", prior: -1}
6: Token {typ: "Operacja", wartosc: "*", prior: 2}
7: Token {typ: "Liczba", wartosc: "2", prior: -1}
8: Token {typ: "NawiasZ", wartosc: ")", prior: 0}
9: Token {typ: "Operacja", wartosc: "^", prior: 3}
10: Token {typ: "Liczba", wartosc: "2", prior: -1}l
----PO ONP
0: Token {typ: "Liczba", wartosc: "2", prior: -1}
1: Token {typ: "Liczba", wartosc: "3", prior: -1}
2: Token {typ: "Liczba", wartosc: "7", prior: -1}
3: Token {typ: "Liczba", wartosc: "2", prior: -1}
4: Token {typ: "Operacja", wartosc: "*", prior: 2}
5: Token {typ: "Operacja", wartosc: "+", prior: 1}
6: Token {typ: "Liczba", wartosc: "2", prior: -1}
7: Token {typ: "Operacja", wartosc: "^", prior: 3}
8: Token {typ: "Operacja", wartosc: "*", prior: 2}
wynik
578
No ale to znaczy, że źle przekształcasz na ONP. Stos powinien być taki: 2 2 2 2 ^ ^ ^.
Przekształcam, tylko stos mam: 2 2 ^ 2 ^ 2 ^
bo chodzi o łączność, nie wiem jak ją zaimplementować
Pokaż jeszcze jak to ewaluujesz.
function obliczZONP(tokenyONP) {
var wynik = [];
for (var i = 0; i < tokenyONP.length; i++) {
if (tokenyONP[i].typ === Typ.Liczba || tokenyONP[i].typ === Typ.Zmienna)
wynik.push(tokenyONP[i]);
if (tokenyONP[i].typ === Typ.Operacja) {
var a = wynik.pop().wartosc;
var b = wynik.pop().wartosc;
if (tokenyONP[i].wartosc === "+")
wynik.push(new Token(Typ.Liczba, String(parseInt(b) + parseInt(a))));
if (tokenyONP[i].wartosc === "-")
wynik.push(new Token(Typ.Liczba, String(parseInt(b) - parseInt(a))));
if (tokenyONP[i].wartosc === "*")
wynik.push(new Token(Typ.Liczba, String(parseInt(b) * parseInt(a))));
if (tokenyONP[i].wartosc === "/")
wynik.push(new Token(Typ.Liczba, String(parseInt(b) / parseInt(a))));
if (tokenyONP[i].wartosc === "^")
wynik.push(new Token(Typ.Liczba, String(parseInt(b) ** parseInt(a))));
}
}
return wynik[0].wartosc;
}
Ewaluacja tutaj nie ma wielkiego znaczenia, pokaż jak robisz parsowanie na ONP, bo to jest to co widocznie kuleje. Btw. zupełnie nie rozumiem, dlaczego od razu cały kod się tutaj nie znalazł, tylko poświęciliśmy 10 postów na to, by wyłuskać od Ciebie te informacje
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 && oper.typ !== Typ.NawiasO && oper.typ !== Typ.Przecinek)
wyjscie.push(dzialania.pop());
if (oper.typ !== Typ.Przecinek)
dzialania.push(oper);
}
else if (dzialania.length > 0 && oper.typ === Typ.NawiasZ) {
while (dzialania.length > 0 && dzialania[dzialania.length - 1].typ !== Typ.NawiasO)
wyjscie.push(dzialania.pop());
dzialania.pop(); // NawiasO
if (dzialania.length > 0 && 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
dodajOper(tokeny[i]);
}
while (dzialania.length > 0)
wyjscie.push(dzialania.pop());
return wyjscie;
}
mpaw napisał(a):
mi liczy
2^2^2^2jako256a powinno65536. Jak można to wyrazić?
Poprawnie RPN to będzie zapisane 2222^^^
Kolejno na stos dwójki
Na stosie będzie
2
2
2
2
Pierwszy ^, to zdejmujesz ze stosu 2 i 2, wykonujesz 2^2, dostajesz 4, 4 na stos, masz na stosie
4
2
2
Zdejmujesz 4 i 2 ze stosu, liczysz 2^4, dostajesz 16, wrzucasz na stos 16, masz teraz na stosie
16
2
Zdejmujesz ze stosu 2 i 16, liczysz 2^16, dostajesz 65536
Wrzucasz 65536 na stos
Nie masz już nic do parsowania
Zdejmujesz 65536 ze stosu - to jest twój rezultat obliczeń
(pisane z głowy i z tego co zostało z wykładów WDI i ASD)
Nie będę się upierać, że
Wrzucasz 65536 na stos
Nie masz już nic do parsowania
Zdejmujesz 65536 ze stosu - to jest twój rezultat obliczeń
trzeba robić kiedy nie ma już nic do parsowania, czy od razu podliczenie 2^16 = 65536 to wynik
Ja to wszystko wiem, powtarzam jeszcze raz NIE wiem tylko JAK zaimpelementować łączność prawostronną podczas generowania RPN
Do tworzenia algorytmu używałem http://www.infoceram.agh.edu.pl/files/onp.pdf a tu nie ma potęg
Pan @enedil zasugerował w komentarzu, że łączność można zaimplementować na wiele sposobów. Czy mógłby podać jeden z nich?
@mpaw: 2 2 ^ 2 ^ 2 ^ ten stos wygląda dobrze:
https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html#general-infix-to-postfix-conversion
A odwróć kolejność potęgowania i powinno być pozamiatane:
wynik.push(new Token(Typ.Liczba, String(parseInt(b) ** parseInt(a)))); -> wynik.push(new Token(Typ.Liczba, String(parseInt(a) ** parseInt(b))));
@lion137: Dzięki! Jednak na stronie https://www.dcode.fr/reverse-polish-notation generuje RPN taki, jak powiedziały chłopaki, tj. 2 2 2 2 ^ ^ ^
Znalazłem gotowca
https://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm#JavaScript
@mpaw: Sprawdziłem, trzeba parsować już z wiedzą o łączności, wersja, którą podałem nie zadziała dla, np.: 2 ** 3 ** 4.