0
$\begingroup$

I am having a hard time even to formulate my question, so here it is:

I have an application that the user can go in and define on a webpage the logic one wants to evaluate for the student to comply with:

Student must take classes (MATH111 OR (MATH101 AND MATH103))

I have an array of all its enrolled classes like:

[MATH101,MATH102,MATH123,MATH444]

How do I evaluate my array on that expression to check if the students satisfies the AND/OR clause?

$\endgroup$
4
  • $\begingroup$ "I have an array of all its classes like" What does "its" refer to? The classes each student has already passed? What is your goal? To decide if a specific student satisfies the condition or to return all the students that satisfy the condition? $\endgroup$
    – phan801
    Commented Feb 8, 2019 at 12:19
  • $\begingroup$ The array I have is the classes the student has (I will edit the question). The goal is to decide if the student satisfies the criteria defined on the AND/OR clause $\endgroup$
    – Walucas
    Commented Feb 8, 2019 at 12:23
  • $\begingroup$ One option may be compiling the expression to a BDD. $\endgroup$
    – dkaeae
    Commented Feb 8, 2019 at 12:55
  • $\begingroup$ Are you asking how to parse an expression? $\endgroup$
    – xskxzr
    Commented Feb 8, 2019 at 16:15

1 Answer 1

1
$\begingroup$

First, your terminology is unusual. I wouldn't speak about "evaluating an array on an expression", but rather about "evaluating an expression using a variable assignment". Your array is, essentially, a variable assignment stating which boolean variables are true and which are false.

You can represent the expression as a syntax tree, having AND/OR internal nodes, and variable names MATH101 as leaves.

Then, you can evaluate the expression simply visiting the tree. In pseudocode:

boolean function eval(tree, array):

    if tree is a leaf X:
       return the boolean answering (X in array?)
    else if tree is OR(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 || b2)
    else tree must be AND(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 && b2)

If you want, you can even implement short-circuit evaluation to save some time. If your expressions are short it won't make any difference w.r.t. performance, though.

$\endgroup$
6
  • $\begingroup$ with this approach I would have a tree representing my logical expression. But its not clear where I would input my array of classes the student has $\endgroup$
    – Walucas
    Commented Feb 8, 2019 at 13:43
  • $\begingroup$ @Walucas I added an explicit array argument. In principle, you could avoid that argument and store it in a global variable (or an outer local variable, if your programming language support those) $\endgroup$
    – chi
    Commented Feb 8, 2019 at 13:46
  • $\begingroup$ Sorry, now you lost me. I cant see how the array get used on the comparison results $\endgroup$
    – Walucas
    Commented Feb 8, 2019 at 13:47
  • $\begingroup$ @Walucas I use it in the line return the boolean answering (X in array?), which scans the array and returns true if X is found, false otherwise. A linear search suffices. $\endgroup$
    – chi
    Commented Feb 8, 2019 at 13:48
  • $\begingroup$ ok, think I got it, let me implement in python and see if that works! $\endgroup$
    – Walucas
    Commented Feb 8, 2019 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.