Algorithm required.

[Steve Lambert]

Hi Guys,

I realise this might not be the correct group for this post so maybe you
could redirect me accordingly. I have a coding requirement for which I
suspect a standard algorithm exists. I need to be able to evaluate a
general, bracketed boolean expression eg ( (A and B) OR (C and D) and (E or
F or G)) etc. Any ideas where I might be able to find appropriate
information.

Cheers

Steve

[Arthur J. O'Dwyer]

Re: Algorithm required.


On Sun, 5 Dec 2004, Steve Lambert wrote:[color=blue]
>
> I realise this might not be the correct group for this post so maybe you
> could redirect me accordingly.[/color]

comp.programmin g is for algorithmic questions.
[color=blue]
> I have a coding requirement for which I
> suspect a standard algorithm exists. I need to be able to evaluate a
> general, bracketed boolean expression eg ( (A and B) OR (C and D) and (E or
> F or G)) etc. Any ideas where I might be able to find appropriate
> information.[/color]

The general problem is called "parsing," and you can do it using a stack
in one pass, or you can build an intermediate data structure to hold the
"essence" of the formula until you're ready to solve it (e.g., if you're
going to be solving a system of equations this way).
ObOnTopic:

struct expr {
enum {ANDexp, ORexp, ATOM} type;
/* If it is a secondary expression... */
struct expr *lhs, *rhs;
/* If it is an atom... */
char varname[10];
};

[...]

int eval(struct expr *f) {
/* Evaluate a formula. */
switch (f->type) {
case ANDexp: return eval(f->lhs) && eval(f->rhs);
case ORexp: return eval(f->lhs) || eval(f->rhs);
case ATOM: return lookup_value(f->varname);
default: do_error("Whoop s! I have a bug!");
}
}

The code for actually reading the input and building the 'expr' data
structure is left as an exercise for the reader with more free time this
morning. ;)

-Arthur

[Chris Torek]

Re: Algorithm required.

In article <Pine.LNX.4.6 0-041.04120511293 30.2985@unix47. andrew.cmu.edu>
Arthur J. O'Dwyer <ajo@nospam.and rew.cmu.edu> wrote:[color=blue]
> ObOnTopic:
>
> struct expr {
> enum {ANDexp, ORexp, ATOM} type;
> /* If it is a secondary expression... */
> struct expr *lhs, *rhs;
> /* If it is an atom... */
> char varname[10];
> };[/color]

I think it is worth pointing out that this is one of those rare
places where a union makes sense even in strictly conforming C
code. :-) An "and" or "or" expression needs *just* the lhs and
rhs, while an "atom" expression needs *just* the varname -- so
why store all three in every kind of "expr" node? This gives
something like:

struct expr {
enum expr_type e_type;
union {
struct {
struct expr *sub_lhs, *sub_rhs;
} un_subexprs;
char un_varname[10];
} e_un;
};

Note that, in this case, the union and sub-struct types have no
tags (because none is really needed). The sub-struct is required
so that the lhs and rhs are in fact separate variables -- but if
you wanted to get rid of it, you could use an array instead:

struct expr {
enum expr_type e_type;
union {
struct expr *un_subexprs[2];
char un_varname[10];
} e_un;
};

and use un_subexprs[0] as the LHS and un_subexprs[1] as the RHS.

Unfortunately, there is no way to get rid of the separate union
member. I sometimes wish that C99 had adopted "anonymous" sub-
struct/union from one of the many dialects that have them (such
as Plan 9 C). As it is, you might choose to write:

#define e_varname e_un.un_varname

and/or:

#define e_lhs e_un.un_subexpr s[0] /* assuming array */
#define e_rhs e_un.un_subexpr s.sub_rhs /* assuming struct */

so that you can pretend C has anonymous sub-elements, even though
it does not. Note that this #define trick works only if the
struct-member "pseudo-names" (here e_varname, e_lhs, and e_rhs)
are not used as ordinary variable names, and tend not to work in
(for instance) debuggers.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[CBFalconer]

Re: Algorithm required.

Chris Torek wrote:[color=blue]
> Arthur J. O'Dwyer <ajo@nospam.and rew.cmu.edu> wrote:
>[color=green]
>> ObOnTopic:
>>
>> struct expr {
>> enum {ANDexp, ORexp, ATOM} type;
>> /* If it is a secondary expression... */
>> struct expr *lhs, *rhs;
>> /* If it is an atom... */
>> char varname[10];
>> };[/color]
>
> I think it is worth pointing out that this is one of those rare
> places where a union makes sense even in strictly conforming C
> code. :-) An "and" or "or" expression needs *just* the lhs and
> rhs, while an "atom" expression needs *just* the varname -- so
> why store all three in every kind of "expr" node? This gives
> something like:
>
> struct expr {
> enum expr_type e_type;
> union {
> struct {
> struct expr *sub_lhs, *sub_rhs;
> } un_subexprs;
> char un_varname[10];
> } e_un;
> };
>
> Note that, in this case, the union and sub-struct types have no
> tags (because none is really needed). The sub-struct is required
> so that the lhs and rhs are in fact separate variables -- but if
> you wanted to get rid of it, you could use an array instead:
>
> struct expr {
> enum expr_type e_type;
> union {
> struct expr *un_subexprs[2];
> char un_varname[10];
> } e_un;
> };
>
> and use un_subexprs[0] as the LHS and un_subexprs[1] as the RHS.
>
> Unfortunately, there is no way to get rid of the separate union
> member. I sometimes wish that C99 had adopted "anonymous" sub-
> struct/union from one of the many dialects that have them (such
> as Plan 9 C). As it is, you might choose to write:
>
> #define e_varname e_un.un_varname
>
> and/or:
>
> #define e_lhs e_un.un_subexpr s[0] /* assuming array */
> #define e_rhs e_un.un_subexpr s.sub_rhs /* assuming struct */
>
> so that you can pretend C has anonymous sub-elements, even though
> it does not. Note that this #define trick works only if the
> struct-member "pseudo-names" (here e_varname, e_lhs, and e_rhs)
> are not used as ordinary variable names, and tend not to work in
> (for instance) debuggers.[/color]

This is precisely where the better syntax of Pascal records will
shine. I would code that as:

TYPE
exprtype = andexpr, orexpr, atom;
exprptr = ^anexpr;
anexpr = RECORD
CASE etype : exptrtype OF
atom: (atomname : ARRAY[10] OF char);
andexpr,
orexpr: (lhs, rhs : exprptr);
END; (* CASE etype *)
END; (* expr RECORD *)

and future reference is dead simple:

VAR
thisexpr : exprptr;
....
new(thisexpr);
thisexpr^.etype = atom;
thisexpr^.atom = 'whatever ';
....
new(thisexpr);
thisexpr^.etype = orexpr;
thisexpr^.lhs = thatexpr;
thisexpr^.rhs = otherexpr;

and this is also a place where the much maligned WITH statement can
come into play:

new(thisexpr);
WITH thisexptr^ DO BEGIN
etype = orexpr;
lhs = thatexpr;
rhs = otherexptr;
END;

all of which avoids the interminable need for additional field,
union, structure names of pure standard C.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[dandelion]

Re: Algorithm required.


"Steve Lambert" <steve.lambert@ ntlworld.com> wrote in message
news:zpGsd.1991 $Kg4.1145@newsf e4-win.ntli.net...[color=blue]
> Hi Guys,
>
> I realise this might not be the correct group for this post so maybe you
> could redirect me accordingly. I have a coding requirement for which I
> suspect a standard algorithm exists. I need to be able to evaluate a
> general, bracketed boolean expression eg ( (A and B) OR (C and D) and (E[/color]
or[color=blue]
> F or G)) etc. Any ideas where I might be able to find appropriate
> information.[/color]

Get a copy of "The Dragon Book".

Aho, Sethi, Ullmann : Compilers. Principles, Techniques, and Tools.
Addison-Wesley, 1997. (the Dragonbook).

[wtuozyds@search26.com]

Re: Algorithm required.

http://www.ardice.com/Games/Video_Ga...ddison-Wesley/