binary integer logic

[p_eqlz_np]

I have a question I am hoping someone here can help me with. let's say we have a bunch of atomic groups (cannot be broken down further), i will give each of them a bit mask. we also have a bunch of users, and each one has a binary value that tells us which atomic groups the user is in. Example:

Groups
G1 - 00001 - (1)
G2 - 00010 - (2)
G3 - 00100 - (4)
G4 - 01000 - ( 8 )
G5 - 10000 - (16)

Users
U1 - 00011 - User is in groups 1 and 2
U2 - 01100 - in groups 3 and 4
U3 - 00010 - in group 2
U4 - 10000 - in group 5
U5 - 01011 - in groups 1, 2, 4

Now we also have groups of groups which are composed of some basic formula. For Example:

Groups of Groups
GG1 - (G1 && G2) || G3
GG2 - (G2 || G3) && (G1 && G4)
GG3 - (G1 && (G2 || G3)) || G5

Now I want to be able to determine all the users that satisfy the conditions for GG1, GG2 and GG3. So based on the above examples, we have:

Users in GG1: U1, U2, U5
Users in GG2: U5
Users in GG3: U1, U4, U5

How can I algorithmically determine this? The groups, users and groups of groups are stored as you see above. Given a user's binary value I need to be able to "plug" it into the GG formula and determine if it is true or not. Do I have to break apart the GG formulas and dynamically map them into if statements? I am hoping for an easier way since they could possibly get complicated.

Thanks for any help.

[iamthwee]

I have a question I am hoping someone here can help me with. let's say we have a bunch of atomic groups (cannot be broken down further), i will give each of them a bit mask. we also have a bunch of users, and each one has a binary value that tells us which atomic groups the user is in. Example:

Groups
G1 - 00001 - (1)
G2 - 00010 - (2)
G3 - 00100 - (4)
G4 - 01000 - ( 8 )
G5 - 10000 - (16)

Users
U1 - 00011 - User is in groups 1 and 2
U2 - 01100 - in groups 3 and 4
U3 - 00010 - in group 2
U4 - 10000 - in group 5
U5 - 01011 - in groups 1, 2, 4

Now we also have groups of groups which are composed of some basic formula. For Example:

Groups of Groups
GG1 - (G1 && G2) || G3
GG2 - (G2 || G3) && (G1 && G4)
GG3 - (G1 && (G2 || G3)) || G5

Now I want to be able to determine all the users that satisfy the conditions for GG1, GG2 and GG3. So based on the above examples, we have:

Users in GG1: U1, U2, U5
Users in GG2: U5
Users in GG3: U1, U4, U5

How can I algorithmically determine this? The groups, users and groups of groups are stored as you see above. Given a user's binary value I need to be able to "plug" it into the GG formula and determine if it is true or not. Do I have to break apart the GG formulas and dynamically map them into if statements? I am hoping for an easier way since they could possibly get complicated.

Thanks for any help.

It would appear you need a way for your program to automatically evalute each equation, i.e apply the rules of boolean mathematics, taking into account where the parentheses are and so on.

Thus, you would prolly need to build an equation parser to handle boolean expressions. Once you have that built that the rest should be as trivial as plugging in the variables.

[Jafet]

Will this interface be open to a casual user? Then you may need to handle full-blown parenthesized expressions; otherwise you could just use stacks and evaluate using RPN. You'll need to pass in all expressions in postfix notation, though.

Could you provide more context? As in, WHY you want to do this? What is the END GOAL? Those could help a lot in accurately diagnosing your problem.

[p_eqlz_np]

thanks for the input guys.

i have been working on writing a parser since this morning. i defined a simple context-free grammar that defines the language of these expressions. having the cfg, it was pretty easy to write a simple syntax checker which just checks an expression and tells you if it is valid or not. i have not written the actual parser yet.

i am using a recursive descent parsing algorithm and plan on building an abstract syntax tree to evaluate the expression. i came across RPN while reading up on this stuff but didnt look too deeply into it. would you suggest RPN is a better choice than a recursive descent algorithm?

as for why i need to do this, it is simply for user-group permissions just like in the example. the expressions will be built by some admin user and these expressions need to be evaluated when checking if a user is in the high level group or not.

[Lord Soth]

Hi,

Recursive Descent is fine or you can simply use pre-fix or post-fix notation and use a stack to push intermediate values at each paranthesis and pop at anti-paranthesis. If you just need this for an application (not as an assignement or academic thing) then you can use the built-in parametric expression evaluator which is in .Net Framework or JScript evaluator COM object.

Loren Soth

[p_eqlz_np]

Hi,

Recursive Descent is fine or you can simply use pre-fix or post-fix notation and use a stack to push intermediate values at each paranthesis and pop at anti-paranthesis. If you just need this for an application (not as an assignement or academic thing) then you can use the built-in parametric expression evaluator which is in .Net Framework or JScript evaluator COM object.

Loren Soth

which method (recursive descent or pre/post fix notation with stacks) is cheaper and more efficient? as for the application, it is in perl on a unix system so I cant use windows stuff

[Jafet]

Well, seeing as your inputs aren't anything fancy (as in, with more than a couple hundred possibly parenthesized, nested operands) the focus should be on implementing this easily, elegantly and securely. Due to the relatively small expected size of the inputs, you shouldn't worry about efficiency too much. But converting infix notation to postfix notation for evaluation RPN-style is rather fast (using a "shunting yard" algorithm, read it up) and is rather easy to implement. The rules and operators are also extensible.

[p_eqlz_np]

Well, seeing as your inputs aren't anything fancy (as in, with more than a couple hundred possibly parenthesized, nested operands) the focus should be on implementing this easily, elegantly and securely. Due to the relatively small expected size of the inputs, you shouldn't worry about efficiency too much. But converting infix notation to postfix notation for evaluation RPN-style is rather fast (using a "shunting yard" algorithm, read it up) and is rather easy to implement. The rules and operators are also extensible.

yeah, what i have actually been doing so far is implementing the shunting yard algorithm.

[Lord Soth]

Hi,

If the platform is Perl then why not use eval ? See https://www.linuxnotes.net/perlcd/advprog/ch05_01.htm

Loren Soth

[p_eqlz_np]

Hi,

If the platform is Perl then why not use eval ? See https://www.linuxnotes.net/perlcd/advprog/ch05_01.htm

Loren Soth

ouch.. perl eval's on strings are horribly inefficient.. that's the last thing i want to be doing here since i need this to be as fast as possible.

[p_eqlz_np]

Hi,

If the platform is Perl then why not use eval ? See https://www.linuxnotes.net/perlcd/advprog/ch05_01.htm

Loren Soth

well, after doing some benchmarking, it turns out eval is nowhere as bad as i expected in this case. i guess it's because the eval expressions are just simple boolean formulas. i guess i wasted all that time writing an infix to rpn converter and evaluator.. oh well, at least i learned some stuff.