Kalkulator kompleksnih izraza

Ovaj tekst je više pojašnjenje načina rada klase nego uputstvo za njeno pravljenje. Iz tog razloga bi bilo pametno prvo skinuti klasu i pratiti njen kôd uporedo sa čitanjem teksta.

Za jedan od projekata na fakultetu, iz predmeta Objektno-orijentisano programiranje, odlučio sam da uradim program za iscrtavanje grafika. Već sam se bavio ovim problemom, ali tri godine ranije, i to u Delphiju, pa sam ovaj put ozbiljnije prišao problemu koji je trebalo da realizujem u Javi.

Program je bio veoma jednostavan:

• korisnik unese matematički izraz u kome figuriše promenljiva x
• korisnik ručno unese granice za X i Y osu, odnosno odredi deo grafika koji želi da se prikaže (verovatno najveća mana programa)
• grafik se iscrta

Sam GUI je realizovan uz pomoć Swinga, ali u to neću zalaziti. Ovde ću prikazati klasu za računanje (relativno) kompleksnih matematičkih izraza (doduše, ne na nivou Wolframa, pa ni kalkulatora koji dolazi uz Ubuntu) koja vuče korene iz tog projekta – pruža neke dodatne mogućnosti, ali bez iscrtavanja grafika (samim tim i bez promenljivih), pa je za demonstraciju njenih mogućnosti dovoljna konzolna aplikacija.

Prvo treba razmotriti šta se smatra kompleksnim izrazom. Ova klasa podržava sledeće:

• osnovne aritmetičke operacije
  • sabiranje +
  • oduzimanje –
  • množenje *
  • deljenje /
  • stepenovanje ^
• grupisanje pomoću zagrada () {} []
• funkcije (trigonometrijske, logaritamske i sl.)
• više načina zapisivanja brojeva
• matematičke konstante

Brojevi se čuvaju u promenljivama tipa double, pa je time ograničena preciznost računanja, format brojeva i, u neku ruku, tačnost. Kompleksnost izraza nije nikakav ograničavajući faktor, jer se on može posmatrati kao da je sastavljen iz manjih celina, koje se dalje mogu dodatno razbijati. Ovo ćemo postići rekurzijom, a izraz će približno moći ovako da izgleda:

• <izraz> <operacija> <izraz>
• ( <izraz> )
• – <izraz>
• <funkcija> ( <izraz> )
• <broj>
• <konstanta>

Imajući ovo na umu, zadati string ćemo analizirati tako da se pokriju svi slučajevi u ovom redosledu. Metod koji računa vrednost izraza će prvo izračunati njegovu vrednost za manje delove tog stringa, pa tek onda za ceo.

Ukoliko u nekoj od svojih iteracija metod naiđe na izraz koji ne može da obradi, to znači da izraz nije pravilno zapisan, i biće vraćena greška.

Priprema izraza

Kao prvo, želimo da obradimo prosleđeni string da bismo olakšali njegovo analiziranje. U ovom slučaju, sva velika slova se pretvaraju u mala, sve zagrade se zamenjuju odgovarajućim malim zagradama, i izbacuju se svi razmaci.

private static String sredi(String s)
{
	// Pretvaramo sva slova u mala

	s = s.toLowerCase();

	// Ostavljamo samo obicne zagrade

	s = s.replace('[', '(');
	s = s.replace('{', '(');
	s = s.replace(']', ')');
	s = s.replace('}', ')');

	// Uklanjamo sve razmake regularnim izrazom

	s = s.replaceAll("\\s", "");

	return s;
}

Ovaj pristup ima nekoliko nedostataka. Na primer, ukoliko korisnik loše uparuje različite zagrade, klasa to neće registrovati. Takođe, razmaci koji razbijaju ime neke funkcije (npr. “sq rt()”) će biti izbačeni, pa će izraz opet biti validan.

Nakon što smo ovo obavili, najzad možemo da pozovemo glavni rekurzivni metod.

Analiza zagrada i operacija – metod izraz()

Sada kada imamo izraz, potrebno je da odlučimo šta ćemo da radimo sa njim, odnosno od čega se on sastoji – da li je to neka funkcija, broj, ili pak zbir trideset sabiraka? Osnovna provera koju treba da izvršimo jeste da li su sve zagrade pravilno uparene/ugnježdene, što možemo jednostavno učiniti jednim prolazom kroz string. A usput ćemo baciti i pogled na operacije koje se nalaze u stringu.

Recimo da se u izrazu nalazi nekoliko aritmetičkih operacija koje nisu u zagradama (one koje jesu biće obrađene tokom nekog drugog poziva metoda, pa nas sada ne zanimaju). Pošto se naš izraz deli na manje delove koji se prvi računaju, očigledno je da u tim manjim delovima treba da se nađu operacije koje će se prve izvršiti – prvo se izvršava stepenovanje, pa množenje i deljenje, i na kraju sabiranje i oduzimanje.

Dakle, u trenutnoj iteraciji metoda treba da nađemo operaciju koja će se poslednja izvršiti, izračunamo izraze levo i desno od nje, i onda na njih primenimo tu operaciju. Na taj način će sve operacije u izrazima levo i desno koje su višeg prioriteta biti izvršene prve, a naša operacija na kraju. Poslednja operacija je, zbog prioriteta, krajnje desno sabiranje ili oduzimanje; ako toga nema, krajnje desno množenje ili deljenje; ako ni toga nema, onda krajnje desno stepenovanje.

Između ostalog, u ovom prvom prolazu kroz string (sa desno na levo) pamtimo i prvu otvorenu i poslednju zatvorenu zagradu, što ćemo kasnije koristiti. Ukoliko naiđemo na nepravilno uparene zagrade, vraćamo grešku.

Računanje izraza

Sada je došlo vreme da zapravo izračunamo vrednost izraza koji smo do sada samo analizirali.

Pošto smo u prethodnom prolasku kroz string odredili da li postoji neka operacija, kao i gde se ona nalazi ako postoji, prvo ćemo obraditi ovaj slučaj. Ukoliko postoji operacija, apsolutno sve u izrazu će se izvršiti pre nje, pa zato pozivamo metod izraz() za podstring levo od operacije i podstring desno od operacije. Nakon što izračunamo te dve vrednosti, pozvaćemo metod izracunajOperaciju() i vratiti vrednost izraza.

if (poslednjaOperacija > 0)
{
	double a = izraz(s.substring(0, poslednjaOperacija));
	double b = izraz(s.substring(poslednjaOperacija+1, duzina));

	return izracunajOperaciju(s.charAt(poslednjaOperacija), a, b);
}

Ako nemamo nijednu operaciju van zagrada, možda je to zato što je ceo izraz zapravo u jednoj zagradi. Ovo se može desiti ukoliko se računa izraz “(2+3)*(3+4)”, pa se poziva metod za izraz “(2+3)”. Ukoliko je to slučaj, jednostavno vrećemo vrednost izraza u zagradi.

if (poslednjaOperacija == -1
	&& prvaOtvorenaZagrada == 0
	&& poslednjaZatvorenaZagrada == duzina-1)
		return izraz(s.substring(1, duzina-1));

Sada smo došli do toga da nemamo nijednu operaciju, a ceo izraz nije u zagradi – tačnije, došli smo do prilično jednostavnog izraza: broj ili funkcija. Kako tom izrazu možda prethodi unarni minus, moramo prvo to da proverimo.

if (poslednjaOperacija == -1 && s.charAt(0) == '-')
{
	return -izraz(s.substring(1, duzina));
}

Ako nemamo ni taj minus, ostaju nam samo funkcija i broj. S obzirom da imamo niz dozvoljenih funkcija i metod koji računa vrednosti tih funkcija, jednostavno proverimo da li string počinje imenom neke od tih funkcija. Ukoliko počinje, računamo vrednost izraza, a ako ne počinje, pretvaramo taj izraz u broj, pošto je samo to ostalo kao mogućnost (uzevši u obzir da taj broj može biti i konstanta).

Kako se pretvaranje stringa u broj nalazi na samom kraju rekurzivne metode, ono će vratiti grešku ako je izraz bilo šta što nismo predvideli, što je u našem slučaju ekvivalentno lošem izrazu.

try {
	return new Double(s);
} catch (Exception e) {
	throw new Exception("Lose formiran izraz");
}

Testiranje

Evo ih (tačni) rezultati nekoliko izraza:

sqrt(15) = 3.872983346207417

tg(pi/2) = 1.633123935319537E16

2/2/2/2 = 0.25

(2*3-ln(25))/(pi/e + 1584 * 4^3)
	+ sqrt(sqrt(sqrt(pi)))*tg(2)
	= -2.5211481854407327

abs(sin(3/4*pi)*cos(1/4*pi)
	+ ln(15+e)
	- 2^sqrt(100)*abs(tg(-1)))^(1/3)
	= 11.675104522002854

Kao i uvek, ne garantujem da u kôd nema bagova, pa me o njima možete obavestiti u komentaru.

Klasu možete skinuti ovde. U pitanju je TXT fajl, jer WordPress iz nekog razloga ne dozvoljava upload JAVA fajlova.