Description

יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה הנוכחית נלמד ״שיטה פולנית״ לכתיבת ביטויים אריתמטיים ונממש אותה בעזרת עץ בינאריהנקרא עץ ביטוי.
תיאור:
הגדרה 1: שיטתinfix
בדרך כלל, נהוג לכתוב ביטוי אריתמטי בצורה הנקראתinfix form :
num op num כאשר
–num מספר
–op פעולה (+,-,*,/)למשל, הביטוים הבאים הם ביטוייinfix :
((31 * 1) + (21 / ))2
((1 + 3) * (6 – 4))
הגדרה 2: שיטתprefix
כתיב פולני (שיטתprefix ) הוא שיטה שפותחה על ידי הלוגיקן הפולני יאן לוקשביץ בשנת 1920. שיטה זובאה לפצות על מספר חסרונות של שיטת הכתיב הנפוצהinfix :
● הצורך להגדיר כללי קדימות אופרטורים.
● הצורך בשימוש בסוגריים.
העיקרון המנחה של הכתיב הפולני הוא כתיבת הפעולה (האופרטור) לפני האופרנדים (המספרים) שעליהםהוא פועל. לדוגמה2 12 +במקום2( + 12)שיטה זו איננה בשימוש בלוגיקה כיום, אך בשל העובדה שקל לנתח ביטוי בכתיב פולני באמצעות מחשב,נעשה בה שימוש במספר שפות תכנות, בעיקר בשפות תכנות מבוססות מחסנית כמו פוסטסקריפט.
דוגמאות:
Infix expression Prefix expression
(2 + )3 + 2 3
(4 * )6 * 4 6
((2 + 3) * (4 * ))6 * + 2 3 * 4 6
((1 + 3) * (6 – ))4 * + 1 3 – 6 4
(((1 + 3) * (6 – 4)) + ((9 – 7) * ))8 + * + 1 3 – 6 4 * – 9 7 8
הגדרה 3: עץ ביטוי
נוח להציג את הביטויים האריתמטיים בעזרת עצים בינאריים. עצים כאלה נקראים עצי ביטוי.
למשל, עבור לביטוי ((4 – 6) * (3 + 1)) מתאים העץ:

אלגוריתם ליצירת עץ ביטוי:
נניח כי נתון ביטוי אריתמטי בצורתprefix . נעבור על הביטוי משמאל לימין וניצור עץ ביטוי באופן הבא:

דוגמא:
נדגים איך האלגוריתם המתואר לעיל עובד על הביטוי: 4 6 – 3 1 + *

1) כתבו מחלקה גנרית בשםBinaryTree המממשת עץ בינארי.
המחלקה צריכה לממש את המנשק הנתון >BinaryTreeI<T. (המנשק נתון בגיטהב, ראה הוראותלהלן).
הבנאים צריכים לאפשר יצירת עלה (בנאי עם פרמטר אחד מטיפוסT ), ויצירת צומת פנימי (בנאיעם שלשה פרמטרים לפי הסדר הבא: פרמטר מטיפוסT , רפרנס לתת-עץ של בן שמאלי, ורפרנסלתת-עץ של בן ימני).
המחלקות כולן צריכות להיות בחבילהil.ac.telhai.ds.trees ;
2) כתבו מחלקה גנרית המרחיבה את הנ”ל וממשת עץ בינארי מלא. (בעץ בינארי מלא לכל צומתשהוא לא עלה שני ילדים בדיוק).
שם המחלקה הוא >FullBinaryTree<T, והיא נמצאת באותה החבילה.
package il.ac.telhai.ds.trees;
public class FullBinaryTree<T> extends BinaryTree<T> {
… }
הוסיפו שני בנאים בדומה לאלו שכתבתם ב 1).
3) כתבו מחלקה המרחיבה את >FullBinaryTree<T, ומממשת עץ ביטוי. (הוסיפו בנאים לתבניתהבאה).
package il.ac.telhai.ds.trees; import java.io.IOException; import java.io.StreamTokenizer; public class ExpressionTree extends FullBinaryTree<String>{
/*
* Read the stream tokenizer until EOF and construct* the expression tree corresponding to it.
* The input contains a prefix expression.
*/
public static ExpressionTree createTree(StreamTokenizer tokenizer) throws IOException {
}
/*
* Returns the infix expression corresponding to the current tree (*)
*/
public String infix() { }
/*
* Returns the prefix expression corresponding to the current tree (*)
*/
public String prefix() { }
/*
* Evaluates the expression corresponding to the current tree * and returns its value
*/
public double evaluate() {
}
}
(*) פורמט הפלט צריך להיות כך:עבורinfix : הרווחים הקיימים הם רק לפני אופרטור ולאחריו (רווח אחד לפני ורווח אחד אחרי).למשל: “(3 * (1 + 2))”
עבורprefix : נקבל את המחרוזת עם שני רווחים בין כל זוג איברים ברשימה, וכן רווח אחדבהתחלה ורווח אחד בסוף. למשל: ” 3 1 2 + * “יש להשתמש במתודותinorder ו-preOrder למימוש המתודותinfix ו-prefix, בהתאמה.4) הריצו את התוכניתPrePolishToInfix הנתונה לכם, ובדקו את התוצאות. שימו לב כי הקלט
.preOrder הוא בצורתPrePolishToInfix-ל
סדר העבודה ופרטים טכניים
: בקישורGITHUB מתוךDS-Lab06-ExpressionTree שליפת הפרויקט●
https://github.com/michalHorovitz/DSLab2021-2022Public
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדות הקודמות יש לבצע שליפהמחדש.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
■ עכבר ימני
Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab06_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם כאשר הם נמצאים בתיקייה
il/ac/telhai/ds/treesכלומר, השורש של קובץ ההגשה יכיל רק תיקייה בשםil .
ומכיל את כל קבצי -java . להמחשה תמונה של קובץ כזה שנפתח ב -WindowsExplorer

בדיקת קובץ ההגשה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
חשוב!!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשהייפסל בגלל פורמט הגשה שגוי וכו.’ דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה.
היות ואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד.’
הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלובחומרה