regex vs stack

Benchmark created on

Description

Given a string containing any combinations of the 4 tokens BEGIN END Y N, calculate the number of "valid" logs contained within.

Logs are valid if they begin with BEGIN and end with END, with no nesting - that is, the string BEGIN BEGIN Y N END END contains only one valid log: BEGIN Y N END.

BEGIN END => 1 BEGIN Y END => 1 BEGIN Y N END BEGIN => 1 END END Y BEGIN N Y N BEGIN Y END => 1 END BEGIN => 0

Setup

const regexAnswers = [];
const stackAnswers = [];

const tokens = ["BEGIN", "END", "Y", "N"];
const strings = [];
for (let i = 1; i <= 10; i++) {
  const length = Math.floor(Math.random() * 10);

  const stringBuild = [];
  for (let j = 0; j < length; j++) {
    stringBuild.push(tokens[Math.floor(Math.random() * tokens.length)]);
  }

  strings.push(stringBuild.join(" "));
}

Teardown

stackAnswers.forEach((stackAnswer, index) => {
  if (stackAnswer !== regexAnswers[index]) {
    console.log("MISMATCH");
  }
});

Test runner

Ready to run.

Testing in
TestOps/sec
regex
strings.forEach((string) => {
  const matches = string.matchAll(/BEGIN([YN\s]+?)END/g);
  regexAnswers.push([...matches].length);
});
ready
stack
strings.forEach((string) => {
  let numMatches = 0;

  let hasBegun = false;

  string.split(" ").forEach((token) => {
    if (token === "BEGIN") {
      hasBegun = true;
    } else if (token === "END" && hasBegun) {
      numMatches++;
      hasBegun = false;
    }
  });

  stackAnswers.push(numMatches);
});
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.