CODEWITHSUNDEEP
stringdesign-patterns
DanMatlin
DanMatlin

Reputation: 1252

Design pattern to evaluate a boolean expression

Is there a common/defined design pattern which will help program an evaluator for boolean expressions.

I am writing a string matching algorithm for such expressions and looking for a design pattern which will help structure the algorithm.

Sample Expected Strings -

"nike AND (tshirt OR jerseys OR jersey OR tshirts OR (t AND shirt)) AND black"

Upvotes: 0

Views: 256

Answers (2)

user11212840
user11212840

Reputation:

Your expression is in the infix notation. To evaluate it, convert it to the postfix notation.

Infix expression looks like:

<operand><operator><operand>

Postfix expression looks like:

<operand><operand><operator>

You can convert your expression using Shunting Yard Algorithm.

As the expression is converted, evaluate it using this approach (pseudocode):

Begin
   for each character ch in the postfix expression, do
      if ch is an operator ⨀ , then
         a := pop first element from stack
         b := pop second element from the stack
         res := b ⨀ a
         push res into the stack
      else if ch is an operand, then
         add ch into the stack
   done
   return element of stack top
End

Upvotes: 1

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522094

I don't know of a design pattern per se which would fit your problem, but if your programming language has regex support, we can easily enough write a pattern such as this:

(?=.*\bnike\b)(?=.*\b(?:tshirts?|jerseys?|t\b.*\bshirt|shirt\b.*\bt))(?=.*\bblack\b).*

The pattern can be explained as:

(?=.*\bnike\b)   match "nike" AND

(?=.*\b(?:tshirts?|jerseys?|t\b.*\bshirt|shirt\b.*\bt))
    match tshirt(s), jersey(s) or "t" and "shirt" AND

(?=.*\bblack\b)  match "black"

.*               then consume the entire line

Demo

Upvotes: 0

Related Questions