biểu thức số học trong cây xử lý như thế nào?

[duongtulang]

Một biểu thức số học được lưu trong cây biểu thức, hãy thực hiện:
a) Mô tả cấu trúc cây biểu thức
b) Đếm số phép toán trong cây biểu thức
c) Đếm số toán hạng trong cây biểu thức

----Ý CỦA EM LÀ----
câu a)
Các toán hạng thì khai báo kiểu int, con các phét toán '+', '-', '*', '/', '%'
thì mình phải khai báo như thế nào vậy các anh
Duyệt cây theo LNR thi:
b) Đếm số phép toán trong cây biểu thức là đếm số nút trong của cây
c) Đếm số toán hạng trong cây biểu thức là đếm số nút lá của cây

Ý em như vậy có đúng không mấy anh chị?
em đang gặp rắc rối là không biết khai báo các phép toán như thế nào. Nhờ các anh chị giúp em.
Xin cám on nhiều.

[sieuphuong]

Các toán hạng thì khai báo kiểu int, con các phét toán '+', '-', '*', '/', '%'
thì mình phải khai báo như thế nào vậy các anh

Mình nghĩ khai báo kiểu char thôi . Và theo mình không hẳn nút trong nào cũng là toán hạng và nút lá nào cũng là toán tử . Để đếm cậu có thể duyệt và so sánh cho chính xác . Ko rõ có phương pháp nào hay hơn không mong mọi người giúp sức .

[rox_rook]

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

#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&not(num2)));
                        else if(prt->data == "#")
                          num = (not(num1)&num2)|(num1&not(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

#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

[Ada]

Một biểu thức số học được lưu trong cây biểu thức, hãy thực hiện:
a) Mô tả cấu trúc cây biểu thức
b) Đếm số phép toán trong cây biểu thức
c) Đếm số toán hạng trong cây biểu thức

----Ý CỦA EM LÀ----
câu a)
Các toán hạng thì khai báo kiểu int, con các phét toán '+', '-', '*', '/', '%'
thì mình phải khai báo như thế nào vậy các anh

Theo như đề mà suy ra, mình nghĩ bạn không cần phải quan tâm đến cái cây đâu. Hãy coi như cái cây đã được khai báo rồi. Bạn chỉ viết code để hiển thị nó ra thôi.

Duyệt cây theo LNR thi:
b) Đếm số phép toán trong cây biểu thức là đếm số nút trong của cây
c) Đếm số toán hạng trong cây biểu thức là đếm số nút lá của cây

Ý em như vậy có đúng không mấy anh chị?

Đúng.

[kidkid]

Kid nghĩ rằng nếu có câu a
Mô tả cấu trúc cây biểu thức
Thì dĩ nhiên phải mô tả cả cây biểu thức rồi .

[huydaibang]

[QUOTE=rox_rook;29560]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

#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&not(num2)));
                        else if(prt->data == "#")
                          num = (not(num1)&num2)|(num1&not(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 

đoạn code của ông vissual C++ nó báo lỗi "expected unqualified-id before "!"token" ở dòng 14:int not(int num).ông có hiểu lỗi đó là gì không?Đây là code cho chuơng trình nào vậy?

[hoanglinhkd]

Một biểu thức số học được lưu trong cây biểu thức, hãy thực hiện:
a) Mô tả cấu trúc cây biểu thức
b) Đếm số phép toán trong cây biểu thức
c) Đếm số toán hạng trong cây biểu thức

----Ý CỦA EM LÀ----
câu a)
Các toán hạng thì khai báo kiểu int, con các phét toán '+', '-', '*', '/', '%'
thì mình phải khai báo như thế nào vậy các anh
Duyệt cây theo LNR thi:
b) Đếm số phép toán trong cây biểu thức là đếm số nút trong của cây
c) Đếm số toán hạng trong cây biểu thức là đếm số nút lá của cây

Ý em như vậy có đúng không mấy anh chị?
em đang gặp rắc rối là không biết khai báo các phép toán như thế nào. Nhờ các anh chị giúp em.
Xin cám on nhiều.

trả lời :
a, mình cũng nghĩ là khai báo kiểu char cho cả toán hạng và toán tử.
b, số phép toán là số node, mà không phải là node lá (tức là số toán tử).
c, cái này thì là số node lá rùi (vì là toán tử thì nó phải có con)

bạn chỉ cần đếm các node, nếu ko là lá thì là toán tử.
còn đếm lá thì dễ rùi

bạn hỉu rùi chứ.

[hoanglinhkd]

[QUOTE=huydaibang;153974]

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

#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&not(num2)));
                        else if(prt->data == "#")
                          num = (not(num1)&num2)|(num1&not(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 

đoạn code của ông vissual C++ nó báo lỗi "expected unqualified-id before "!"token" ở dòng 14:int not(int num).ông có hiểu lỗi đó là gì không?Đây là code cho chuơng trình nào vậy?

đoạn code trên không chạy cũng ko sao.
nhưng mình thấy nó đúng rùi đó. chủ topic nên tham khảo rùi tự viết.
các hàm kiểm tra ký tự có là toán hạng, toán tử... mình chỉ xem sơ qua thấy đúng rùi. hi vọng bạn sẽ tự code được . nhưng quan trọng là bạn phải hiểu cấu trúc của nó, chứ cài đặt chỉ là hình thức thui.

[hungenter]

troi gi ma dai the