====== درخت عبارت ======

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

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


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

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

<code cpp 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);
}
</code>

<code cpp 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 << ")";
}
</code>

<code cpp 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();
}
</code>
===== ساختن درخت عبارت =====
درخت عبارت را از روی هر سه نمایش می‌توان در زمان خطی و صرفاً با یک بار پیمایش عبارت تشکیل داد. به این عملیات، **تجزیه عبارت** هم می‌گویند.

  * از روی نمایش پیش‌ترتیب: ساده‌ترین نمایش برای تشکیل درخت عبارت نمایش پیش‌ترتیب است. هر بار که یک عنصر از ورودی می خوانیم، اگر عملگر بود، بسته به تعداد عملوندهای‌ش بازگشتی تابع را صدا می‌زنیم تا زیر عبارت‌های مطلوب را تجزیه کنیم.
<code cpp 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); //یک راس برگ با محتویات داده شده می‌سازد
}
</code>

  * از روی نمایش پس‌ترتیب: یک پشته در نظر می‌گیریم و اگر یک عملوند از ورودی خواندیم، آن را به پشته اضافه می‌کنیم و اگر با یک عملگر مواجه شدیم، به تعداد عملوندهای‌ش از انتهای پشته بر‌می‌داریم و حاصل عملیات را به پشته می‌افزاییم.
<code cpp 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();
}
</code>
  * از روی نمایش میان‌ترتیب: اگر بخواهیم شرط خطی بودن زمان اجرا و تنها یک بار پیمایش عبارت را نگاه داریم، تجزیه‌ی عبارت میان‌ترتیب، دشواری بیش‌تری دارد. البته در حالت‌های خاص (مثلاً اگر عبارت، کاملاً پرانتزگذاری شده باشد) کار ساده‌تر است. اما در حالت کلی باید گرامر زبان را تحلیل کرد و مبتنی بر آن تجزیه عبارت را پیاده‌سازی کرد. در کد زیر، تابع $readE()$ عبارتی شامل اعداد، متغیرها، و عملگرهای: جمع، تفریق، ضرب، تقسیم، توان و پرانتز را تجزیه می‌کند:
<code cpp 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;
}

</code>