473,320 Members | 2,035 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Algorithm required.

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
Nov 14 '05 #1
5 1484

On Sun, 5 Dec 2004, Steve Lambert wrote:

I realise this might not be the correct group for this post so maybe you
could redirect me accordingly.
comp.programming is for algorithmic questions.
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.


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("Whoops! 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
Nov 14 '05 #2
In article <Pi**********************************@unix47.andre w.cmu.edu>
Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> wrote:
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];
};


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_subexprs[0] /* assuming array */
#define e_rhs e_un.un_subexprs.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.
Nov 14 '05 #3
Chris Torek wrote:
Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> wrote:
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];
};


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_subexprs[0] /* assuming array */
#define e_rhs e_un.un_subexprs.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.


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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #4

"Steve Lambert" <st***********@ntlworld.com> wrote in message
news:zp*****************@newsfe4-win.ntli.net...
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.


Get a copy of "The Dragon Book".

Aho, Sethi, Ullmann : Compilers. Principles, Techniques, and Tools.
Addison-Wesley, 1997. (the Dragonbook).
Nov 14 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit...
1
by: git_cs | last post by:
Hey , guys and gals do any of you have the DES algorithm in C/C++ language. I would be happy if any of you could give the source code. I studied the algorithm, and have written a C language...
12
by: No Such Luck | last post by:
Hi All: I'm not sure if this is the right place to ask this question, but I couldn't find a more appropriate group. This is more of a theory question regarding an algorithm implemented in C, not...
2
by: ben | last post by:
hello, i'm following an algorithm book and am stuck on an early excersise in it, not because of the c programming side of it or even the algorithm side of it, i don't think, but because of maths....
113
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same...
4
by: Hunk | last post by:
Hi I have a binary file which contains records sorted by Identifiers which are strings. The Identifiers are stored in ascending order. I would have to write a routine to give the record given...
22
by: Jia Lu | last post by:
Hi all. I want to create a large list like: aaaa ~ zzzz Is there any good algorithm to do this? Thanx Jia Lu
3
by: gomsi | last post by:
hi, i have a paragraph where i have to insert <markand </marktags to highlight the required words.i am implementing it in c++ i am currently doing it as follows.. i take the corresponding...
1
by: almurph | last post by:
Hi everyone, Concerning the Needleman-Wunsch algorithm (cf. http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have noticed a possible loop. Inside the algorithm there is an...
2
by: shashankbs | last post by:
Given a topology and a certain node X, find the shortest path tree with X as the root. * Input: a topology file similar to the following (which is a three-node ring) ...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.