Boolean search in C

[kenny rullo]

Hello people, I'm a new member of this fantastic community!
I'm a student and i have to solve this puzzle:

I have a string like
"The quick brown fox jumps over the lazy dog" (or longer)

I have to search through this string using boolean operators like
"quick AND brown OR fox"

mantaining the logical order, so "quick AND (brown OR fox)".

(consider that the search string can be longer with n search options).

What's the strategy?

I can recursively tokenize the string by splitting via strtok()? but how to mantain operator precedence?

If anyone can help me or if you know a good solution pointing me to the right way i'll appreciate!
Thanks!
Valerio

[gpraghuram]

Hello people, I'm a new member of this fantastic community!
I'm a student and i have to solve this puzzle:

I have a string like
"The quick brown fox jumps over the lazy dog" (or longer)

I have to search through this string using boolean operators like
"quick AND brown OR fox"

mantaining the logical order, so "quick AND (brown OR fox)".

(consider that the search string can be longer with n search options).

What's the strategy?

I can recursively tokenize the string by splitting via strtok()? but how to mantain operator precedence?

If anyone can help me or if you know a good solution pointing me to the right way i'll appreciate!
Thanks!
Valerio

My idea is, you can tokenize the string and look for words which represents operators like and or etc.
As you encounter the word push it to a separate stack and continue tokenizing.
Finally at the end of iteration you will have all the operators in the stack.
Please add more info and i will try to help u

Raghuram

[kenny rullo]

My idea is, you can tokenize the string and look for words which represents operators like and or etc.
As you encounter the word push it to a separate stack and continue tokenizing.
Finally at the end of iteration you will have all the operators in the stack.
Please add more info and i will try to help u

Raghuram

Raghuram
thanks for the answer. I created my own strategy to solve this:
1) tokenize the search string by spaces
2) eval every token
2.1)if token is AND, OR transform to &, |
2.2)if token is a word, use strstr to find if the token is on the searched string. if token is found, return 1, otherwise 0.
3) at the end of the loop, i have a string like "1&0|1" (one and zero or one).

If you evaluate this, you can know if the search string can return values.

Following the code:

#include <stdio.h>
#include <string.h>

char *converti(char *token, char *campione);

int main(int argc, char *argv[]) {
	char titolo[] = "la vispa teresa correa tra l'erbetta e con un calcio moria la minchietta";
	char ricerca[] = "vispa and jeeg";
	
	char *pch;
	char result[] = "\0";
	pch = strtok(ricerca, " ");
	while(pch != NULL) {
		strcat(result, converti(pch, titolo));
		pch = strtok(NULL, " ");
	}
	printf("%s\n", result);
	return 0;
}

char *converti(char *token, char *campione) {
	if( strcmp(token, "and") == 0 ) 
		return "&";
	else if( strcmp(token, "or") == 0 )
		return "|";
	else
		if( strstr(campione, token) != NULL )
			return "1";
		else
			return "0";
}

Now the computer can evaluate the boolean problem... but, i think that the atoi() function can evaluate and transform, but it evaluate the first integer, not the whole expression. D'OH!

Can you solve this?

[gpraghuram]

Raghuram
thanks for the answer. I created my own strategy to solve this:
1) tokenize the search string by spaces
2) eval every token
2.1)if token is AND, OR transform to &, |
2.2)if token is a word, use strstr to find if the token is on the searched string. if token is found, return 1, otherwise 0.
3) at the end of the loop, i have a string like "1&0|1" (one and zero or one).

If you evaluate this, you can know if the search string can return values.

Following the code:

#include <stdio.h>
#include <string.h>

char *converti(char *token, char *campione);

int main(int argc, char *argv[]) {
	char titolo[] = "la vispa teresa correa tra l'erbetta e con un calcio moria la minchietta";
	char ricerca[] = "vispa and jeeg";
	
	char *pch;
	char result[] = "\0";
	pch = strtok(ricerca, " ");
	while(pch != NULL) {
		strcat(result, converti(pch, titolo));
		pch = strtok(NULL, " ");
	}
	printf("%s\n", result);
	return 0;
}

char *converti(char *token, char *campione) {
	if( strcmp(token, "and") == 0 ) 
		return "&";
	else if( strcmp(token, "or") == 0 )
		return "|";
	else
		if( strstr(campione, token) != NULL )
			return "1";
		else
			return "0";
}

Now the computer can evaluate the boolean problem... but, i think that the atoi() function can evaluate and transform, but it evaluate the first integer, not the whole expression. D'OH!

Can you solve this?

There is a issue in the code
You are doing a array overwrite here
[code=c]
char result[] = "\0"; //The size of the array is 1
pch = strtok(ricerca, " ");
while(pch != NULL) {
strcat(result, converti(pch, titolo)); //This causes array
//overwrite
pch = strtok(NULL, " ");
}

[/code]
Try to use dynamic allocation for the variable result
atoi converts the ascii string to a number is the ascii string contains a number

Raghuram