C++, top-down recursive descent parser solution


  • 0
    A

    I've solved this task by using a top-down recursive descent parser. Could be an overkill for just a validation, but this is just another approach to use.

    There are two primitives: bool match(char a) which checks if the next char is equal to given and char take() which returns a character and increments iterator. Return value is discarded since we just need to do validation. I've also added bool match(char a, char b) that works with the char ranges.

    On top of that there are helper functions:

    • bool takeIfMatches(char c) – takes a character if it matches given
    • void takeWhileMatches(char c) – takes characters while they match given

    Grammar is not very strict and elegant:

    • UntrimmedSignedScientificNum ::= [space]*<SignedScientificNum>[space]*
    • SignedScientificNum ::= [Sign](<Num>[.<Num>] | .<Num>)[e<SignedNum>]
    • SignedNum ::= [Sign]<Num>
    • Sign ::= + | -
    • Num ::= <0-9>[<0-9>]*

    I planned to use simpler expression for SignedScientificNum:

    • SignedScientificNum ::= <SignedNum>[.<Num>][e<SignedNum>]

    But hit that both .1 and 1. should be valid.

    The code is a regular top-down recursive descent parser. It tries to match the next character and picks a branch depending on the match.

    class Solution {
    public:
        string _s;
        string::iterator it;
        bool isNumber(string s) {
            _s = s;
            it = _s.begin();
            return parseUntrimmedSignedScientificNum();
        }
        
        // parsing expressions
        
        bool parseUntrimmedSignedScientificNum() {
            if (isEnd()) return false;
    
            takeWhileMatches(' ');
            
            if (!parseSignedScientificNum()) {
                return false;
            }
            
            takeWhileMatches(' ');
            
            return isEnd();
        }
        
        // valid: '1', '1.', '.1', '+.8', '1.1e8', '-1e-10'
        // invalid: '.', ' '
        bool parseSignedScientificNum() {
            if (isEnd()) return false;
            
            if (match('+') || match('-')) {
                take();
            }
    
            if (!match('.')) {
                if (!parseNum()) {
                    return false;
                }
                if (takeIfMatches('.')) {
                    parseNum();
                }
            } else if (takeIfMatches('.')) {
                if (!parseNum()) {
                    return false;
                }
            }
            
            if (takeIfMatches('e') || takeIfMatches('E')) {
                if (!parseSignedNum()) {
                    return false;
                }
            }
            
            return true;
        }
        
        bool parseSignedNum() {
            if (isEnd()) return false;
    
            if (match('+') || match('-')) {
                take();
            }
            return parseNum();
        }
        
        bool parseNum() {
            if (isEnd()) return false;
    
            if (!match('0', '9')) {
                return false;
            }
            
            takeWhileMatches('0', '9');
            return true;
        }
        
        
        // parser primitives
        void takeWhileMatches(char c) {
            while (takeIfMatches(c));
        }
    
        void takeWhileMatches(char c, char d) {
            while (takeIfMatches(c, d));
        }
        
        bool takeIfMatches(char c) {
            if (isEnd()) return false;
            if (match(c)) {
                take();
                return true;
            }
            return false;
        }
    
        bool takeIfMatches(char c, char d) {
            if (isEnd()) return false;
            if (match(c, d)) {
                take();
                return true;
            }
            return false;
        }
        
        bool match(char c) {
            if (isEnd()) return false;
            return *it == c;
        }
        
        bool match(char c, char d) {
            if (isEnd()) return false;
            return *it >= c && *it <= d;
        }
        
        char take() {
            if (isEnd()) return 10;
            return *it++;
        }
        
        bool isEnd() {
            return it == _s.end();
        }
    };
    

Log in to reply
 

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