boolean expression checker/matcher

S

sunil

Hello,
I have a boolean expression thats specified in pre/in/post fix
notations, lets assume infix for the sake of this argument. The
expression can be in any of the following forms:
Form A:
-------------
(As1&&/||Bs1&&/||Cs1 )|| (As2&&/||Bs2&&/||Cs2)||....(Asn&&/||Bsn&&/||
Csn) with following rules:
-Inner ANDs/ORs are optional but if they are specified in one nesting
they must be specified in all nestings with same connector type across
all.
-Each boolean variable is identified by two attributes ex: As1: A is
the condition while s1 is the data on which the condition is operating
(this data could be like instance of same class), so As1 could be
interpreted as
attribute X of Class s1 > 100
so the list of possible legal expansions for this (for n=2) is:
(As1&&Bs1&&Cs1)||(As2&&Bs2&&Cs2).....
(As1||Bs1||Cs1)||(As2||Bs2||Cs2)
(As1&&Bs1) || (As2&&Bs2)....
(As1||Bs1) || (As2||Bs2)...
As1&&As2....
As1 || As2...
Form B:
------------
(As1&&/||Bs1)&&(Cs2&&/||Ds2)&&(Es3&&/||Fs3) this has slightly
different rules:
-Inner AND/ORs are optional and if they are specified for one nesting
they need not be specified for another nesting.
-Each boolean variable is identified as before by two attributes:
As1, A:condition s1: data on which condition operates
-max # nestings limited to 3
-max # variables in each nesting is limited to 2
because of rule1, the # of legal expansions is now a lot
so list of possible combinations would include:
-All AND/OR cases:
(As1&&Bs1)&&(Cs2&&Ds2)&&(Es3&&Fs3)
(As1||Bs1)&&(Cs2||Ds2)&&(Es3||Fs3)
-One OR (2 AND) case:
(As1||Bs1)&&(Cs2&&Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2||Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2&&Ds2)&&(Es3||Fs3)
-Two OR (1 AND) cases:
(As1||Bs1)&&(Cs2||Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2||Ds2)&&(Es3||Fs3)
(As1||Bs1)&&(Cs2&&Ds2)&&(Es3||Fs3)
-Partial :
-All AND/OR: (inner)
(As1&&Bs1)&&(Cs2&&Ds2)
(As1||Bs1)&&(Cs2||Ds2)
As1&&Cs2
As1&&Cs2&&Es3
-partial some AND,some OR:
(As1||Bs1)&&(As2&&Bs2)
(AS1&&Bs1)&&(As2||Bs1)
(As1||Bs1)&&(As2||Bs2)
(As1||Bs1)&&As2
(As1&&Bs1)&&As2
As1&&(As2&&Bs2)
As1&&(As2||Bs2)
(As1||Bs1)&&Cs2&&(Es3&&Fs4)
(As1||Bs1)&&Cs2&&(Es3||Fs4)
As1&&Cs2&&(Es3&&Fs4)
(AS1||BS1)&&Cs2&&Es3........ (list may not be complete)
I want to write a C++ program which would take in an expression in one
of the forms: pre/in/post fix forms and would try to check if it
matches one of these forms, the program should tell whats the form
type(A/B) and the expression it has matched with. Whats the best way
to tackle this?

Also the program should be able to handle conversions, example if user
specifies: (As1&&As2)||(As1&&Bs2) it should convert it As1&&(As2||Bs2)
which is a supported form. If user specifies an expression thats not
supported it should specify how to break this down into minimal #
groupings: ex:As1||As2||Cs2 would be broken down as (As1||As2)||Cs2.
As1||As2 is supported expression... (this could also be broken down as
As1||(As2||Cs2), it would be enough for it to report one form of
expression)
Thanks in advance,
Sunil
 
K

kwikius

Hello,
I have a boolean expression thats specified in pre/in/post fix
notations, lets assume infix for the sake of this argument. The
expression can be in any of the following forms:
Form A:
-------------
(As1&&/||Bs1&&/||Cs1 )|| (As2&&/||Bs2&&/||Cs2)||....(Asn&&/||Bsn&&/||
Csn) with following rules:
-Inner ANDs/ORs are optional but if they are specified in one nesting
they must be specified in all nestings with same connector type across
all.
-Each boolean variable is identified by two attributes ex: As1: A is
the condition while s1 is the data on which the condition is operating
(this data could be like instance of same class), so As1 could be
interpreted as
attribute X of Class s1 > 100
so the list of possible legal expansions for this (for n=2) is:
(As1&&Bs1&&Cs1)||(As2&&Bs2&&Cs2).....
(As1||Bs1||Cs1)||(As2||Bs2||Cs2)
(As1&&Bs1) || (As2&&Bs2)....
(As1||Bs1) || (As2||Bs2)...
As1&&As2....
As1 || As2...
Form B:
------------
(As1&&/||Bs1)&&(Cs2&&/||Ds2)&&(Es3&&/||Fs3) this has slightly
different rules:
-Inner AND/ORs are optional and if they are specified for one nesting
they need not be specified for another nesting.
-Each boolean variable is identified as before by two attributes:
As1, A:condition s1: data on which condition operates
-max # nestings limited to 3
-max # variables in each nesting is limited to 2
because of rule1, the # of legal expansions is now a lot
so list of possible combinations would include:
-All AND/OR cases:
(As1&&Bs1)&&(Cs2&&Ds2)&&(Es3&&Fs3)
(As1||Bs1)&&(Cs2||Ds2)&&(Es3||Fs3)
-One OR (2 AND) case:
(As1||Bs1)&&(Cs2&&Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2||Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2&&Ds2)&&(Es3||Fs3)
-Two OR (1 AND) cases:
(As1||Bs1)&&(Cs2||Ds2)&&(Es3&&Fs3)
(As1&&Bs1)&&(Cs2||Ds2)&&(Es3||Fs3)
(As1||Bs1)&&(Cs2&&Ds2)&&(Es3||Fs3)
-Partial :
-All AND/OR: (inner)
(As1&&Bs1)&&(Cs2&&Ds2)
(As1||Bs1)&&(Cs2||Ds2)
As1&&Cs2
As1&&Cs2&&Es3
-partial some AND,some OR:
(As1||Bs1)&&(As2&&Bs2)
(AS1&&Bs1)&&(As2||Bs1)
(As1||Bs1)&&(As2||Bs2)
(As1||Bs1)&&As2
(As1&&Bs1)&&As2
As1&&(As2&&Bs2)
As1&&(As2||Bs2)
(As1||Bs1)&&Cs2&&(Es3&&Fs4)
(As1||Bs1)&&Cs2&&(Es3||Fs4)
As1&&Cs2&&(Es3&&Fs4)
(AS1||BS1)&&Cs2&&Es3........ (list may not be complete)
I want to write a C++ program which would take in an expression in one
of the forms: pre/in/post fix forms and would try to check if it
matches one of these forms, the program should tell whats the form
type(A/B) and the expression it has matched with. Whats the best way
to tackle this?

Its not really a C++ issue. Really its about grammar.

For a vulgar American slang parser , try bison.

For a more sophisticated inclusive multicultural parser (niceley
beyond reach of the americans) try slk.

regards
Andy Little
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top