עץ ביטוי בוליאני – בגרות 2015 במדעי המחשב – שאלה 1 (899205)

השאלה מבקשת לחשב ערך של עץ בוליאני, שבו בכל צומת (node) פנימית (כלומר שאיננה עלה) מוגדרת פעולה בוליאנית באמצעות string (כלומר הערך "AND" או הערך "OR").
בסעיף ב' אנחנו מתבקשים לכתוב פעולה שתקבל עץ בוליאני כזה, ותחזיר את ערכו, כלומר תחזיר טיפוס בוליאני אמיתי בשפה (bool בשפת C#, או boolean בשפת Java), ולא string.
כדי לחשב את ערכו של כל העץ, צריך לסרוק ולחשב את הביטוי בכל חלקי העץ. ניתן לעשות זאת באמצעות סריקה לעומק (depth first search) שאותה מממשים באמצעות רקורסיה.
ניסוח השאלה "חוסך" לנו מספר בדיקות.
הנה מה שנתון בשאלה:

  • בכל עלה כתוב "F" או "T". כלומר, אין עלים שכתוב בהם משהו אחר.
  • "בכל צומת שאיננו עלה"..כתוב "AND" או "OR".
  • "לכל צומת שאיננו עלה יש שני בנים"

כלומר, אם קראתי "AND" או "OR" אז בוודאות אינני עלה, ובוודאות יש לי שני בנים.
אם קראתי "T" או "F" אז בוודאות אני עלה ! (שהרי בכל צומת שאיננו עלה רשום "AND" או "OR")
נשאר רק לבדוק שהעץ שקיבלנו (כולו!) איננו ריק.

להלן הקוד:

 


כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *