Howdy ,..
Mikaa has created this nice prog for solving binary expression it is by
CC licence.
to compile :
cc -c -lm expressions.cpp -o bexpr
g++ bexpr
/****************************************************************
* Expressions.
*
* This programm calculates boolean expressions.
* Any englsih character stands for variable. Variables are
* case-insensetive.
* '+' stands for 'OR'
* '*' stands for 'AND'
* '!' (postfix) stands for unary 'NOT'
* To get results type '='.
* Max. variable count for now is 26.
*
* Programm reads expression and parses it into a binary tree
* of operations. Recursive descendant method is used for it.
* If syntax is Ok, it prints boolean operation table for
* expression, if not, then error message is printed.
*
* When a tree is ready, programm tries all combinations
* of variables values, evaluates expression for
* every combination and prints results.
*
* Well, the code is structed very bad for now, but it works. If
* you have suggestions, or if you found a bug -- please, let me
* know by mail ([EMAIL PROTECTED]) or by ICQ (231914268).
*
* Hope, you will find the programm usefull.
* WBR, Mikae.
*****************************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define MAX_VARIABLE_COUNT 26
#define EOE '=' //End Of Expression
enum SYNTAX_STATUS
{
SYNTAX_STATUS_ERR_NO_PARENTH,
SYNTAX_STATUS_ERR_PARENTH,
SYNTAX_STATUS_ERR_OP,
SYNTAX_STATUS_ERR_VAR,
SYNTAX_STATUS_ERR_MEM,
SYNTAX_STATUS_ERR_VAR_EXCEED,
SYNTAX_STATUS_OK,
SYNTAX_STATUS_DONE
};
enum NODE_TYPE
{
NODE_TYPE_OPERAND,
NODE_TYPE_OR,
NODE_TYPE_AND,
NODE_TYPE_NOT
};
struct NODE
{
NODE *right;
NODE *left;
char name;
NODE_TYPE type;
};
struct VARIABLE
{
char name;
int value;
};
/*********************
* Variables.
**********************
*/
int vars_count;
VARIABLE vars[MAX_VARIABLE_COUNT];
void init_vars()
{
vars_count = 0;
}
//Looks for name in array of variables. If name not found
// checks, whether it is possible to add new variable or not.
// If variable was successfully added returns true, else returns false.
int insert_variable(char name)
{
int found = 0, res = 1;
for (int i = 0; i < vars_count; i++)
if (vars[i].name == name)
{
found = 1;
break;
}
if (!found)
{
if (vars_count < MAX_VARIABLE_COUNT)
{
vars[vars_count].name = name;
vars[vars_count].value = 0;
vars_count++;
}
else
res = 0;
}
return res;
}
//Looks for name in array of variables. If found returns its value,
// else prints information about exception and returns 0.
int get_var_value(char name)
{
int res = 0;
int found = 0;
for (int i = 0; i < vars_count; i++)
if (vars[i].name == name)
{
res = vars[i].value;
found = 1;
break;
}
if (!found)
printf("DBG: Exception: name not found.\n");
return res;
}
int comparator(const void *p1, const void *p2)
{
return ((VARIABLE *)p1) ->name > ((VARIABLE *)p2) ->name;
}
//Sorts variables in the array by name. Not sure that I need it.
void sort_variables()
{
qsort(vars, vars_count, sizeof(VARIABLE), comparator);
}
void print_vars_names()
{
for (int i = 0; i < vars_count; i++)
printf("%c ", vars[i].name);
}
//Just prints names of variables using space as delimeter.
void print_vars_values()
{
for (int i = 0; i < vars_count; i++)
printf("%i ", (vars[i].value != 0) ? 1 : 0);
}
/******************
* Work with trees.
*******************
*/
NODE *create_leaf(char name, NODE_TYPE type)
{
NODE *res = (NODE *)malloc(sizeof(NODE));
if (res != NULL)
{
res ->name = name;
res ->type = type;
res ->left = NULL;
res ->right = NULL;
}
return res;
}
NODE *create_node(char name, NODE_TYPE type, NODE *left, NODE *right)
{
NODE *node;
node = create_leaf(name, type);
if (node)
{
node ->left = left;
node ->right = right;
}
return node;
}
//Just prints tree considering node's priorites. Returns length of
// printed chars.
int print_tree(NODE *root)
{
int ct = 0;
if (root ->left)
{
if ((root ->left ->type != NODE_TYPE_OPERAND) &&
(root ->type > root ->left ->type)
)
ct += printf("(");
ct += print_tree(root ->left);
if ((root ->left ->type != NODE_TYPE_OPERAND) &&
(root ->type > root ->left ->type)
)
ct += printf("\b) ") - 2;
}
ct += printf("%c ", root ->name);
if (root ->right)
{
if ((root ->right ->type != NODE_TYPE_OPERAND) &&
(root ->type > root ->right ->type)
)
ct += printf("(");
ct += print_tree(root ->right);
if ((root ->right ->type != NODE_TYPE_OPERAND) &&
(root ->type > root ->right ->type)
)
ct += printf("\b) ") - 2;
}
return ct;
}
//Evaluates tree using current set of variables values.
int evaluate_tree(NODE *root)
{
int right, left, res;
if (root ->right)
right = evaluate_tree(root ->right);
if (root ->left)
left = evaluate_tree(root ->left);
switch (root ->type)
{
case NODE_TYPE_OPERAND:
res = get_var_value(root ->name);
break;
case NODE_TYPE_AND:
res = left && right;
break;
case NODE_TYPE_OR:
res = left || right;
break;
case NODE_TYPE_NOT:
res = !left;
break;
default:
printf("DBG: Exception: unsupported node type.\n");
break;
}
return res;
}
//Frees memory allocated for nodes.
void destroy_tree(NODE *root)
{
if (root)
{
if (root ->right)
destroy_tree(root ->right);
if (root ->left)
destroy_tree(root ->left);
free(root);
}
}
/************************
* Kinda lexem analyzator.
*************************
*/
char get_lexem()
{
char c;
while (isspace(c = getchar()))
;
return c;
}
/**********************************
* Functions for expression parsing.
***********************************
*/
//The following four functions build expression tree recursively.
// 'parse_or' function starts parsing.
//
// char *lexem [in]: next lexem for parsing.
// NODE *root [out]: root of tree of parsed expression
// SYNTAX_STATUS *status [out]: status of syntax analyzing.
// Is equal to SYNTAX_STATUS_DONE if
// everything Ok.
NODE *parse_or(char *lexem, SYNTAX_STATUS *status);
NODE *parse_var(char *lexem, SYNTAX_STATUS *status)
{
NODE *node = NULL;
if (*lexem == '\0')
*lexem = get_lexem();
if (!isalpha(*lexem))
{
switch (*lexem)
{
case '(':
*lexem = get_lexem();
node = parse_or(lexem, status);
if (*status == SYNTAX_STATUS_ERR_PARENTH)
{
*status = SYNTAX_STATUS_OK;
*lexem = get_lexem();
}
else if ((*status == SYNTAX_STATUS_DONE) || (*status ==
SYNTAX_STATUS_OK))
*status = SYNTAX_STATUS_ERR_NO_PARENTH;
break;
case EOE:
*status = SYNTAX_STATUS_DONE;
break;
default:
*status = SYNTAX_STATUS_ERR_VAR;
node = NULL;
break;
}
}
else
{
char name = toupper(*lexem);
node = create_leaf(name, NODE_TYPE_OPERAND);
if (!node)
*status = SYNTAX_STATUS_ERR_MEM;
else if (!insert_variable(name))
*status = SYNTAX_STATUS_ERR_VAR_EXCEED;
*lexem = get_lexem();
}
return node;
}
NODE *parse_not(char *lexem, SYNTAX_STATUS *status)
{
NODE *left = NULL, *node;
left = parse_var(lexem, status);
if (*status == SYNTAX_STATUS_OK)
{
while ((*lexem == '!') && (*status == SYNTAX_STATUS_OK))
{
node = create_node(*lexem, NODE_TYPE_NOT, left, NULL);
if (node)
left = node;
else
*status = SYNTAX_STATUS_ERR_MEM;
*lexem = get_lexem();
}
}
return left;
}
NODE *parse_and(char *lexem, SYNTAX_STATUS *status)
{
NODE *left = NULL;
NODE *right;
NODE *node;
char operation;
int run = 1;
left = parse_not(lexem, status);
if (*status != SYNTAX_STATUS_OK)
run = 0;
operation = *lexem;
while (run)
switch (operation)
{
case '*':
*lexem = '\0';
right = parse_not(lexem, status);
if (*status == SYNTAX_STATUS_OK)
{
node = create_node(operation, NODE_TYPE_AND,
left, right);
if (node)
left = node;
else
{
*status = SYNTAX_STATUS_ERR_MEM;
run = 0;
}
}
else
run = 0;
operation = *lexem;
break;
default:
run = 0;
break;
}
return left;
}
NODE *parse_or(char *lexem, SYNTAX_STATUS *status)
{
NODE *left = NULL;
NODE *right;
NODE *node;
char operation;
int run = 1;
left = parse_and(lexem, status);
if (*status != SYNTAX_STATUS_OK)
run = 0;
operation = *lexem;
while (run)
switch (operation)
{
case '+':
*lexem = '\0';
right = parse_and(lexem, status);
if (*status == SYNTAX_STATUS_OK)
{
node = create_node(operation, NODE_TYPE_OR,
left, right);
if (node)
left = node;
else
{
*status = SYNTAX_STATUS_ERR_MEM;
run = 0;
}
}
else
run = 0;
operation = *lexem;
break;
case ')':
*status = SYNTAX_STATUS_ERR_PARENTH;
run = 0;
break;
default:
*status = SYNTAX_STATUS_ERR_OP;
run = 0;
break;
case EOE:
*status = SYNTAX_STATUS_DONE;
run = 0;
break;
}
return left;
}
/**********************
* Kinda error handling.
***********************
*/
//Just prints error description by error number.
void print_error(SYNTAX_STATUS status)
{
char *err_str;
switch (status)
{
case SYNTAX_STATUS_ERR_PARENTH:
err_str = "Unexpected ')'";
break;
case SYNTAX_STATUS_ERR_NO_PARENTH:
err_str = "Unmatched '('";
break;
case SYNTAX_STATUS_ERR_OP:
err_str = "Expected operator";
break;
case SYNTAX_STATUS_ERR_VAR:
err_str = "Expected variable";
break;
case SYNTAX_STATUS_ERR_MEM:
err_str = "Not enough memory";
break;
case SYNTAX_STATUS_ERR_VAR_EXCEED:
err_str = "Sorry, count of variables (26 for this version)
exceeded";
break;
default:
err_str = "DBG: Exception: Unknown error type";
break;
}
printf("Error: %s.\n\n", err_str);
}
//Runs over all combinations of variables values,
// evaluating every set.
void evaluate(NODE *root)
{
int v, p;
p = (int)pow(2, vars_count);
for (int i = p - 1; i >= 0; i--)
{
for (int j = 0; j < vars_count; j++)
{
v = p >> 1;
v >>= j;
vars[j].value = i & v;
}
print_vars_values();
printf(" %i", (evaluate_tree(root) != 0) ? 1 : 0);
printf("\n");
}
}
void print_line(int len)
{
for (int i = 0; i < len; i++)
printf("-");
}
void usage()
{
printf("Any englsih character stands for variable.\n"
"'+' stands for 'OR'\n"
"'*' stands for 'AND'\n"
"'!' (postfixed) stands for unary 'NOT'\n"
"For quit press CTRL+Z (Windows) or CTRL+D (Unix).\n\n"
"If you found a bug -- please, let me know ([EMAIL
PROTECTED]).\n\n\n"
);
}
int main(int argc, char **argv)
{
NODE *root;
SYNTAX_STATUS status;
char lexem;
int len;
usage();
printf("Enter expression. Type '=' to get results.\n\n");
while ((lexem = get_lexem()) != EOF)
{
init_vars();
status = SYNTAX_STATUS_OK;
root = parse_or(&lexem, &status);
if (status != SYNTAX_STATUS_DONE)
{
print_error(status);
destroy_tree(root);
//remove trailing characters
while (getchar() != '\n')
;
}
else
{
if (root)
{
len = 0;
len += printf("Parsed expression: ");
len += print_tree(root);
printf("\n");
print_line(len);
printf("\n");
print_vars_names(); printf(" Result:");
printf("\n");
evaluate(root);
printf("\n");
destroy_tree(root);
}
}
printf("Enter expression. Type '=' to get results.\n\n");
}
return 0;
}
