درخت عبارت

برای تجزیه، محاسبه و نمایش یک عبارت ریاضی (جبری، بولی، جبر مجوعه‌ها و …) شامل ثابت‌ها، متغیرها و عملگرهای یک‌عملونده (قرینه، قدر مطلق، نقیض و …) و دو عملونده (اشتراک، تقسیم و …) می توان از یک درخت دودویی بهره برد که به آن درخت عبارت می‌گویند. البته برای عبارت‌هایی که عملگرهایی با بیش از دو عملوند دارند هم می‌توان درخت عبارت تشکیل داد؛ اما به ندرت چنین عملوندهایی استفاده می‌شوند و درخت حاصل دیگر دودویی نخواهد بود.

برگ های درخت، بیانگر عملوندها (ثابت‌ها و متغیرها) هستند و هر رأس غیر برگ، یک عملگر را نشان می‌دهد. در زیر یک عبارت و درخت متناظر با آن نشان داده‌ شده است:

درخت عبارت را می‌توان به سه شکل پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب پیمایش کرد که به ترتیب نمایش پیشوندی، میانوندی و پسوندی یک عبارت را تولید می‌کنند.

هر کدام از نمایش‌ها استفاده‌های خود را دارند. نکته‌ی جالب درباره‌ی نمایش پیش‌ترتیب و پس‌ترتیب این است که نیازی به پرانتزگذاری ندارند و بدون ابهام تفسیر می‌شوند. اما در نمایش میان‌ترتیب، پرانتزگذاری نیاز است و برای پرهیز از گذاشتن پرانتزهای اضافه، مهم است که اولویت و از چپ یا راست اجرا شدن عملگر های هم‌اولویت را بدانیم. طریقه‌ی تولید هر سه نمایش را در زیر آورده‌ایم:

prefix_print.cpp

void prefix_print(node *cur) { // + * + a b c 7
    cur-> print();
    if (cur-> l)
        prefix_print(cur-> l);
    if (cur-> r)
        prefix_print(cur-> r);
}

infix_print.cpp

void infix_print(node *cur, bool p = false) { // (a + b) * c + 7
    if (p)
        cout << "(";
    int pr = prio[cur-> opr]; 
    if (cur-> l) {
        int lo = prio[cur-> l-> opr];
        infix_print(cur-> l, lo < pr || (lo == pr && asso[cur-> opr] == 'r'));
    }
    cur-> print();
    if (cur-> r) {
        int ro = prio[cur-> r-> opr];
        infix_print(cur-> r, ro < pr || (ro == pr && asso[cur-> opr] == 'l'));
    }
    if (p)
        cout << ")";
}

postfix_print.cpp

void postfix_print(node *cur) { // a b + c * 7 +
    if (cur-> l)
        postfix_print(cur-> l);
    if (cur-> r)
        postfix_print(cur-> r);
    cur-> print();
}

درخت عبارت را از روی هر سه نمایش می‌توان در زمان خطی و صرفاً با یک بار پیمایش عبارت تشکیل داد. به این عملیات، تجزیه عبارت هم می‌گویند.

• از روی نمایش پیش‌ترتیب: ساده‌ترین نمایش برای تشکیل درخت عبارت نمایش پیش‌ترتیب است. هر بار که یک عنصر از ورودی می خوانیم، اگر عملگر بود، بسته به تعداد عملوندهای‌ش بازگشتی تابع را صدا می‌زنیم تا زیر عبارت‌های مطلوب را تجزیه کنیم.

prefix_read.cpp

node *prefix_read() {
    string token;
    cin >> token;
    if (is_opr(token)) {
        node *cur = new node(token);
        if (hasl[token])
            cur-> l = prefix_read();
        if (hasr[token])
            cur-> r = prefix_read();
        return cur;
    }
    return leaf(token); //یک راس برگ با محتویات داده شده می‌سازد
}

• از روی نمایش پس‌ترتیب: یک پشته در نظر می‌گیریم و اگر یک عملوند از ورودی خواندیم، آن را به پشته اضافه می‌کنیم و اگر با یک عملگر مواجه شدیم، به تعداد عملوندهای‌ش از انتهای پشته بر‌می‌داریم و حاصل عملیات را به پشته می‌افزاییم.

postfix_read.cpp

node *postfix_read() {
    vector<node*> v;
    string token;
    while (cin >> token) {
        string s = token;
        node *cur;
        if (is_opr(s)) {
            cur = new node(s);
            if (hasr[s]) { // اگر عملگر، عملوند راست داشت
                cur-> r = v.back();
                v.pop_back();
            }
            if (hasl[s]) { // اگر عملگر، عملوند چپ داشت
                cur-> l = v.back();
                v.pop_back();
            }
        }
        else
            cur = leaf(s);
        v.push_back(cur);
    }
    return v.back();
}

• از روی نمایش میان‌ترتیب: اگر بخواهیم شرط خطی بودن زمان اجرا و تنها یک بار پیمایش عبارت را نگاه داریم، تجزیه‌ی عبارت میان‌ترتیب، دشواری بیش‌تری دارد. البته در حالت‌های خاص (مثلاً اگر عبارت، کاملاً پرانتزگذاری شده باشد) کار ساده‌تر است. اما در حالت کلی باید گرامر زبان را تحلیل کرد و مبتنی بر آن تجزیه عبارت را پیاده‌سازی کرد. در کد زیر، تابع $readE()$ عبارتی شامل اعداد، متغیرها، و عملگرهای: جمع، تفریق، ضرب، تقسیم، توان و پرانتز را تجزیه می‌کند:

infix_read.cpp

string advance() {
    string s = token;
    if (!(cin >> token))
        token = "$";
    return s;
}
node *readE();
node *readP() {
    if (token == "(") {
        advance();
        node *cur = readE();
        advance();
        return cur;
    }
    return leaf(advance());
}
node *readF() {
    node *cur = readP();
    if (token == "^")
        cur = new node(advance(), cur, readP());
    return cur;
}
node *readT() {
    node *cur = readF();
    while (prio[token] == prio["*"])
        cur = new node(advance(), cur, readF());
    return cur;
}
node *readE() {
    node *cur = readT();
    while (prio[token] == prio["+"])
        cur = new node(advance(), cur, readT());
    return cur;
}