Simple C solution 6ms : Backus Naur Form


  • 0
    I

    The following BNF describe arithmetics operations:

    Expression ::= [ "-" ] Term { ("+" | "-") Term }
    Term       ::= Factor { ( "*" | "/" ) Factor }
    Factor     ::= Number | "(" Expression ")"
    Number     ::= Digit{Digit} | [Digit] "." {Digit}
    Digit      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
    

    It can be reduced to:

    Expression ::= [ "-" ] Term { ("+" | "-") Term }
    Term       ::= Factor { ( "*" | "/" ) Factor }
    Factor     ::= Number
    Number     ::= Digit{Digit}
    Digit      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
    

    Now, we have to implement each rule and see if it works.

    static bool     ft_expect_token(char **p, int const c)
    {
        while (0 != isspace(**p))
            ++(*p);
        if (**p != c)
            return (false);
        ++(*p);
        return (true);
    }
    
    static int      ft_parse_digit(char **p)
    {
        return (*(*p)++ - '0');
    }
    
    static int      ft_parse_number(char **p)
    {
        int total;
        
        while (0 != isspace(**p))
            ++(*p);
        total = 0;
        while (0 != isdigit(**p))
            total = total * 10 + ft_parse_digit(p);
        return (total);
    }
    
    static int      ft_parse_factor(char **p)
    {
        return (ft_parse_number(p));
    }
    
    static int      ft_parse_term(char **p)
    {
        int     result;
        
        result = ft_parse_factor(p);
        while (true)
        {
            if (true == ft_expect_token(p, '*'))
                result *= ft_parse_factor(p);
            else if (true == ft_expect_token(p, '/'))
                result /= ft_parse_factor(p);
            else
                break ;
        }
        return (result);
    }
    
    static int      ft_parse_expression(char **p)
    {
        int     result;
        
        if (true == ft_expect_token(p, '-'))
            result = -ft_parse_term(p);
        else
            result = ft_parse_term(p);
        while (true)
        {
            if (true == ft_expect_token(p, '+'))
                result += ft_parse_term(p);
            else if (true == ft_expect_token(p, '-'))
                result -= ft_parse_term(p);
            else
                break ;
        }
        return (result);
    }
    
    int calculate(char *s)
    {
        return (ft_parse_expression(&s));
    }
    

Log in to reply
 

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