#Valid parentheses leetcode

3 messages · Page 1 of 1 (latest)

brittle dock
#

https://leetcode.com/problems/valid-parentheses/
I wanted to know if there is a better way of doing this. When I see this problem I first thought of a recursive-descent parser and here's my solution:

struct Lexer {
    char* cur;
    char* end;
    inline void adv() {
        ++cur;
    }
    inline bool ok() {
        return cur < end;
    }
    inline char peek() {
        return *cur;
    }
};
class Solution {
public:
/*
Program = Expr*;

Expr => '(' Expr* ')'
|    '[' Expr* ']'
|    '{' Expr* '}'
|
;
*/
LeetCode
Valid Parentheses - LeetCode

Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every clo...
# 
bool expr(Lexer& lex) {
        if(!lex.ok())
            return false;
        switch(lex.peek()) {
            case '(': {
                lex.adv();
                while(true) {
                    auto bef = lex.cur;
                    if(!expr(lex))
                        return false;
                    if(lex.cur == bef)
                        break;
                }
                if(!lex.ok())
                    return false;
                if(lex.peek() != ')')
                    return false;
                lex.adv();
                break;
            }
            case '[': {
                lex.adv();
                while(true) {
                    auto bef = lex.cur;
                    if(!expr(lex))
                        return false;
                    if(lex.cur == bef)
                        break;
                }
                if(!lex.ok())
                    return false;
                if(lex.peek() != ']')
                    return false;
                lex.adv();
                break;
            }
            case '{': {
                lex.adv();
                while(true) {
                    auto bef = lex.cur;
                    if(!expr(lex))
                        return false;
                    if(lex.cur == bef)
                        break;
                }
                if(!lex.ok())
                    return false;
                if(lex.peek() != '}')
                    return false;
                lex.adv();
                break;
            }
        }
        return true;
    }
    bool isValid(string s) {
        Lexer lex = {s.data(), &s.back() + 1};
        while(lex.ok()) {
            auto bef = lex.cur;
            if(!expr(lex))
                return false;
            if(lex.cur == bef)
                return false;
        }
        return true;
    }
};
kindred skiff
#

there is no need for recursion