10-regular-expression-matching

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <unordered_map>

using std::string;
using std::vector;
using std::cin;
using std::cout;

static const auto kSpeedUp = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
    TypeName(const TypeName&) = delete; \
    TypeName& operator=(const TypeName&) = delete;

template <typename T>
class RefCounted {
protected:
    RefCounted() : ref_count_(0) {}
public:
    void AddRef() const {
        ++ref_count_;
    }

    void Release() const {
        if (0 == --ref_count_) {
            delete static_cast<const T*>(this);
        }
    }
private:
    DISALLOW_COPY_AND_ASSIGN(RefCounted<T>)
private:
    mutable int32_t ref_count_;
};

template <typename T>
class RefPtr {
public:
    RefPtr() : ptr(nullptr) {}

    ~RefPtr() {
        if (ptr) {
            ptr->Release();
            ptr = nullptr;
        }
    }

    RefPtr(T* p) : ptr(p) {
        if (ptr) {
            ptr->AddRef();
        }
    }

    RefPtr(const RefPtr<T>& r) : ptr(r.ptr) {
        if (ptr) {
            ptr->AddRef();
        }
    }

    template <typename U>
    RefPtr(const RefPtr<U>& r) : ptr(r.Get()) {
        if (ptr) {
            ptr->AddRef();
        }
    }

    template <typename U>
    RefPtr(RefPtr<U>&& r) : ptr(r.Get()) {
        r.ptr = nullptr;
    }

    T* Get() const {
        return ptr;
    }

    T** GetAddressOf() const {
        return &ptr;
    }

    T& operator*() const {
        return *ptr;
    }

    T* operator->() const {
        return ptr;
    }

    T** operator&() {
        if (ptr) {
            ptr->Release();
            ptr = nullptr;
        }
        return &ptr;
    }

    RefPtr<T>& operator=(T* p) {
        if (p) {
            p->AddRef();
        }
        T* old = ptr;
        ptr = p;
        if (old) {
            old->Release();
        }
        return *this;
    }

    RefPtr<T>& operator=(const RefPtr<T>& r) {
        return operator=(r.ptr);
    }

    template <typename U>
    RefPtr<T>& operator=(const RefPtr<U>& r) {
        return operator=(r.Get());
    }

    RefPtr<T>& operator=(RefPtr<T>&& r) {
        RefPtr<T>(std::move(r)).Swap(*this);
        return *this;
    }

    template <typename U>
    RefPtr<T>& operator=(RefPtr<U>&& r) {
        RefPtr<T>(std::move(r)).Swap(*this);
        return *this;
    }

    template <typename U>
    bool operator==(const RefPtr<U>& rhs) const {
        return ptr == rhs.Get();
    }

    template <typename U>
    bool operator!=(const RefPtr<U>& rhs) const {
        return ptr != rhs.Get();
    }

    template <typename U>
    bool operator<(const RefPtr<U>& rhs) const {
        return ptr < rhs.Get();
    }

    void Reset(T* p) {
        operator=(p);
    }

    void Reset() {
        Reset(nullptr);
    }

    void Swap(T** pp) {
        T* old = ptr;
        ptr = *pp;
        *pp = old;
    }

    void Swap(RefPtr<T>& r) {
        Swap(&r.ptr);
    }
private:
    template <typename U>
    friend class RefPtr;

    typedef T* RefPtr::*Testable;
public:
    operator Testable() const {
        return ptr ? &RefPtr::ptr : nullptr;
    }
private:
    T* ptr;
};

constexpr char kNull = '\0';
constexpr char kAny = '.';

class FAState : public RefCounted<FAState> {
public:
    using StateType = int;

    enum OpType : int {
        kExact = 0,
        kZeroOrMore = 1
    };
public:
    StateType state_;
    OpType op_type_;
    FAState* prev_state_;
    bool is_accepting_state_;
    std::vector<std::pair<char, RefPtr<FAState>>> transition_list_;
public:
    FAState() : state_(0), op_type_(kExact), prev_state_(nullptr), is_accepting_state_(false) {}

    FAState(StateType state, OpType op_type, FAState* prev_state, bool is_accepting_state) :
        state_(state), op_type_(op_type), prev_state_(prev_state), is_accepting_state_(is_accepting_state) {}

    bool IsAcceptingState() const {
        return is_accepting_state_;
    }

    void AppendNextState(char accept_input, const RefPtr<FAState>& state) {
        transition_list_.emplace_back(accept_input, state);
    }
};

using FAStateList = RefPtr<FAState>;

class PatternParser {
public:
    explicit PatternParser(const std::string& pattern) : pattern_(pattern) {}

    explicit PatternParser(std::string&& pattern) : pattern_(std::move(pattern)) {}

    FAStateList ToFiniteAutomatonStates() {
        FAStateList state_list = new FAState(0, FAState::kExact, nullptr, false);
        RefPtr<FAState> current_state = state_list;

        char prev_char = 0;
        FAState::StateType current_index = 0;

        auto iter = pattern_.cbegin();

        while (iter != pattern_.cend()) {
            const char ch = *iter;
            const FAState::StateType new_index = current_index + 1;

            RefPtr<FAState> new_state;

            if ((isalpha(ch) || ch == '.') && (iter + 1 == pattern_.cend() || *(iter + 1) != '*')) {
                new_state = new FAState(new_index, FAState::OpType::kExact, current_state.Get(), false);
                current_state->AppendNextState(ch, new_state);
                prev_char = ch;
            } else if ((isalpha(ch) || ch == '.') && (iter + 1 != pattern_.cend() && *(iter + 1) == '*')) {
                if (ch == prev_char && current_state->op_type_ == FAState::kZeroOrMore) {
                    iter += 2;
                    continue;
                }
                new_state = new FAState(new_index, FAState::kExact, current_state.Get(), false);
                // spin
                RefPtr<FAState> spin_state = new FAState(new_index, FAState::kZeroOrMore, current_state.Get(), false);
                spin_state->AppendNextState(ch, spin_state);
                spin_state->AppendNextState(ch, new_state);

                current_state->op_type_ = FAState::kExact;
                current_state->AppendNextState(kNull, spin_state);
                current_state->AppendNextState(kNull, new_state);
                ++iter;
                prev_char = ch;
            } else if (*iter == '*') {
                ++iter;
                continue;
            }

            current_state = new_state;
            current_index = new_index;
            ++iter;
        }

        current_state->is_accepting_state_ = true;

        return state_list;
    }
private:
    std::string pattern_;
private:
    DISALLOW_COPY_AND_ASSIGN(PatternParser)
};

class RegularExpressionNFA {
public:
    explicit RegularExpressionNFA(const FAStateList& state_list) :
        current_state_(nullptr), state_list_(state_list), is_accepted_(false) {}

    explicit RegularExpressionNFA(FAStateList&& state_list) :
        current_state_(nullptr), state_list_(std::move(state_list)), is_accepted_(false) {}

    void InputString(const std::string& input) {
        current_state_ = state_list_.Get();
        
        is_accepted_ = DFS(current_state_, input, 0);
    }

    bool IsAccepted() {
        return is_accepted_;
    }
private:
    bool DFS(FAState* state, const std::string& input, size_t index) {
        if (index == input.length()) {
            if (state->IsAcceptingState()) {
                return true;
            }
        }

        for (auto& pair : state->transition_list_) {
            if (pair.first == kNull) {
                bool ret = DFS(pair.second.Get(), input, index);
                if (ret) {
                    return true;
                }
            } else if (index < input.length() && (pair.first == kAny || pair.first == input[index])) {
                bool ret = DFS(pair.second.Get(), input, index + 1);
                if (ret) {
                    return true;
                }
            } else {
                continue;
            }
        }

        return false;
    }
private:
    FAState* current_state_;
    FAStateList state_list_;
    bool is_accepted_;
private:
    DISALLOW_COPY_AND_ASSIGN(RegularExpressionNFA)
};

class Solution {
public:
    bool isMatch(string s, string p) {
        PatternParser pattern_parser(std::move(p));
        FAStateList state_list = pattern_parser.ToFiniteAutomatonStates();

        RegularExpressionNFA nfa(std::move(state_list));
        nfa.InputString(s);

        return nfa.IsAccepted();
    }
};

int main(void) {
    Solution sln;

    std::cout << std::boolalpha;

    auto match = sln.isMatch("aa", "a");
    std::cout << match << std::endl;

    match = sln.isMatch("aa", "a*");
    std::cout << match << std::endl;

    match = sln.isMatch("ab", ".*");
    std::cout << match << std::endl;

    match = sln.isMatch("aab", "c*a*b");
    std::cout << match << std::endl;

    match = sln.isMatch("mississippi", "mis*is*p*.");
    std::cout << match << std::endl;

    match = sln.isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*a*a*b");
    std::cout << match << std::endl;

    match = sln.isMatch("aaaaaaaaaaaaab", "a***********************b");
    std::cout << match << std::endl;

    match = sln.isMatch("", "a*");
    std::cout << match << std::endl;

    match = sln.isMatch("mississippi", "mis*is*ip*.");
    std::cout << match << std::endl;

    match = sln.isMatch("aaa", "a*a");
    std::cout << match << std::endl;

    match = sln.isMatch("aaa", "ab*a*c*a");
    std::cout << match << std::endl;

    match = sln.isMatch("aba", "ab*a*c*ba");
    std::cout << match << std::endl;

    match = sln.isMatch("aa", "c*.c");
    std::cout << match << std::endl;

    match = sln.isMatch("a", "ab*a");
    std::cout << match << std::endl;

    match = sln.isMatch("a", ".*..a*");
    std::cout << match << std::endl;

    match = sln.isMatch("bbbba", ".*a*a");
    std::cout << match << std::endl;

#ifdef _WIN32
    system("pause");
#endif
    return 0;
}