JavaScript Playground

const tokenize = (pattern) => {
    const tokens = [];
    let i = 0;

while (i < pattern.length) {
        const char = pattern[i];

if (char === '.' || char === '*' || char === '(' || char === ')' || char === '|') {
            tokens.push({
                type: char,
                value: char
            });
        } else if (char === '\\') { // Handle escaped characters
            i++;
            tokens.push({
                type: 'literal',
                value: pattern[i]
            });
        } else if (char === '[') { // Handle character classes
            let charClass = '';
            i++;
            while (pattern[i] !== ']' && i < pattern.length) {
                charClass += pattern[i];
                i++;
            }
            tokens.push({
                type: 'charClass',
                value: charClass
            });
        } else {
            tokens.push({
                type: 'literal',
                value: char
            });
        }
        i++;
    }

return tokens;
};

const parse = (tokens) => {
    let i = 0;

const parseSequenceExpression = () => {
        const node = {
            type: 'sequence',
            elements: []
        };

while (i < tokens.length) {
            const token = tokens[i];

if (token.type === 'literal') {
                node.elements.push({
                    type: 'literal',
                    value: token.value
                });
            } else if (token.type === '*') {
                const lastElement = node.elements.pop();
                node.elements.push({
                    type: 'star',
                    element: lastElement
                });
            } else if (token.type === '.') {
                node.elements.push({
                    type: 'dot'
                });
            } else if (token.type === 'charClass') {
                node.elements.push({
                    type: 'charClass',
                    value: token.value
                });
            } else if (token.type === '|') {
                i++;
                const right = parseSequenceExpression();
                return {
                    type: 'alternation',
                    left: node,
                    right
                };
            } else if (token.type === '(') {
                i++;
                node.elements.push(parseSequenceExpression());
            } else if (token.type === ')') {
                break; // End of a grouping
            }

i++;
        }

return node;
    };

return parseSequenceExpression();
};

const assertEqual = (expected, actual, message) => {
    if (expected !== actual) {
        console.error(`FAIL: ${message}`);
    } else {
        console.log(`PASS: ${message}`);
    }
};

const runTests = () => {
    const tests = [{
            pattern: "a.b*c",
            input: "abbbc",
            expected: true
        },
        {
            pattern: "a.b*c",
            input: "abc",
            expected: true
        },
        {
            pattern: "a.b*c",
            input: "ac",
            expected: true
        },
        {
            pattern: "a.b*c",
            input: "abbc",
            expected: true
        },
        {
            pattern: "a.b*c",
            input: "axbc",
            expected: false
        },

// Character class tests
        {
            pattern: "[abc]x",
            input: "bx",
            expected: true
        },
        {
            pattern: "[abc]x",
            input: "dx",
            expected: false
        },

// Grouping and alternation tests
        {
            pattern: "(a|b)c",
            input: "ac",
            expected: true
        },
        {
            pattern: "(a|b)c",
            input: "bc",
            expected: true
        },
        {
            pattern: "(a|b)c",
            input: "cc",
            expected: false
        },

// Escaped characters tests
        {
            pattern: "a\\.b",
            input: "a.b",
            expected: true
        },
        {
            pattern: "a\\.b",
            input: "a-b",
            expected: false
        },
        {
            pattern: "a\\*b",
            input: "a*b",
            expected: true
        }
    ];

tests.forEach(({ pattern, input, expected }, index) => {
        const tokens = tokenize(pattern);
        const ast = parse(tokens);
        const result = evaluateMatch(ast)(input) !== null;
        assertEqual(expected, result, `Test ${index + 1}`);
    });
};

runTests();

PASS: Test 1

PASS: Test 2

PASS: Test 4

PASS: Test 6

PASS: Test 7

PASS: Test 8

PASS: Test 9

PASS: Test 10

PASS: Test 11

PASS: Test 12

PASS: Test 13