Algorithm to parse an expression and assinging a value that satisfies the conditions

Question

The requirement is to parse a complex expression and assign the value to the variable that satisfies the condition. For e.g.

((!(($weatherResult.cityName=="Seattle")||($weatherResult.cityName=="Portland")))&&($weatherResult.cityName=="Folsom")) So based on this expression, the value of $weatherResult1.cityName should be Folsom.

Now if we take this expression

((!(($weatherResult.cityName=="Seattle")||($weatherResult.cityName=="Portland")))&&(!($weatherResult.cityName=="Folsom"))) Here the value of $weatherResult1.cityName should be any other city that does not match Seattle or Portland or Folsom. E.g. Boston

There is a catalog of US cities but not necessary that every expression needs to be backed by a catalog. The values can be plain strings as well.

One idea is to randomly pick a value and evaluate the expression to true. If it is false, then keep repeating, but this approach is time consuming and expensive. Rather I want to parse the expression and pick the value intelligently. I was thinking to use ANTLR to parse the expression but still not able to come up with an algorithm that would allow me to parse the tree and pick/assign values.

Anyone has any recommendations, please suggest.

Answer 1

A potential solution is to use a constraint programming solver. See https://mlabonne.github.io/blog/constraintprogramming/

Note that this problem is NP complete. It will quickly be solved for small inputs but runtime will explode for large inputs.

In fact, if all what you got is equalities to city names, you could use a SAT solver.