پرسش: یک درخت دودویی داده می شود که یک عبارت ریاضی را به این صورت نشان می دهد: هر گره یک عملگر یا یک مقدار است. عملگر روی حاصل زیر درخت چپ و راست عمل می کند. برنامه ای بنویسید که حاصل عبارت ریاضی مرتبط با درخت دودویی را محاسبه نماید.
پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم که آن را درست درک کرده ایم. فرض کنیم که درخت عبارت ریاضی شکل زیر را داریم. این درخت معادل عبارت ریاضی (9-2) * 4 می باشد.
ریشه این درخت عملگر * (ضرب) می باشد. این به آن معناست که حاصل نهایی این عبارت شامل حاصل ضرب زیر درخت چپ (یعنی 4) در حاصل زیر درخت سمت راست می باشد. بنابراین قبل از آنکه بتوانیم حاصل ضرب را حساب کنیم به دانستن حاصل زیر درخت سمت راست نیاز داریم. ریشه زیر درخت سمت راست عملگر - (تفریق) می باشد به این معنا که حاصل این زیر درخت برابر با تفریق زیر درخت های سمت چپ و راست آن (یعنی 2 و 9) خواهد بود. بنابراین حاصل این زیر درخت 2 - 9 = 7- می باشد. با توجه به اینکه اکنون حاصل زیر درخت سمت راست ریشه را داریم می توانیم عملگر ضرب را اعمال نموده و با حاصل نهایی 4*(7-) = 28- می رسیم.
این روش بدست آوردن حاصل مربوط به عبارت ریاضی درخت پیشنهاد می کند که ما از یک الگوریتم بازگشتی برای پاسخ به مساله استفاده نماییم: برای بدست آوردن مقدار هر زیر درخت در صورتی که ریشه ی زیر درخت یک عملگر باشد باید ابتدا حاصل زیر درخت سمت چپ و سپس زیر درخت سمت راست آن را بصورت بازگشتی محاسبه کنیم. آنگاه عملگر ریشه را روی حاصل زیر درخت چپ و راست اجرا کنیم. در صورتی که مقدار ریشه زیر درخت یک عدد باشد، حاصل آن خود مقدار عددی است.
برای اطمینان از درستی این الگوریتم، آن را روی درخت مثال فوق اجرا می کنیم.
۱- محاسبه مقدار برای ریشه درخت
مشاهده ریشه (عملگر *)
۱.۱ - محاسبه مقدار زیر درخت سمت چپ
مشاهده مقدار 4 به عنوان ریشه. چون یک عملگر نیست خود مقدار 4 حاصل است.
۲.۱ - محاسبه مقدار زیر درخت سمت راست
مشاهده ریشه زیر درخت (عملگر -)
۱.۲.۱- محاسبه زیر درخت سمت چپ
مشاهده مقدار 2 به عنوان ریشه و برگرداندن آن به عنوان حاصل
۲.۲.۱- محاسبه زیر درخت سمت راست
مشاهده مقدار 9 به عنوان ریشه و برگرداندن آن به عنوان حاصل
اعمال عملگر - روی حاصل زیر درخت چپ (2) و زیر درخت راست (9) و برگرداندن 7-
اعمال عملگر * روی حاصل زیر درخت چپ (4) و زیر درخت راست (7-) و برگرداندن 28-
بنابر این اجرای الگوریتم روی درخت مثال پاسخ درست را تولید می کند.
سپس شروع به نوشتن برنامه می کنیم. چند خط اول برنامه (خط 1 تا 5) تعریف ساختار گره های درخت است. گره یک کلاس ساده است که دارای چند فیلد data برای نگهداری مقدار گره، left اشاره گری به زیر درخت چپ، و right اشاره گری به زیر درخت راست می باشد.
سپس قسمت الگوریتمی برنامه شروع می شود. ابتدا نام و پارامتر مناسب برای تابع تعریف می کنیم (خط 7). در ابتدای تابع چک می کنیم که آیا ریشه مقداری تهی است. در این صورت مقدار 0 را بر می گرداند (خط 8 و 9). این کار بخصوص در مواجهه با عملگر تکی منها مفید می باشد.
سپس یک دیکشنری از عملگرها تعریف می کنیم. مقدار مربوط به هر عنصر دیکشنری یک تابع است که دو پارامتر می گیرد و عملگر را روی آنها اعمال و حاصل را برمی گرداند (خط 11 تا 14). از این تکنیک به عنوان جایگزینی برای ساختار شرطی متوالی مورد نیاز و تکرار کد مشابه استفاده می کنیم.
دو خط آخر برنامه (در واقع یک خط که به دلیل طولانی بودن شکسته شده است) بسیار فشرده است و فراخوانی های بازگشتی در آن انجام می دهیم. این کد بینهایت زیباست.
در هر بازگشت ریشه یک زیر درخت وارسی می کنیم. اگر مقدار ریشه عملگر (یکی از مقادیر +، -، *، /) نباشد خود مقدار برمی گردانیم. در غیر این صورت حاصل زیر درخت چپ و سپس راست با فراخوانی بازگشتی محاسبه می کنیم و آنگاه عملگر روی آنها برای محاسبه حاصل اعمال می شود (خط 15 و 16).
در خط 11 در برنامه فوق از یک دیکشنری استفاده شده است. مقدار مربوط به هر کلید در دیکشنری یک تابع lambda است که در واقع امکان تعریف توابع یک خطی را می دهد. توابعی که اینجا تعریف کردیم دو پارامتر می گیرند و حاصلی را محاسبه می کنند.
بدلیل استفاده از این ساختار دیکشنری، دیگر نیازی به استفاده از شرطهای پی در پی برای فراخوانی تابع وجود ندارد. در ضمن برنامه بسیار قابل توسعه است و اگر عملگر جدیدی به عملگرهای محاسباتی درخت اضافه شود تنها کافی است یک خط به دیکشنری اضافه شود.
