16 ms Recursive descent supporting parenthese too. Simple EBNF format included


  • 0
    F
    //E -> T {-|+ T}
    //T -> M {*|/ M}
    //M -> ( E )
    //M -> number
    char *s;
    int evaluateM()
    {
        int v=0;
        while(*s == ' ') s++;
        if(*s == '(') {
            s++;
            v = evaluateE();
            while(*s == ' ') s++;
            if(*s != ')') cout << "missing ')' " <<endl; 
            s++;
            return v;
        }else if(isdigit(*s)) {
            v = strtol(s, &s, 10);
        }else{
            cout << "error" <<endl;
        }
        return v;
    }
    
    int evaluateT()
    {
        int v = evaluateM();
        while(*s == ' ') s++;
        while(*s == '*' || *s == '/') {
            char op = *s++;
            if(op == '*') v = v * evaluateM();
            else v = v / evaluateM();
            while(*s == ' ') s++;
        }
        return v;
    }
    
    int evaluateE()
    {
        int v = evaluateT();
        while(*s == ' ') s++;
        int sign = 1;
        while(*s == '-' || *s == '+') {
            sign = (*s == '+') ? 1 : -1;
            s++;
            v += evaluateT()*sign;
            while(*s == ' ') s++;
        }
        return v;
    }
    
    int calculate(string s) {
        this->s = &s[0];
        return evaluateE();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.