javascript array parsing matching

Let's say I have an array.

["red", "blue", "neon", "black", "orange"]

I want to evaluate whether or not a certain matching pattern is true.

I want commas to indicate OR and && to indicate AND.

"red&&blue" -> true
"blue&&white" -> false
"red,white" -> true
"(red&&blue),(red&&white)" -> true
"(red&&blue)&&(red&&white)" -> false
"(red&&blue)&&(red&&neon)" -> true

What kind of matching scheme should I use? I would like to not implement a parser from scratch, if there's any existing that would be great, but otherwise I would like the logic to work just like how it works in javascript with unlimited complexity.

I'm basically looking for something like this but for javascript: Java library for parsing & building logical expressions

Upvotes: 1

Answers (3)

thefourtheye

Reputation: 239683

I think this particular case, can be solved with this simple function

var whiteList = ["red", "blue", "neon", "black", "orange"];
function evaluator(inputString) {
    var data = whiteList.reduce(function(previous, current) {
        return previous.split(current).join("####");
    }, inputString);
    data = data.replace(",", "||").replace(/[a-zA-Z]+/g, "false");
    return eval(data.replace(/####/g, "true"));
}

Sample run, with testcases (Thanks to @T.J. Crowder :)

Upvotes: 1

T.J. Crowder

Reputation: 1075765

You'll almost certainly be best off writing a parser or using one someone's already written. As you pointed out in the comments, for this very constrained input, it's actually really easy:

Split the string on the operators
Walk through the resulting split string:
- Validating operators
- Converting , to ||
- Optionally validating the names
- Replacing names with true (if it's in the array) or false (if it isn't)
Rejoin the result into a string again
Run the result through eval (since you now know it only has the operators you've whitelisted and the text true or false)

Here's a quick proof-of-concept: Live Copy | Live Source

<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8 />
<title>Expression Thingy</title>
  <style>
    .good {
      color: green;
    }
    .bad {
      color: #d22;
    }
  </style>
</head>
<body>
  <script>
    (function() {
      var array = ["red", "blue", "neon", "black", "orange"];
      var tests = [
        {expr: "red&&blue",                 expect: true},
        {expr: "blue&&white",               expect: false},
        {expr: "red,white",                 expect: true},
        {expr: "(red&&blue),(red&&white)",  expect: true},
        {expr: "(red&&blue)&&(red&&white)", expect: false},
        {expr: "(red&&blue)&&(red&&neon)",  expect: true},
        {expr: "(red+blue)&&(red!neon)",    expectInvalid: true}
      ];
      var data;

      // Turn data into an object with named properties, to make lookups
      // faster
      data = {};
      array.forEach(function(entry) {
        data[entry] = true;
      });

      // Run the tests
      tests.forEach(runTest);

      function runTest(test) {
        var parts, invalid = false;

        // Get an array of tokens: We'll get `(`, `)`, `,`, `&&`, whitespace, or a name in each array slot
        parts = test.expr.match(/&&|,|\(|\)|\s+|[^()&,]+/g);

        // Validate the operators and turn the names into "true" or "false"
        parts.forEach(function(part, index) {
          switch (part) {
            case ",":
              // Valid operator, replace with ||
              parts[index] = "||";
              break;
            case "&&":
            case "(":
            case ")":
              // Valid operator
              break;
            default:
              // Name or whitespace
              if (!part.replace(/\s+/g, "")) {
                // Whitespace
              }
              else {
                // Name, validate it -- obviously apply whatever rule works
                // for your data, the rule below allows A-Z, $, and _ in
                // the first position and those plus digits in subsequent
                // positions.
                if (!/^[A-Za-z$_][A-Za-z0-9$_]*$/.test(part)) {
                  // Invalid
                  display("Invalid name: " + part, test.expectInvalid);
                  invalid = true;
                }
                else {
                  // Valid, replace it
                  parts[index] = data[part] ? "true" : "false";
                }
              }
              break;
          }
        });
        if (!invalid) {
          // Now we know parts only has valid stuff we can trust in it, rejoin
          // and eval it
          result = !!eval(parts.join(""));
          display(test.expr + ": Got " + result + ", expected " + test.expect, result === test.expect);
        }
      }

      function display(msg, good) {
        var p = document.createElement('p');
        p.innerHTML = String(msg);
        if (typeof good !== "undefined") {
          p.className = good ? "good" : "bad";
        }
        document.body.appendChild(p);
      }
    })();
</script>
</body>
</html>

You'd probably want to massage the validation rules at least a bit.

Old answer, largely assumed you could trust the input:

It's easy to turn those inputs into valid JavaScript expressions. Then you can either:

Use a parser someone else has already written, ~~like this one (details in this blog post)~~ (that one doesn't seem to support && and ||, though perhaps you could extend it to), or
Convert the array into object properties and use eval. Never trust eval on inputs that aren't safe or can't be made safe. But if the inputs are safe or can be made safe, eval is fine.

Assuming the values in the array are valid JavaScript identifiers, you can turn those expressions into valid JavaScript expressions simply by changing , to ||:

str = str.replace(/,/g, "||");

Similarly, this turns that array into an object with those named properties:

var obj = {};
data.forEach(function(entry) {
    obj[entry] = true;
});

...which you'd presumably then pass into the expression evaluator.

If you're going the eval route, you have to do a bit more prep on the string, turning "(red&&blue),(red&&white)" into '(obj["red"]&&obj["blue"])||(obj["red"]&&obj["white"])', like this:

str = str.replace(/,/g, "||").replace(/\b([a-zA-Z0-9_]+)\b/g, 'obj["$1"]');

I won't do an example using an expression evaluator library, but here are the basics with eval: Live Copy | Live Source

<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8 />
<title>Expression Thingy</title>
  <style>
    .good {
      color: green;
    }
    .bad {
      color: #d22;
    }
  </style>
</head>
<body>
  <script>
    (function() {
      var data = ["red", "blue", "neon", "black", "orange"];
      var tests = [
        {expr: "red&&blue",                 expect: true},
        {expr: "blue&&white",               expect: false},
        {expr: "red,white",                 expect: true},
        {expr: "(red&&blue),(red&&white)",  expect: true},
        {expr: "(red&&blue)&&(red&&white)", expect: false},
        {expr: "(red&&blue)&&(red&&neon)",  expect: true}
      ];
      var obj;

      // Turn data into an object with named properties
      obj = {};
      data.forEach(function(entry) {
        obj[entry] = true;
      });

      // Turn the expressions into eval strings
      tests.forEach(createEvalString);

      // Run the tests
      tests.forEach(runTest);

      function createEvalString(test) {
        test.evalStr = test.expr.replace(/,/g, "||").replace(/\b([a-zA-Z0-9_]+)\b/g, 'obj["$1"]');
      }

      function runTest(test) {
        var result;

        display(test.evalStr);
        result = !!eval(test.evalStr); // Relies on us closing over `obj`
        display(test.expr + ": Got " + result + ", expected " + test.expect, result === test.expect);
      }

      function display(msg, good) {
        var p = document.createElement('p');
        p.innerHTML = String(msg);
        if (typeof good !== "undefined") {
          p.className = good ? "good" : "bad";
        }
        document.body.appendChild(p);
      }
    })();
  </script>
</body>
</html>

That's just a starting point. For one thing, you'll want to check the strings carefully before transforming them and using them with eval.

Upvotes: 1

georg

Reputation: 215049

For future readers, here's a more reliable way to do the job:

go to http://pegjs.majda.cz/online
enter the grammar for your mini-language
test the grammar with your examples
click "download parser"

That's basically all about that - no need to reinvent wheels.

For the examples you've posted the grammar can be like this:

{
var props = ["red", "blue", "neon", "black", "orange"]; 
}


start
  = additive

additive
  = left:multiplicative "," right:additive { return left || right }
  / multiplicative

multiplicative
  = left:primary "&&" right:multiplicative { return left && right }
  / primary

primary
  = atom
  / "(" additive:additive ")" { return additive; }

atom 
  = letters:[a-z]+ { return props.indexOf(letters.join("")) >= 0 }

Upvotes: 2

javascript array parsing matching

Answers (3)

Related Questions