30/09/2018, 16:02

Cần giúp đỡ: sửa lỗi khi chuyển biểu thức inFix sang binary tree expression

Em có làm 1 class Expression trong đó chứa các trường như sau:
string inFix;
string preFix;
string postFix;
node* tree;

Em gặp vấn đề trong method convert_to_tree() từ biểu thức inFix. Em làm theo hướng dẫn ở trang này: http://yinyangit.wordpress.com/2011/01/28/algorithm-tạo-va-su-dung-cay-biểu-thức-expression-tree/

và đây là link down file em làm: http://www.mediafire.com/download/1hcqx51879zp14d/Expression+C++.rar

Mọi người ai rãnh thì xem hộ em với ạ! Em xin cảm ơn!
(Do em làm theo cách em hiểu nên ko có ghi thêm chú thích sau dấu “//”, mọi người không hiểu ý em ở đoạn nào cứ nói để em nêu ý kiến của em)

Gió viết 18:05 ngày 30/09/2018

Giả sử xâu inFix có độ dài lớn. Bạn gọi strlen quá nhiều lần trong Expression là không cần thiết. Việc bạn gọi ...Fix.data() cũng tương tự. Nó sẽ mất thời gian O(n) cho mỗi lần gọi. Bạn có thể goi str.length() chỉ tốn O(1) thôi.

Expression::Expression(const char* source)    {
    inFix.assign(source);
    length_inFix = length_preFix = length_postFix =inFix.length();
    convert_to_postFix();
    convert_to_preFix();
    convert_to_tree();
}

Việc có string postFix rồi thì chuyển sang cây rất đơn giản. Không cần sub_tree hay copy_tree gì cả.

void Expression::convert_to_tree()    {
    
    stack<node*> st;
    for(int i=0;i<postFix.length();++i){
        node * tmp=new node();
        tmp->left=tmp->right=NULL;
        tmp->op=postFix[i];
        if(is_operand(tmp->op)) tmp->value=(float) (tmp->op-'0');
        if(is_operator(postFix[i])){
            
            node *right=st.top();
            st.pop();
            node *left=st.top();
            st.pop();
            tmp->left=left;
            tmp->right=right;
        }
        st.push(tmp);
    }
    tree=st.top();
}

Tôt hơn bạn nên chuyển từ xâu sang {operator,operand,brack}. rồi chuyển sang inFix,preFix sẽ đễ hơn.
Mình nghĩ code của bạn rắc rối ở chỗ chuyển sang cây thôi.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

0 chủ đề

0 bài viết

Tác giả nổi bật