boolean expression checker/matcher

Discussion in 'C++' started by sunil, Aug 27, 2008.

  1. sunil

    sunil Guest

    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
    sunil, Aug 27, 2008
    #1
    1. Advertising

  2. sunil

    kwikius Guest

    On Aug 27, 10:31 pm, sunil <> wrote:
    > 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
    kwikius, Aug 28, 2008
    #2
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roedy Green

    Re: java.util.regex.Matcher

    Roedy Green, Jul 30, 2003, in forum: Java
    Replies:
    0
    Views:
    360
    Roedy Green
    Jul 30, 2003
  2. J Leonard
    Replies:
    4
    Views:
    12,598
    Mark Space
    Jan 19, 2008
  3. Pager O Rama

    MSN BLOCK CHECKER-MSN STATUS CHECKER-MSN PROBLEMS

    Pager O Rama, Apr 4, 2006, in forum: ASP General
    Replies:
    0
    Views:
    212
    Pager O Rama
    Apr 4, 2006
  4. Jacob Grover
    Replies:
    5
    Views:
    299
    Jacob Grover
    Jul 18, 2008
  5. Metre Meter
    Replies:
    7
    Views:
    350
    Metre Meter
    Aug 6, 2010
Loading...

Share This Page