Except for being recursive the procedure described above is fairly simple. It does depend on having a parser though, and parsers are not simple. For the postfix version of the language it’s possible to avoid the parsing stage entirely and write a simple checker which works directly on the unparsed statements.
Our simple checker needs a stack, but no other data structures. A stack is a simple data structure with only three operations. We can push a value onto the top of the stack or pop the value currently at the top off of the stack. We can also check whether the stack is currently empty.
Our procedure starts with an empty stack and reads tokens one by one from the statement expressing the module rule. When it reads a module name it pushes a 0 onto the stack if the student has selected the module and pushes a 1 onto the stack if the student has not. When it reads a ¬ it pops a value from the top of the stack and pushes 1 minus that value onto the stack. When it reads an ∧ it pops two values off of the stack and pushes their maximum onto the stack. When it reads an ∨ it pops two values off of the stack and pushes their minimum onto the stack. After reading all the tokens there is one value on the stack. The student’s choices comply with the rule if and only if that value is 0.
Here is the statement “Probability Statistics ∧ Algebra Geometry ∧ ∨” decorated with the state of the stack after reading each token, if the student has selected “Statistics” and “Algebra” but no other modules. To make things compact the stack is written horizontally, with the left hand side being the “top”.
Probability 1 Statistics 0 1 ∧ 1 Algebra 0 1 Geometry 1 0 1 ∧ 1 1 ∨ 1The final value is 1, meaning the selection does not comply with the rule.
If you’ve been wondering what the counter in our recogniser for the postfix language represented you now have an answer: it’s the size of the stack. The contents of the stack depend on the individual student’s module choices but its size doesn’t.
One minor comment is that this module selection checker is using 0 and 1 as substitutes for the Boolean values “true” and “false”, in that order. With this convention “and” corresponds to a maximum and “or” to a minimum. Using 0 for “true” and 1 for “false” might seem odd but it has the advantage that ∧ corresponds to a maximum and ∨ to a minimum, which is easy to remember because the arrow pointing upward means that we take the higher of the two numbers and the arrow pointing downwards means we take the lower one. Of course it would have been possible to use the reverse convention, with 0 for “false” and 1 for “true”, with relatively minor modifications to the algorithm.
You could write a similar checker for the prefix version of the language but it would have to read tokens in reverse order.