[JAVA of C++] Rekenmachine programmeren

[Verwijderd]

hey, ik heb een vraag over hoe ik een rekenmachine moet programmeren. Een gewone simpele rekenmachine heb ik al gemaakt en daar is niet veel moeilijks aan. Het is nu zo dat ik een wat ingewikkeldere rekenmachine moet maken. In java of c++ maakt niet uit.

Deze rekenmachine heeft de mogelijkheid om + - * en / te doen en om met haakjes te werken. Alleen moet dit allemaal gebeuren in 1 tekstvak. Als je bijvoorbeeld een som hebt:

( 10*2 ) / ( 5 +1 ) =

dt moet je dan zelf typen in 1 tekstvak. Op de 1 of andere manier moet hij alle tekens van elkaar onderscheiden. Mijn kennis gaat zo ver dat ik bijvoorbeeld een getal in een tekstvak kan invoeren en die kan uitlezen en converteren naar een double zodat je er iets mee kan. Maar hoe is het nu mogelijkheid om alle tekens apart te lezen en er ook nog een bepaalde context in te brengen.

Ik stel me zo voor dat ik een programma moet maken die per teken gaat kijken wat voor teken het is. Als er een haakje open staat, dan moet er een methode starten die kijkt wat er allemaal staat voor het haakje sluiten.

Ik heb er wel ideeen over, maar ik kan het niet in de praktijk brengen omdat ik daar de kennis niet voor heb.

[Soultaker]

Als ik je goed begrepen heb beperk je je vraag tot het verwerken van de invoertekst. Het ontleden van tekst in componenten wordt in het algemeen 'parsing' genoemd: het omzetten van een stuk tekst in een boomstructuur volgens de specificatie van een bepaalde grammatica. Om ermee te experimenteren is waarschijnlijk Java het makkelijkst, aangezien er veel introductiemateriaal is over parsing in Java en er minder verschillende mogelijkheden zijn dan in C/C++ en de situatie dus overzichtelijker is.
_{Mocht je toch voor C++ kiezen dan wil ik je op het bestaan van Spirit wijzen; een parser framework geïmplementeerd met behulp van C++ templates, waardoor geen code gegenereert hoeft te worden.}

Maar veel belangrijker is dat je een introductie zoekt in parsing. Daarbij wordt in Java vaak gebruik gemaakt van parser generators die code genereren om bepaalde grammatica's te verwerken. Twee bekende voorbeelden zijn ANTLR en JavaCC, maar er zijn er nog veel meer.

Een redelijk simpele 'taal' zoals voor de rekenmachine die je beschrijft (met wat simpele operatoren, getallen en haakjes) is ook goed met de hand (zonder parser generators) te schrijven. Een voorbeeld daarvan kun je hier vinden:
Een voorbeeld kun je hier vinden:
http://www.cs.bris.ac.uk/...0122/java/calc/index.html

Suggesties voor boeken heb ik niet direct; ik heb zelf "Programming Language Processors in Java" van Watt en Brown gelezen. Dat boek gaat wat verder (gaat onder andere over compilers); het voordeel is dat er wordt gefocused op het handmatig schrijven van parsers wat nuttig is bij het begrip van parser generators en dergelijke, maar helaas wordt er maar één parse-strategie behandelt. Voor jouw doel zijn de eerste paar hoofdstukken wel heel goed van toepassing, denk ik.

[Verwijderd]

Als je het in C++ wil doen moet je "Stroustrup" (The programming language C++) maar eens pakken. Daarin word een geavanceerde rekenmachine gemaakt om concepten van C++ uit te leggen. Zie bijvoorbeeld hoofdstuk 6.

Lijkt me een uitstekende manier om wat meer te leren. De gebruikte principes lijken me niet echt taal-afhankelijk.

[ Voor 13% gewijzigd door Verwijderd op 06-03-2004 22:08 ]

[Cuball]

effe zoeken voor infix calculator

[ Voor 10% gewijzigd door Cuball op 07-03-2004 13:07 ]

[Verwijderd]

Ok alvast bedankt voor de reacties. Nu ga ik kijken of het me lukt

[Reptile209]

Ik heb ooit zoiets gemaakt met een soort van binaire boom:
* zoek de hoogste operator (van rechts naar links, volgorde: * / + -)
* splits daar je formule in 2 delen: links en rechts als nieuwe takken van de boom en bewaar de operator
* doe nu recursief op links en rechts hetzelfde, dus de hoogste operator zoeken, splitsen en door

Uiteindelijk eindigen takken op een getal. Twee getallen + een operator kan je uitrekenen en vervangen door een getal zodat je de boom stap voor stap uitwerkt.

Terugrekenend krijg je hier dus:
3-18 = -15; 2+ -15 = -13; 6+12 = 18; 18 * -15 = -270

[madwizard]

Zie ook [rml][ Design OO / Java] Ontwerp van wiskundige expressies[/rml]

[Robtimus]

Reptile209 schreef op 07 maart 2004 @ 13:45:
Ik heb ooit zoiets gemaakt met een soort van binaire boom:
* zoek de hoogste operator (van rechts naar links, volgorde: * / + -)
* splits daar je formule in 2 delen: links en rechts als nieuwe takken van de boom en bewaar de operator
* doe nu recursief op links en rechts hetzelfde, dus de hoogste operator zoeken, splitsen en door

Uiteindelijk eindigen takken op een getal. Twee getallen + een operator kan je uitrekenen en vervangen door een getal zodat je de boom stap voor stap uitwerkt.
[afbeelding]
Terugrekenend krijg je hier dus:
3-18 = -15; 2+ -15 = -13; 6+12 = 18; 18 * -15 = -270

Eh, je maakt een tweetal foutjes IMHO:

1) operatoren * en / zijn in principe gelijk, net zoals + en -. Als + voor - gaat, dan is 4-2+2 gelijk aan 4-4, dus 0. Je wilt natuurlijk dat de uitkomst 4 is. Evenzo met * en / : 4/4*4 moet natuurlijk 1 zijn, maar als je * voor laat gaan komt eruit 1/4.

2) Je moet juist eerst op de laagste operatoren (+ en -) spitsen, daarna pas op de hogere (* en /). Want jij komt op (6+12)*(3-18+2) = -234 (je bent opeens weer met -15 gaan rekenen ipv -13), terwijl het zou moeten zijn 6+(12*3)-18+2 = 26

[Alarmnummer]

Bij ANTLR zit een voorbeeld van een rekenmachine + parser. Als je niet al te veel geinteresseerd bent in de theorie maar meer in de praktijk dan moet je daar even naar kijken.

[Reptile209]

IceManX schreef op 07 maart 2004 @ 14:04:
[...]
Eh, je maakt een tweetal foutjes IMHO:

1) operatoren * en / zijn in principe gelijk, net zoals + en -. Als + voor - gaat, dan is 4-2+2 gelijk aan 4-4, dus 0. Je wilt natuurlijk dat de uitkomst 4 is. Evenzo met * en / : 4/4*4 moet natuurlijk 1 zijn, maar als je * voor laat gaan komt eruit 1/4.

2) Je moet juist eerst op de laagste operatoren (+ en -) spitsen, daarna pas op de hogere (* en /). Want jij komt op (6+12)*(3-18+2) = -234 (je bent opeens weer met -15 gaan rekenen ipv -13), terwijl het zou moeten zijn 6+(12*3)-18+2 = 26

Volkomen gelijk. Ik had het een en ander even snel en uit het hoofd (van bijna 2jaar geleden) neergezet. Met jouw correcties erbij, klopt 'ie wel.
Ik zal eens kijken of ik de source nog ergens heb, die deed het nl wel goed

[riezebosch]

IceManX schreef op 07 maart 2004 @ 14:04:
[...]
Eh, je maakt een tweetal foutjes IMHO:

1) operatoren * en / zijn in principe gelijk, net zoals + en -. Als + voor - gaat, dan is 4-2+2 gelijk aan 4-4, dus 0. Je wilt natuurlijk dat de uitkomst 4 is. Evenzo met * en / : 4/4*4 moet natuurlijk 1 zijn, maar als je * voor laat gaan komt eruit 1/4.

2) Je moet juist eerst op de laagste operatoren (+ en -) spitsen, daarna pas op de hogere (* en /). Want jij komt op (6+12)*(3-18+2) = -234 (je bent opeens weer met -15 gaan rekenen ipv -13), terwijl het zou moeten zijn 6+(12*3)-18+2 = 26

Haha, volgens maak je zelf 1 foutje (heel kleintje hoor). Maar volgens mij wil je dat 4/4*4 gewoon 4 is, en niet 1 (en ook niet 1/4 natuurlijk)

[Glimi]

riezebosch schreef op 08 maart 2004 @ 18:51:
Haha, volgens maak je zelf 1 foutje (heel kleintje hoor). Maar volgens mij wil je dat 4/4*4 gewoon 4 is, en niet 1 (en ook niet 1/4 natuurlijk)

Als je in Nederland woont, dan zou je eigenlijk moeten willen dat vermenigvuldigen voor delen gaat. Wij zijn zo'n beetje het enige land met afwijkende prioriteiten. Het antwoord wat ik zou geven zou dan ook 1/4 zijn

[edit] Volgens mij is dat opgehouden met bestaan http://members.ams.chello.nl/r.kuijt/dale.htm Achja, kan ik het ook es hebben over 'vroeger'

[edit2] Oeps, rekenfout

[ Voor 20% gewijzigd door Glimi op 08-03-2004 19:05 ]

[voodooless]

Het netste is als je een lexical analyser gebruikt. Ik heb lang geleden als eens zoiets gemaakt met java, en dat ging erg goed. Is wel ff uitzoekwerk

[Robtimus]

riezebosch schreef op 08 maart 2004 @ 18:51:
Haha, volgens maak je zelf 1 foutje (heel kleintje hoor). Maar volgens mij wil je dat 4/4*4 gewoon 4 is, en niet 1 (en ook niet 1/4 natuurlijk)

Eh juist, oepsie

Glimi schreef op 08 maart 2004 @ 19:00:
Als je in Nederland woont, dan zou je eigenlijk moeten willen dat vermenigvuldigen voor delen gaat. Wij zijn zo'n beetje het enige land met afwijkende prioriteiten. Het antwoord wat ik zou geven zou dan ook 1/2 zijn

De tijd van Meneer van Dale is allang achterhaald; ook in NL hebben delen en vermenigvuldigen een gelijke prioriteit nu. Bovendien zou het nog altijd 1/4 moeten zijn

[Glimi]

IceManX schreef op 08 maart 2004 @ 19:04:
(...)
De tijd van Meneer van Dale is allang achterhaald; ook in NL hebben delen en vermenigvuldigen een gelijke prioriteit nu. Bovendien zou het nog altijd 1/4 moeten zijn

Ik zie het ja
Als 'strafwerk' zal ik hem vanavond even schrijven in Haskell
[edit] Wat als het goed is, makkelijk te vertalen zou moeten zijn naar Boost::Spirit

[ Voor 13% gewijzigd door Glimi op 08-03-2004 19:08 ]

[Gerco]

Voor het specifieke doel van een rekenmachine gaan parser generators naar mijn bescheiden mening wat ver (al is het natuurlijk wel de meest complete aanpak). Toen ik een eenvoudige expressie evaluator in elkaar moest zetten heb ik het op de volgende manier aangepakt:
• Expressie omzetten van infix naar postfix (rpn) notatie, bijvoorbeeld zo
• De rpn expressie evalueren, bijvoorbeeld zo

Dit levert een stuk eenvoudiger code op dan een parser generator zou doen, helaas is het natuurlijk ook stukken minder flexibel kwa uitbreidbaarheid e.d.

Het resulaat van bovenstaande tijdverspilling is overigens hier te vinden. Deze kan niet meer dan + - / * ( en ) begrijpen, maar demonstreert het principe best aardig. Als je er een echte stringtokenizer achter zou hangen wordt 'ie al een stuk bruikbaarder.

[ Voor 23% gewijzigd door Gerco op 08-03-2004 19:14 ]

[Glimi]

Glimi schreef op 08 maart 2004 @ 19:06:
Ik zie het ja
Als 'strafwerk' zal ik hem vanavond even schrijven in Haskell
[edit] Wat als het goed is, makkelijk te vertalen zou moeten zijn naar Boost::Spirit

Beloofd is beloofd: Have fun

Haskell:

module Calc where

import ParseLib

{- EBNF of the Calc grammar
-Positions of whitespaces ommited
-String literals between single quotes

-- Expressions
E -> T
E -> E '+' T
E -> E - T

-- Terms
T -> F
T -> T '*' F
T -> T '/' F

--Factors
F -> '(' E ')'
F -> Nums

-- Numbers
Nums -> Float   -- To lazy to overload it for Int's too

-}

{- The datatype -}
data Expr       = Con Float
                | Mul Expr Expr
                | Dvd Expr Expr
                | Add Expr Expr
                | Min Expr Expr
                deriving Show
                
{- The algebra for folding quickly -}
type ExprAlgebra e
                = ( Float -> e          -- Con
                  , e -> e -> e         -- Mul
                  , e -> e -> e         -- Dvd
                  , e -> e -> e         -- Add
                  , e -> e -> e         -- Min
                  )
                  
foldExpr        :: ExprAlgebra e -> Expr -> e
foldExpr (fCon, fMul, fDvd, fAdd, fMin)
                = fold 
                where fold (Con f)      = fCon f
                      fold (Mul e1 e2)  = fold e1 `fMul` fold e2
                      fold (Dvd e1 e2)  = fold e1 `fDvd` fold e2
                      fold (Add e1 e2)  = fold e1 `fAdd` fold e2
                      fold (Min e1 e2)  = fold e1 `fMin` fold e2
                
{- The parsing part, including priorities -}

pExpr           :: Parser Char Expr
pExpr           = chainl pTerm
                        (     const Add <$> symbol '+'
                          <|> const Min <$> symbol '-'
                        )
                     
pTerm           :: Parser Char Expr  
pTerm           = chainl pFactor
                        (     const Mul <$> symbol '*'
                          <|> const Dvd <$> symbol '/'
                        )
                    

pFactor         :: Parser Char Expr
pFactor         =     Con <$> readFloat
                  <|> parenthesised pExpr
                  
{- The evaluation -}

evalAlgebra     :: ExprAlgebra Float
evalAlgebra     = ( id, (*), (/), (+), (-) )

eval            :: Expr -> Float
eval            = (foldExpr evalAlgebra)

calc            :: [Char] -> Float
calc input      = eval input'
                where input' = fst $ head $ filter (null.snd) $ pExpr input

Bovenstaande code is eigenlijk het schoolvoorbeeld van het implementeren van een calculator met meerdere prioriteiten. Dit is nog verder te vereenvoudigen, maar dan is het niet zo simpel meer te begrijpen als je geen haskell kent
De evaluatie gaat door middel van een fold over de opgebouwde parsetree.

[ Voor 12% gewijzigd door Glimi op 08-03-2004 23:01 ]

[Soultaker]

Bij Spirit zit al voorbeeldcode van een simpele parser voor dit soort expressies (met prioriteiten, maar nog zonder haakjes), die gebruikt wordt ter illustratie van de de tekst in de gebruikershandleiding.

[Glimi]

Soultaker schreef op 09 maart 2004 @ 00:15:
Bij Spirit zit al voorbeeldcode van een simpele parser voor dit soort expressies (met prioriteiten, maar nog zonder haakjes), die gebruikt wordt ter illustratie van de de tekst in de gebruikershandleiding.

Kent Boost::Spirit eigenlijk ook folds over de AST's (bijv dmv visitors) of moet je die zelf nog aanmaken?