Về cấu trúc dữ liệu mà học tới cây nhị phần thì cũng rắc rối rùi, nói giảng thì chắc không ai dám giảng hết phần này được, cài đặt nó cũng khá rắc rối. Mình có source sưu tầm về nó đây, bạn chịu khó đọc đỡ nhé, còn cái cây Binary của mình bữa h viết vẫn chưa xong T_T (vô học lại rùi hic hic). Bạn chịu khó nghiên cứu nhé :
logical.h
PHP Code:
#ifndef _LOGICAL_H_
#define _LOGICAL_H_
#include <iostream>
#include <string>
#include <math.h>
#include <sstream>
#include <iostream>
#include <stack>
using namespace std;
//negacion de num
int not(int num) {
if(num == 1) num = 0;
else num = 1;
return num;
}
// Overloaded function, checks a string for an operator
bool IsOperator(string mystring)
{
if(mystring == "#" || mystring == ">" || mystring == "|" || mystring == "<" || mystring == "&" || mystring == "!")
return(true);
else
return(false);
}
// Overloaded function, checks a character for an operator
bool IsOperator(char ops)
{
if(ops == '#' || ops == '|' || ops == '>' || ops == '&' || ops == '<' || ops == '!' || ops == '(' || ops == ')')
return(true);
else
return(false);
}
bool IsOperand(char ch) //Checks for character to be an operand
{
if (ch == '0' || ch == '1')
return true;
else
return false;
}
//Binary Tree Definition and Implementation
class node_type
{
public:
string data;
node_type *left_child;
node_type *right_child;
node_type(string k)
{
data=k;
left_child = NULL;
right_child = NULL;
}
};
class binary_tree
{
public:
node_type *root;
void print(node_type *r); // Postfix traversal
binary_tree(void) { root = NULL;}
void print(void) {print (root);}
void evaluate()
{
evaluate(root);
}
void evaluate(node_type* prt) //recursive tree evaluation
{
//if it's a binary operator and both sons are leafs
if((IsOperator(prt->data) && prt->data != "!" && !IsOperator(prt->left_child->data) && !IsOperator(prt->right_child->data)))
{
int num = 0;
int num1 = atoi(prt->left_child->data.c_str());
int num2 = atoi(prt->right_child->data.c_str());
if(prt->data == "|")
num = num1 | num2;
else if(prt->data == ">")
num = not(not(num2)&num1);
else if(prt->data == "&")
num = num1 & num2;
else if(prt->data == "<")
num = not((not(num1)&num2)|(num1¬(num2)));
else if(prt->data == "#")
num = (not(num1)&num2)|(num1¬(num2));
stringstream bob;
bob << num;
string suzzy(bob.str());
prt->data = suzzy;
prt->left_child = NULL;
prt->right_child = NULL;
}
//if we have a unary operator (!) we must evaluate the following part of the tree beggining
//from the right child of that node
else if(prt->data == "!" && prt->left_child == NULL && prt->right_child != NULL) {
evaluate(prt->right_child);
int num = not(atoi(prt->right_child->data.c_str()));
stringstream bob;
bob << num;
string suzzy(bob.str());
prt->data = suzzy;
prt->left_child = NULL;
prt->right_child = NULL;
}
//if a leaf, do nothing
else if(prt->left_child == NULL && prt->right_child == NULL);
else
{
evaluate(prt->left_child);
evaluate(prt->right_child);
evaluate(prt);
}
}
//still not working ok, why?
void clear_help(node_type* rt) // destructor
{
if( rt != NULL )
{
clear_help( rt->left_child);
clear_help( rt->right_child);
delete rt;
}
}
void clear()
{
clear_help(root);
}
};
//Checks Precedence, returns true of: A is higher precendence over B
bool TakesPrecedence(char OperatorA, char OperatorB)
{
if (OperatorA == '(') return false;
if (OperatorB == '(') return false;
if (OperatorB == ')') return true;
if ((OperatorA == '!') && (OperatorB == '!')) return false;
if (OperatorA == '!') return true;
if (OperatorB == '!') return false;
return true;
}
node_type *build_node(string x) //build a new node for the tree
{
node_type *new_node;
new_node = new node_type(x);
return(new_node);
}
void binary_tree::print(node_type *p) //postfix traversal
{
if(p != NULL)
{
print(p->left_child);
print(p->right_child);
cout << p->data << " ";
}
}
//Creates a copy of a tree passes the roots of the 2
// trees, r1 being the root of the tree to be copied to
// and r2 being the root of the tree being copied.
void copy(node_type *&r1, node_type *r2)
{
if(r2 == NULL)
r1 = NULL;
else
{
r1 = build_node(r2->data);
copy(r1->left_child, r2->left_child);
copy(r1->right_child, r2->right_child);
}
}
/*********** Checks if expression is ok **********/
bool isok(string exp)
{
char check;
int error=0;
int lb=0;
int rb=0;
//will check every character in the string
for(unsigned int m=0;m < exp.size(); m++)
{
check = exp[m];
if(IsOperand(check))
{
//if after an operand there's a left bracket
if(exp[m+1] == '(')
error++;
else if(IsOperand(exp[m+1]))
error++;
else if(exp[m+1] == '!')
error++;
}
else if(IsOperator(check))
{
if(check == ')')
{
rb++;
if(exp[m+1]=='#' || exp[m+1]=='|' || exp[m+1]=='>' || exp[m+1]=='&' || exp[m+1]=='<' || exp[m+1]==')')
{
//if it's the last character of the string
if(m+2 == exp.size()) //if it ends the string
error++;
m++;
if(exp[m] == ')')
rb++;
}
else if(IsOperand(exp[m+1]))
error++;
else if(IsOperator(exp[m+1]))//si es '('
error++;
}
else if(check == '(')
{
lb++;
if(exp[m+1] =='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]) && exp[m+1] != '!')
error++;
}
else //if it's >,<,!,|,#, or &
{
//if it's the last character of the string
if(m+1 == exp.size()) //if it ends the string
error++;
//if it's the first one and not a "not"
else if(m == 0 && check != '!')
error++;
else if(exp[m+1] == '(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]) && exp[m+1] != '!')
error++;
}
}
else //when it's not an operator nor an operand
error++;
}
if(error == 0 && lb==rb)
return(true);
else
return(false);
}
/*******************************************/
char logic(string infix) {
binary_tree etree;
stack<binary_tree> NodeStack;
stack<char> OpStack;
char c;
string tempstring;
binary_tree temp;
binary_tree temp_tree;
string thisstring="";
for(unsigned int i=0;i<infix.size();i++) {
c = infix[i];
if(IsOperand(c)) {//if operand, create tree and push into NodeStack
tempstring = "";
tempstring = tempstring + c;
temp.root = build_node(tempstring);
NodeStack.push(temp);
}
//Else if Operator, check precedence and push into OpStack
else if(c == '#' || c == '|' || c == '>' || c == '&' || c == '<' || c == '!') {
if(OpStack.empty()) OpStack.push(c);
else if(OpStack.top() == '(') OpStack.push(c);
else if(TakesPrecedence(c, OpStack.top())) OpStack.push(c);
else {
while(!OpStack.empty() && TakesPrecedence(OpStack.top(), c)){
thisstring="";
thisstring = thisstring + OpStack.top();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
//must evaluate different if !
if(OpStack.top() != '!') {
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
}
else etree.root->left_child = NULL;
OpStack.pop();
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
etree.root = NULL;
}
OpStack.push(c);
}
}
else if(c == '(') OpStack.push(c);//a bracket process begins
else if(c == ')') {//bracket process ends
while(OpStack.top() != '(') {
//will evaluate everything that's inside a pair
//of brackets
thisstring="";
thisstring = thisstring + OpStack.top();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
if(OpStack.top() != '!') {
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
}
else etree.root->left_child = NULL;
OpStack.pop();
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
etree.root = NULL;
}
OpStack.pop();
}
} // end of for loop
if(OpStack.empty()) { //in case we only had an operand in our string
copy(etree.root,NodeStack.top().root);
NodeStack.pop();
}
else while(!OpStack.empty()) {//While OpStack not empty, pop that stack and create tree
thisstring="";
thisstring = thisstring + OpStack.top();
etree.root = build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child = temp_tree.root;
temp_tree.root = NULL;
if(OpStack.top() != '!') {
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child = temp_tree.root;
NodeStack.pop();
temp_tree.root = NULL;
}
else etree.root->left_child = NULL;
OpStack.pop();
copy(temp_tree.root, etree.root);
NodeStack.push(temp_tree);
if(!OpStack.empty()) {
etree.root = NULL;
}
}
etree.evaluate();//do we have to be geniuses?
return etree.root->data[0]; //now the result is in the root of the tree
} //end of function
#endif
main
PHP Code:
#include <condefs.h>
#include <math.h>
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include "logical.h"
char dalevalor(char * vector, char * var, char variable) {
unsigned int i=0,f=0;
while(i<strlen(var) && f == 0) {
if(var[i] == variable) f = 1;
else i++;
}
if(f==1) return vector[i];
else return variable;
}
void cambiaexp(char * original, char * destino, char * vector, char * var) {
unsigned int i;
for(i=0;i<=strlen(original);i++) {
if(!IsOperator(original[i])) destino[i] = dalevalor(vector,var,original[i]);
else destino[i] = original[i];
}
}
void rotate(char * vector, int mov, int tam) {
int i,j;
if(mov>tam) mov = tam;
for(i=0;i<mov;i++) {
for(j=tam;j>=1;j--){
vector[j] = vector[j-1];
vector[j-1] = '0';
}
}
vector[tam] = '\0';
}
int cuentavar(char * original) {
unsigned int i,max=0;
for(i=0;i<strlen(original);i++) {
if(original[i] == 'p' && max < 1) max = 1;
if(original[i] == 'q' && max < 2) max = 2;
if(original[i] == 'r' && max < 3) max = 3;
if(original[i] == 's' && max < 4) max = 4;
}
return max;
}
int main() {
char original[30];
char evaluable[30];
char o;
string infix = "";
char matriz[16][5];
char variables[] = {"pqrs"};
int i,j,maxX,maxY;
char temp[5];
do {
cout<<"Inserta la expresion logica a evaluar: ";
cin>>original;
cout<<"--------------------------------------"<<endl;
cout<<"Expresion a evaluar : ";
cout<<original<<endl;
cout<<"--------------------------------------"<<endl;
maxX = cuentavar(original);//we must see how many variables we are using
maxY = pow(2,maxX);//and amount of expressions to evaluate
for(i=0;i<maxX;i++) cout<<variables[i];
cout<<" | Expresion"<<endl;
cout<<"--------------------------------------"<<endl;
//we need to fill the matrix with the right values
for(i=0;i<maxY;i++) {
itoa(i,temp,2);
rotate(temp,maxX-(strlen(temp)),maxX);
for(j=0;j<maxX;j++) {
matriz[i][j] = temp[j];
}
matriz[i][j] = '\0';
}
//the two following lines will give us an example expression in
//order to evaluate it and know it's ok
cambiaexp(&original[0],&evaluable[0],matriz[0],variables);
infix = evaluable;
if(!isok(infix)) {
cout<<"**************************************"<<endl;
cout<<" Expresion incorrecta"<<endl;
cout<<"**************************************"<<endl;
cout<<" & igual a AND"<<endl;
cout<<" | igual a OR"<<endl;
cout<<" # igual a XOR"<<endl;
cout<<" ! igual a NOT"<<endl;
cout<<" > igual a implicacion"<<endl;
cout<<" < igual a doble implicacion"<<endl;
cout<<"**************************************"<<endl;
}
else {
for(i=0;i<maxY;i++) {
cambiaexp(&original[0],&evaluable[0],matriz[i],variables);
infix = evaluable;
cout<<matriz[i]<<" | "<<infix<<" resulta en "<<logic(infix)<<endl;
}
cout<<"--------------------------------------"<<endl;
}
cout<<"Desea insertar otra expresion (S/N)? ";
cin>>o;
o = toupper(o);
cout<<endl;
} while(o == 'S');
}
Không biết phải cái bạn tìm không, đọc cũng oải quá T_T