path: root/js/little-regex.js

// Inspired by https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
const matchHere = (pattern, text) => {
    if (pattern.length === 0) return true;
    
    // If pattern ends with $, match end of string
    if (pattern[0] === '$' && pattern.length === 1) return text.length === 0;

    // If next char is '*', match zero or more occurrences of prev char
    if (pattern[1] === '*') return matchStar(pattern[0], pattern.slice(2), text);

    // Match . or literal character
    if (text.length !== 0 && (pattern[0] === '.' || pattern[0] === text[0])) {
        return matchHere(pattern.slice(1), text.slice(1));
    }

    return false;
};

const matchStar = (prevChar, pattern, text) => {
    // Try matching zero occurrences first
    if (matchHere(pattern, text)) return true;

    // Then, match one or more occurrences of prevChar
    while (text.length > 0 && (text[0] === prevChar || prevChar === '.')) {
        text = text.slice(1);
        if (matchHere(pattern, text)) return true;
    }

    return false;
};

const match = (pattern, text) => {
    // Handle ^ anchor at the beginning
    if (pattern[0] === '^') {
        return matchHere(pattern.slice(1), text);
    }

    // Otherwise, check the entire string
    for (let i = 0; i <= text.length; i++) {
        if (matchHere(pattern, text.slice(i))) return true;
    }

    return false;
};

const assertEqual = (actual, expected, testName) => 
    console.log(actual === expected ? `Passed: ${testName}` : `Failed: ${testName}. Expected ${expected} but got ${actual}`);

assertEqual(match("ab*c", "ac"), true, "Star match 'ab*c' vs 'ac' (zero occurrences)");
assertEqual(match("ab*c", "abbbc"), true, "Star match 'ab*c' vs 'abbbc' (multiple occurrences)");
assertEqual(match("^ab.*c$", "abc"), true, "Complex match '^ab.*c$' vs 'abc'");
assertEqual(match("^ab.*c$", "abcd"), false, "Complex mismatch '^ab.*c$' vs 'abcd'");