<funkcija> ::= <aditiv> [ {+|-} <aditiv> ]*
<aditiv> ::= <multip> [ {*|/} <multip> ]*
<multip> ::= <faktor> [^ <faktor>]*
<faktor> ::= -<funkcija> | x | (<funkcija>) | <broj> | <matem_funkc>(<funkcija>) | <broj>
<matem_funkc>::= exp | sqr | sin | cos  ...

class FunkcijaParser {
   private boolean debug=true;
   public void setDebug(boolean value) {
      this.debug = value;
   }
   
   private String funkcija;
   private class bnDrvo {
      // binarno drvo
      // --- ugradjene funkcije ---
   // 1.) parseFun
   // 2.) parseAditiv
   // 3.) parseMultip
   // 4.) parseFaktor
   // 5.) parseMatem --
   // 6.) parseBroj  -- neobavezno -- jos nisam siguran
   // 7.) parseVarX -- neobavezno
   }

   private bnDrvo Drvo = new bnDrvo();

   public FunkcijaParser(String f) {
      // konstruktor
   }
}

  public int parseX(String a) {
    this.sadrzaj = a;
    this.tip = TIP_FUNKCIJA;
    this.parseX();
  }

package bnDrvo;
public class bnDrvo {
    /*
            Binarno Drvo je struktura koja u uopstenom smislu ima 3 elementa :
                   a) lijevo dijete
                    b) desno dijete
                    c) sadrzaj (tj "sebe" - svoju vrijednost)

            djeca su reference na novo drvo - na istu vrstu - na sebe
    */
    public bnDrvo levo;      
    public bnDrvo desno;
    public Object sadrzaj;      
    public byte tip;      // tip cvora= string|operator|varx etc
   public boolean debug;
   
    public static final byte TIP_ERROR   =-1;
    public static final byte TIP_FUNKCIJA = 0;   // neobradjeni cvor - string
    public static final byte TIP_OPERATOR = 1;    // sabiranje, oduzimanje etc
    public static final byte TIP_BROJ      = 2;   // konstante
    public static final byte TIP_VARX      = 3;   // varijabla

    public bnDrvo () {                  // konstrutkor, poziva se pri kreiranju
            this.levo=null;
            this.desno=null;
            this.sadrzaj=null;   
            this.tip = TIP_ERROR;
            this.debug = true;
    }
}

public int parseFun() {
// vraca/returns :
            // 1: posao obavljen po propisu :DD
            // 0: posao obavljen (sa mogucom programskom greskom)
            //-1: sintaksna greska

            // ovu funkciju treba pokrenuti na pocetku
            // ok, treba parsiratit this.sadrzaj
            String f;   
            if ((this.tip != TIP_FUNKCIJA) || !(this.sadrzaj instanceof String))
                    return -1;
            else
                    f=(String) this.sadrzaj;

            if (f.length()<1)
                    return 0;

            int i;
            int zagrade=0;
            char ch;

            // dakle, f treba rastaviti na aditive (dijelove odvojene plusem i minusem)
            // sad cu da napravim jedan aditiv i on ce da bude u lijevoj grani drveta
            // dok cu ostatak prebaciti u desnu granu i pozvacu njegov parseFun
            this.levo = new bnDrvo();
            this.desno = new bnDrvo();

            // for krece od 1 zato jer prvo slovo moze biti minus sto bi moglo malo
            // da zbuni parser , pa tako krece od drugog slova
            for (i=1; i<f.length(); i++) {
                    ch = f.charAt(i);      // slovo po slovo - FUNKCIJA :DD
                    switch (ch) {
                            case '(':
                                    zagrade++;
                                    break;
                            case ')':
                                    zagrade--;
                                    break;
                            case '+':
                            case '-':
                                    if (zagrade != 0) break;
                                    // dakle imam aditiv i sad ga trebam smjestiti lijevo mjesto

                                    String operand = new String();
                                    operand+= ch;
                                    this.sadrzaj = operand;   // sabiranje/oduzimanje
                                    this.tip = TIP_OPERATOR;
                        
                                    String a = f.substring(0,i);   // lijevi aditiv
                                    String b = f.substring(i+1,f.length());   // desni ostatak
                                    if (debug)
                                       System.out.println("\tbn* l=" + a + " d=" + b);
                                    this.levo.parseAditiv(a);   // sad parsiram ovaj aditiv
                                    this.desno.parseFun(b);      // i ostatak
                                    return 1;               // k, sve ok
                    }   // switch
            }   // for

            if (zagrade!=0) {
                    this.tip = TIP_ERROR;
                    System.out.println("Greska sa zagradama !\n");
                    return -1;
            }
            // dakle, vise aditiva nije pronadjeno
            // to znaci da je cijela funkcija sastavljena od jednog aditiva
            return this.parseAditiv();
    }   // funkcija

int parseAditiv() {         
// ovu funkciju poziva funkcija parseFun
            /* da se podsjetimo
            // <aditiv> ::= <multip> [ {*|/} <multip>]*
            // kao i u proslom slucaju sredicu prvi multiplikativ
            // a ostatak cu da proslijedim dalje kao aditiv
            */   
            String f;   
            if ((this.tip != TIP_FUNKCIJA) || !(this.sadrzaj instanceof String))
                    return -1;
            else
                    f=(String) this.sadrzaj;

            if (f.length()<1)
                    return 0;

            int i;
            int zagrade=0;
            char ch;

            this.levo = new bnDrvo();
            this.desno = new bnDrvo();

            for (i=0; i<f.length(); i++) {
                    ch = f.charAt(i);      // slovo po slovo - FUNKCIJA :DD
                    switch (ch) {
                            case '(':
                                    zagrade++;
                                    break;
                            case ')':
                                    zagrade--;
                                    break;
                            case '/':
                            case '*':
                                    if (zagrade != 0) break;
                                    // dakle imam aditiv i sad ga trebam smjestiti lijevo mjesto

                                    String operand = new String();
                                    operand+=ch;
                                    this.sadrzaj = operand;   // mnozenje , dijeljenje
                                    this.tip = TIP_OPERATOR;

                                    String l = f.substring(0,i);   // lijevi multiplikativ
                                    String d = f.substring(i+1,f.length());   // desni ostatak
                                 
                                    this.levo.parseMultip(l);   // sad parsiram ovaj aditiv
                                    this.desno.parseAditiv(d);      // i ostatak
                                    return 1;               // k, sve ok
                    }   // switch
            }   // for

            if (zagrade!=0) {
                    this.tip = TIP_ERROR;
                    System.out.println("Greska sa zagradama !\n");
                    return -1;
            }
            // dakle, vise multiplikativa nije pronadjeno
            // to znaci da je cijela funkcija sastavljena od jednog multiplikativa
            return this.parseMultip();
    }

int parseMultip() {
            // <multip> ::= <faktor> [^<faktor>]*
            String f;   
            if ((this.tip != TIP_FUNKCIJA) || !(this.sadrzaj instanceof String))
                    return -1;
            else
                    f=(String) this.sadrzaj;

            if (f.length()<1)
                    return 0;

            int i;
            int zagrade=0;
            char ch;

            this.levo = new bnDrvo();
            this.desno = new bnDrvo();

            for (i=0; i<f.length(); i++) {
                    ch = f.charAt(i);
                    switch (ch) {
                            case '(':
                                    zagrade++;
                                    break;
                            case ')':
                                    zagrade--;
                                    break;
                            case '^':
                                    if (zagrade != 0) break;

                                    // k, nasao sam faktor
                                    String operand = new String();
                                    operand+= ch;
                                    this.sadrzaj = operand;   
                                    this.tip = TIP_OPERATOR;
                           
                                    String l = f.substring(0,i);            // faktor himself
                                    String d = f.substring(i+1,f.length());      // ostatak
                                    if (debug)
                                       System.out.println("\tbn* l=" + l + " d=" + d);
                                    this.levo.parseFaktor(l);   
                                    this.desno.parseMultip(d);
                                    return 1;                  
                    }   // switch
            }   // for

            if (zagrade!=0) {
                    this.tip = TIP_ERROR;
                    System.out.println("Greska sa zagradama !\n");
                    return -1;
            }
            // ako funkcija dodje dovde to znaci da je sve ovo faktor
            return this.parseFaktor();
    }

int parseFaktor() {
            /* FAKTOR : ovo je najvazniji - tezi - dio
                    Postoje slijedece mogucnosti:
            1) -<funkcija> #ovo prepoznajem po znaku minus !!! (oleeeee !!!)
            2) x   #varijabla x
            3) (<funkcija>) # dakle ako pocinje i zavrsava sa zagradama
            4) <broj> # ako pocinje sa cifrom
            5) <matematickafunkcija(<funkcija>)> # ako pocinje sa nekim slovima
            */
            String f;   
            if ((this.tip != TIP_FUNKCIJA) || !(this.sadrzaj instanceof String))
                    return -1;
            else
                    f=(String) this.sadrzaj;

            if (f.length()<1)
                    return 0;

            this.levo = new bnDrvo();
            this.desno = new bnDrvo();

            // ********** PRVI SLUCAJ -   "-<funkcija>"
            if (f.charAt(0)=='-') {
                    // ovo je jednako mnozenju sa -1 ili oduzimanju od 0
                    // ja cu uzeti oduzimanje od nula a mozda brze je samo promjeniti znak
                    // tako da onaj ko hoce bolje, neka malo prouci ovo sto pisem
                    // i lako ce shvatiti kako to da napravi ... (mnozenje sa -1...)
                    this.tip = TIP_OPERATOR;
                    this.sadrzaj = "-";   // oduzimanje
                    this.levo.tip = TIP_BROJ;
                    this.levo.sadrzaj = new Double(0);   // dakle, 0 - <funkcija> = - <funkcija>   
                    this.desno.tip = TIP_FUNKCIJA;
                    return this.desno.parseFun(f.substring(1,f.length()) );
            }
            // ********** DRUGI SLUCAJ -  "x"
            else if (f.charAt(0)=='x' && f.length()==1) {
                    this.tip = TIP_VARX;
                    this.sadrzaj = "";
                    return 1;   
            }
            // ********** TRECI SLUCAJ -  "{ ( <funkcija> ) }"
            else if (f.charAt(0)=='(') {
                    this.tip = TIP_FUNKCIJA;
                    // e, od sadrzaja treba odcjepiti zagrade
                    // NOTE: mozda vam se ucini da se na kraju mozda ne nalazi
                    // zatvorena zagrada, medjutim, ako je funkcija ispravno napisana,
                    // na kraju se sigurno nalazi zatvorena funkcija, inace ovo ne bi
                    // bio faktor vec bi od njega nastao aditiv-multiplikativ etc
                    // primjer : (x+2) + 2 nikako ne bi bio faktor jer bi ga funkcija
                    // parseFun iscjepala do (x+2) i 2. Kao sto vidite
                    // na kraju ostanu ili faktori bez zagrada(2) ili sa zagradama (x+2)
                    this.sadrzaj = f.substring(1,f.length()-1);
                    return this.parseFun();
            }
            // ********** CETVRTI SLUCAJ - BROJ - "<{0..9}* [ . {0..9}*]>"
            else if ("0123456789".indexOf(f.charAt(0)) >=0) {
                    // gore sam objasnio notaciju obicnog broja (cijeli i decimalni)
                    // hvala Sunu (bogu???) pa je ugradio double parser tako da se tu
                    // ne trebam muciti
                    this.tip = TIP_BROJ;
                    this.sadrzaj = new Double(Double.parseDouble(f));
                    return 1;
            }
            // ********** PETI SLUCAJ - MATEMATICKA FUNKCIJA - cos, sin, tan, pow itd
            else {
                    // e, za pocetak, u ovu grupu spadaju i neke konstante : pi i e
                    if (f=="pi") {
                       this.tip = TIP_BROJ;
                       this.sadrzaj = new Double(3.1415926);   // TODO: zamjeni sa precizn.
                        return 1;
                    } else if (f=="e") {
                       this.tip = TIP_BROJ;
                       this.sadrzaj = new Double(2.7182818);   // TODO: zamjeni sa precizn.
                        return 1;   
                    }
            
                    // <string> <(<funkcija>)>
                    // ili <imefunkcija>(<argumentfunkcije>)
                    // pa, onda, prvo da vidimo koje je ime funkcije .....
                    // ime cu pronaci funkcijom String.substring(0,m) - e ovo m trebam naci
                    // -- trebam naci index prve otvorene zagrade

                    int m = f.indexOf('(');
               
                    if (m<0) {
                            // greska !
                            this.tip = TIP_ERROR;
                            System.out.println("Greska sa matematickom funkcijom - nema otvorene !\n");
                            return -1;
                    }
                    // moram da provjerim da li se faktor zavrsava sa istom zagradom
                    // sa kojom i pocinje
                    if (f.charAt(f.length()-1) != ')')  {
                            System.out.println("Greska kod matematicke funkcije, nema zavrsne "+
                                                            "zagrade !\n");
                            this.tip = TIP_ERROR;
                            return -1;
                    }

                    String ime;
                    String argument;

                    ime = f.substring(0,m);
                    argument = f.substring(m+1,f.length() -1);   // bez zagrada ...
                    // ova debug linija sluzi za provjeravanje imena funkcije i njenog argumenta ...
               if (debug) System.out.println("\t\tIME=" + ime + " ARG=" + argument);
                    // ime funkcije je sadrzaj, a argument funkcije
                    // je lijevo dijete (lepo belo levo dete 0_o_O)            
                    // dok ce desno dete biti null jer nije potrebno ))):

                    this.tip = TIP_OPERATOR;
                    this.sadrzaj = ime;   

                    this.levo.tip = TIP_FUNKCIJA;
                    return this.levo.parseFun(argument);
            } // kraj petog slucaja
            // ********** NOTE: trebao bih ubaciti i provjeru gresaka, ali
            // ********** to cu poslije jer sad imam drugi prioritet
            //this.tip = TIP_ERROR;
            //return -1; // nije moguce dosegnuti
    }

   ///////////////////////////////////////////////////////////////////////////////////////
    //                         RACUNANJE FUNKCIJE ZA VRIJEDNOST X                        //
    ///////////////////////////////////////////////////////////////////////////////////////
    public double getY(double x) {
       switch (this.tip) {
          case TIP_FUNKCIJA:
          case TIP_ERROR:
             System.out.println("Greska pri racunanju - izgleda da funkcija nije dobro parsirana!\n");
             return 0;
          case TIP_OPERATOR:
             if (!(this.sadrzaj instanceof String)) {
                // ne vjerujem da je ovaj blok moguce dosegnuti, ali moje je da se osiguram :)))
                System.out.println("Greska prilikom racunanja operatora!\n");
                return -1;   
             }
             String op = this.sadrzaj.toString(); // iliti (String) this.sadrzaj
   
             if (op.equals("+")) {
                return this.levo.getY(x) + this.desno.getY(x);
               } else if (op.equals("-")) {
                return this.levo.getY(x) - this.desno.getY(x);
             } else if (op.equals("/")) {
                double tmp = this.desno.getY(x);
                if (tmp==0) {
                   // dijeljenje sa nulom, Metalova sugestija :))
                   // --- nikad se sam ne bih sjetio 0_OOOO_o   
                   System.out.println("Dijeljenje nulom !\n");
                   return 0.0;
                }
                return this.levo.getY(x) / tmp;
             } else if (op.equals("*")) {
                return this.levo.getY(x) * this.desno.getY(x);
             } else if (op.equals("^")) {
                return Math.pow(this.levo.getY(x), this.desno.getY(x));   
             }
             /////////////// MATEMATICKE FUNKCIJE ////////////////////
             // NOTE: trebam ugraditi provjeru - slicnu kao i ovu gore za x/0
              else if (op.equals("sin")) {
                return Math.sin(this.levo.getY(x));      
             } else if (op.equals("cos")) {
                return Math.cos(this.levo.getY(x));
             } else {
                if (debug) System.out.println("Trazena je nepoznata funkcija !\n");
                return 0.0;
                // OVO JE PRIVREMENA VRIJEDNOST - dakle nepoznata funkcija vraca 0
                // inace, slovodno dodajte nove funkcije ako vam trebaju
             }
          case TIP_VARX :
             if (debug) System.out.println("\t\t VARX " + x);
             // TODO: varijabla : modifikovanjem ovog dijela, i dijela parsiranja faktora
             //                   moguce je za minut napraviti parser koji npr ima dvije varijable
             //                   recimo x i y a rezultat bi onda bio z - kontate ? === 3D funkcija!!!
             ///////
             return x;
          case TIP_BROJ :
             Double Dbl = (Double) this.sadrzaj;
             double dbl = Dbl.doubleValue();
             if (debug) System.out.println("\t\tBROJ :: " + dbl);
             return dbl;
          default:
             if (debug)
             System.out.println("Definitivno, nesto je prolupalo u vezi sa bnDrvo.tip varijablom !");
       } // switch
       return 0;
    } // ::~


/**************************** LOG PART ****************************
6. novembar 2004 :
   GRESKA : prilikom parsiranja izraza (-2) * (-2) javlja se greska
    - objasnjenje : problem je sa ovom prvom zagradom, izraz -2 * (-2) je ispravno   
    - ***: negativan broj - izraz -M se pise ovako (-M) dakle, mora biti okruzen
      zagradama !!!! primjer 5 * (-3) = -15
    - ***: pojednostavio sam gresku : problem je ako funkcija pocinje sa
       otvorenom zagradom ! Odoh da pogledam ko pravi probleme ..... hm greska
       je u parseFun funkciji - zbog onog prvog slova parser preskoci prvu
       zagradu i onda misli(m) da je izraz neispravan
    - POPVRAVLJENO : dodao sam jedan if ispred pocetka petlje u parseFun funkciji
   DEBUG:  debug varijabla je postala static i po defaultu ima vrijednost false
*/

package FunkcijaParser;
import bnDrvo.bnDrvo;
public class FunkcijaParser {
   // @author Srecko Toroman
   // @description:
   /* Ovoj klasi se daje string iz kojeg ona pravi
      jedno drvo iz kojeg se mogu dobiti rezultati
      za neko x (opis je los, okok)
   */
   
   // My favourite color is blue ... no! Yellow !~-_,.. ,. .
   
   // k, ova klasa koristi klasu bnDrvo koja razdvaja string u drvo
   // a zatim ova klasa rekurzijom uvrstava x u drvo i izracunava
   // vrijednost funkcije ......
   
   // NOTE: primjetio sam jedan problem sa zagradama
   //      ne znam tacno o cemu se radi, ali preporucujem da koristite samo male zagrade
   private boolean debug=true;
   public void setDebug(boolean value) {
      this.debug = value;
   }
   
   private int isParsed = -1;
   public bnDrvo Fun;      // prebaciti na private kad se otklone bugovi
   
   public FunkcijaParser() {
      this.Fun = new bnDrvo();
      this.Fun.tip = new bnDrvo().TIP_ERROR;
      this.Fun.sadrzaj = "";
   }
   public FunkcijaParser(String funkcija) {
        this.Fun = new bnDrvo();
        this.Fun.sadrzaj = formatiraj(funkcija);
        this.Fun.tip = new bnDrvo().TIP_FUNKCIJA;
   }
   
   public int Parse(String s) {
      isParsed=this.Fun.parseFun(formatiraj(s));   
      return isParsed;
   }
   
   public double IzracunajY (double X) {
      if (this.isParsed==1)
         return this.Fun.getY(X);         
      else return -1;
   }
   
   private String formatiraj(String a) {
      a.toLowerCase();                        // sve ide u mala slova
      StringBuffer nospc = new StringBuffer();      // String a bez razmaka (blankova)
      for (int i=0; i<a.length(); i++)
         if (a.charAt(i)!=' ')
            nospc.append(a.charAt(i));
      return nospc.toString();
   }
}

import FunkcijaParser.FunkcijaParser;
import java.io.*;
public class test_prvi {
   public static void main (String[] args) {
            
      System.out.println("TEST PRVOG DIJELA PROJEKTA:\n");
      FunkcijaParser parser = new FunkcijaParser();
      String funkcija = "";
      BufferedReader ulaz = new BufferedReader (
         new InputStreamReader(System.in));
      try {
         funkcija = ulaz.readLine();
      }
      catch (Exception e) {
         
      }
      
      int status=parser.Parse(funkcija);
      System.out.println("Status parsiranja je : " + status);
      // 1 ok -  ostalo nije dobro
      
      double x;
      String xstr="0";
      try {
         xstr = ulaz.readLine();
      }
      catch (Exception e) {
         System.out.println(e.toString());   
      }
      
      x = Double.parseDouble(xstr);
      
      System.out.println("iiiiii ! Rezultat = " + parser.IzracunajY(x));
      
   }
}