9ms C solution, using BNF and Recursive descent parsing, that can calculate +-*/( ).


  • 0
    W
    /*
    E -> T +- T | T
    T -> F * / T | F
    F -> (E) | num
    expr is the original expression, wont be changed
    s is the address of expr, pointing to current pos that we are handling
    */
    void trim_space(char *s) {
    	char *p = s;
    	while (*s) {
    		if (*s == ' ')	s++;
    		else			*p++ = *s++;
    	}
    	*p = '\0';
    }
    double E(char *expr, char** s) {
    	double T(char *expr, char** s);
    	double ret = 0.0F;
    	if (!**s) return ret;
    	ret = T(expr, s);
    	while (**s == '+' || **s == '-') {
    		(*s)++;
    		ret += *(*s - 1) == '+'? T(expr, s):-T(expr, s);
    	}
    	return ret;
    }
    
    double T(char *expr, char** s) {
    	double F(char *expr, char** s);
    	double ret;
    	ret = F(expr, s);
    	while (**s == '*' || **s == '/') {
    		(*s)++;
    		ret *= *(*s - 1) == '*'?F(expr, s):1 / F(expr, s);
    	}
    	return ret;
    }
    
    double F(char *expr, char** s) {
    	if (!**s) return 1.0F;
    	double ret = 1.0F;
    	if (**s == '(') {
    		(*s)++;
    		ret = E(expr, s);
    	}
    	if (**s == ')') (*s)++;// do nothing
    	else if (**s >= '0' && **s <= '9' || **s == '+' || **s == '-') {
    		ret = strtod(*s, s);
    	}
    	return ret;
    }
    int calculate(char* s) {
        trim_space(s);
        char *p = s;
        return E(s, &p);
    }
    

Log in to reply
 

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