?: és a lengyel-forma

Programozás - kezdő

Szeretnék felolvasni egy kifejezést, és lengyel-formára bontani, de a ?: operátornál megakadtam.

Az algoritmus, amit a lengyel-formához ajánlgatnak, mindenhol szavanként, tokenenként olvassa sorban a kifejezést, de a ?: operátor önmaga egy operátor, míg felolvasás közben két külön token, ráadásul további operátorok is kerülhetnek közéjük.

Tudtok segíteni abban, mi a korrekt lengyel-formára alakítási algoritmusa egy stringnek, ha van benne ?: operátor is?

  • 539 megtekintés

( apal v | 2022. 06. 13., h – 11:00 )

Igy hirtelen arra gondolnek hogy a ? es : operatorokat parba allitod, es ugy kezeled mint a ( ... ) part az algoritmus szempontjabol, azonban a : eseten a megfelelo prioritassal felveszel egy operatort es akkor veszed ki a stack-bol es teszed be az PSN sorozatba, amikor mint egy sima operator eljon az ideje. Hogy mi a prioritasa az jo kerdes, de szerintem ez az egyik legalacsonyabb prioritasu.

Es akkor mar csak arra kell figyelni hogy az egymasba agyazott ?:-k jol menjenek. De ez ugyanaz a problemakor mint amikor az a kerdes hogy az a+b+c-bol [a][b][+][c][+] -t  vagy [a][b][c][+][+] format csinalsz.

( NevemTeve | 2022. 06. 13., h – 11:43 )

Szerkesztve: 2022. 06. 13., h – 12:00

Nyilván meg lehet csinálni, csak nem lesz jó, ugyanis a rövidzár kiértékelést így nem lehet megcsinálni. Mondjuk van egy ilyen példa:

x==0 ? 100 : 100/x

ha ezt lefordítod arra, hogy:

x   ( x )
0   ( x 0 )
==  ( f )
100 ( f 100 )
100 ( f 100 100 )
x   ( f 100 100 x )
/   ( f 100 100/x )
?:  ( 100 vagy 100/x)

Akkor máris nem kerülted el a nullával osztás problémáját.

Szerk: egy kicsit átszerveztem; valamint hozzátenném, hogy a zárójelek között a verem pillanatnyi állapota látszik FORTH-stílusban; az 'f' egy logikai érték (flag), miszerint nulla volt-e az 'x' értéke

Nem így lenne ez helyes?

x   ( x )
0   ( x 0 )
==  ( f )
100 ( f ( 100 ) )
100 ( f ( 100 ) ( 100 ) )
x   ( f ( 100 ) ( 100 x ) )
/   ( f ( 100 ) ( 100 x / ) )
?:  ( 100 vagy 100/x )

Ha a Postscript jelölésrendszerét nézem:

x 0 eq { 100 } { 100 x div } ifelse exec

Tehát nem szabad kiértékelni a kifejezést, amíg nem derül ki, melyiket kell!

Nyilván meg lehet csinálni, csak nem lesz jó, ugyanis a rövidzár kiértékelést így nem lehet megcsinálni.

Erre is teljesen jo a PSN (reverse/suffix) jeloles:

[x] [0] [==] [100] [100] [x] [/] [?:].

Kiertekelesnel meg ugy implementalod a verem-strukturat hogy a verem egyes elemei nemcsak operandusok es operatorok lehetnek hanem onallo PSN sorozatok is (hierarchikus rendszer). Es az egyes operandusoknak megfelelo PSN sorozatokat viszont csak akkor ertekeled ki ha szukseg is van ra. Sima ügy, sok ilyet/hasonlot csinaltam mar :) Ebben a peldaban ez igy fog kinezni:

[[x] [0] [==]] [100] [[100] [x] [/]] [?:]

A [?:] elott 3 sorozat van mint operandus. Az elsot mindenkepp ki kell ertekelnie. Es annak az eredmenyetol fuggen ertekeli ki a masodikat vagy harmadikat. Amelyiket nem kell kiertekelnie azt eldobja. Ugyanez a logika jo a && meg || esetekre is.
 

( iwanabeguru | 2022. 06. 13., h – 12:02 )

Fogalamam sem volt mi a lengyel forma, de elolvastam egy rövid bevezetőt az ELTE honalpján

https://people.inf.elte.hu/veanna/alg1/segedanyagok/LengyelForma/index…

Szerintem ez aritmetikai/logikai operátorokra vonatkozik, a "?:" az egyik sem (szerintem),  ez syntactic sugar hogy ne kelljen if-else blockot írni. 

Pythonban ez nem is létezik, ott így néz ki

x = érték1 if feltétel else érték2

Szóval ez szerintem egy kakukk tojás és belül a fordító egy if-else utasításra átfordítja.

// Hocus Pocus, grab the focus
winSetFocus(...)

http://c2.com/cgi/wiki?FunnyThingsSeenInSourceCodeAndDocumentation

A C nyelvben van ilyen operátor, és valóban operátornak tűnik. Van asszociativitása és precedenciája is. Az "a?b:c" lengyel-formára hozott alakja valahogy így néz ki "a b c ?:".

Amúgy sem emlékszem olyan megkötésre, hogy a lengyel-formára hozás csak maximum két paraméteres operátorokra működne.

Az oké hogy operátornak tituláljuk. Gondolom mivel leírható más operátorokkal egy sorba ezért operátornak nevezik és kapott precedenciát, de ez inkább vezérlési szerkezetre hasonlít.

A matek tudásom már majdnem teljesen elkopott de nekem nem rémlik elágazás operátor, ez meg éppen az.

// Hocus Pocus, grab the focus
winSetFocus(...)

http://c2.com/cgi/wiki?FunnyThingsSeenInSourceCodeAndDocumentation

Én ismertem, csak reverse Polish notation (RPN) néven. Sose szerettem, nem bírom megszokni. Se számológépeknél, se dc-ben, sem nyelveknél (PS). Valahogy nagyon nyakatekertnek tűnik, állandóan tudatosítani kell, hogy mi van a stack-ben, melyik operátor pontosan mire fog vonatkozni. Nagyon kontraintuitív. Más felől viszont régen pont azért volt népszerű, mert könnyű interpretálni, kisebb hardver és erőforrás kell hozzá. Ugyanez igaz a funkcionális programozásra, azt se bírom rendesen megérteni, mert ott ugyebár a hagyományos imperatív, strukturális módszerek nem működnek, nem nyúlhat az ember a változókhoz, nem úgy néznek ki a loopok, stb..

Amit én a topiknyitóban nem értek, hogy pontosan milyen kifejezésről van szó, milyen nyelven, és mi célból akarja a kolléga „felolvasni”, RPN-re alakítani.

“Windows 95/98: 32 bit extension and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company that can't stand 1 bit of competition.”

( persicsb | 2022. 06. 13., h – 14:28 )

Szerkesztve: 2022. 06. 13., h – 14:36

Szerintem a ?: operátor kiértékeléséhez nem lesz elegendő a pushdown automata, ezért aztán hiába szervezed stackbe a kifejezés parzolt alakják, értelmezni nem fogod tudni, ahhoz Turing-gép kell.

 

Edit: bocs, valszeg hülyeséget mondtam. Nested stack automata is jó lesz neked, az már elegendő egy ilyen nyelv kiértékeléséhez. 

( NevemTeve | 2022. 06. 13., h – 15:05 )

Érdemes lenne nem utánozni a PHP hibáját: ha van egy ilyen kifejezésünk:

          a==1 ? b :  a==2  ? c : d

Az PHP-ben ezt jelenti:

         (a==1 ? b :  a==2) ? c : d

A többi programozási nyelven:

          a==1 ? b : (a==2  ? c : d)

Szerintem ez nem hiba, mert emberi intuíció mentén a PHP megoldásával értek egyet. Plusz ez pontosan definiálható a nyelv specifikációjában, hogy mi a kiértékelési sorrend. Persze az még jobb, ha mindent agyonzárójelezünk, a gépnek felesleges, de az emberi tényező miatt jó. Én pont emiatt nem szeretem a x y z * + formát, mert aki nem RPN-mágus, rohadtul belezavarodik, míg a ((x y *) z +) sokkal világosabbá teszi, még a gyp-seknek is. Ez kétség kívül hasznos a Lisp-ben, hogy a zárójelezés mindig világosan mutatja, hogy melyik függvényhívás milyen paraméterekre fog vonatkozni. Persze egyben idegesítő is követni, hogy minden zárójel le legyen zárva, könnyű kifelejteni egyet-egyet.

“Windows 95/98: 32 bit extension and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company that can't stand 1 bit of competition.”

Az első példád is ugyanilyen jó volt. Ez igazából preferencia kérdése. Nekem a PHP megoldása a logikusabb, neked a többié. Oda-vissza lehet érvelni. Szerintem az emberek a balról jobbra értelmezést szokták meg, pl. olvasásnál, számolásnál is, ezért szerintem intuitívabb a PHP-s módszer, ha a többiek akarják, tarthatunk róla szavazást. A másik fajta rendszer mögött meg az lehet a logika, hogy egymásba ágyazott if then else szerkezeteknél a legmélyebbre beágyazott, legbelül, legvégül meghívott szerkezetnek teljes, tovább nem bontható if then else-nek kell lennie, és ezt kiértékelve ágyazza be a többi kifejezésbe, de ez szerintem elég gépies logika, viszont ilyen oldalról meg az RPN mentalitásába jobban beleillik, ha tényleg az RPN a cél, igaz akkor meg a if then else ? : formáról vitatkoznánk, és nem az if ? then : else-ről.

“Windows 95/98: 32 bit extension and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company that can't stand 1 bit of competition.”