Description

יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה הנוכחית נתרגל את מבנה הנתונים “מחסנית” ונלמד על “כתיב פולני הפוך” של ביטוייםאריתמטיים.
תיאור:
הגדרה 1: שיטתinfix
בדרך כלל, נהוג לכתוב ביטוי אריתמטי בצורה הנקראתinfix form :num op numכאשר
–num מספר
–op פעולה (+,-,*,/)למשל, הביטוים הבאים הם ביטוייinfix :
(31*1) + (21/2)
(1+3) * (6-4)
הגדרה 2: שיטתpostfix העיקרון המנחה של הכתיב הפולני ההפוך הוא כתיבת הפעולה (האופרטור) אחרי האופרנדים (המספרים)שעליהם הוא פועל. לדוגמה+ 2 21במקום2 + 21
דוגמאות נוספות:
Infix expression Postfix expression
2+3 2 3 +
4 * 6.5 4 6.5 *
(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 * +
אלגוריתם שערוך ביטוי:
התחל עם מחסנית ריקהכל עוד יש קלט
– קרא את האסימון הבא בקלט
– אם האסימון הוא מילה (TTWORD) אזי:
– אם המילה היאquit – קריאת הקלט נעצרת (1)
– אחרת הביטוי שגוי (2)
– אחרת אם האסימון הוא מספר, דחוף אותו למחסנית
– אחרת אם האסימון הוא אופרטור (3). אז:
– הוצא את שני הערכים מראש המחסנית (אם אין כאלה, הקלט שגוי (2))
– בצע את הפעולה המתאימה לאופרטור על שני הערכים הנ”ל וחשב את התוצאה.
– דחוף את התוצאה למחסנית.
(בסיום הקלט:)
– אם המחסנית ריקה הביטוי שגוי (2).
– אחרת,
– הוצא את התוצאה מראש המחסנית
– אם המחסנית לא ריקה הביטוי שגוי (2)
(1) על לולאת הקלט לעצור כאשר מתקבלת המילהquit או כאשר מתקבל סימוןEOF .
(2) כאשר הפלט שגוי יש להדפיס הודעה מתאימה ולצאת מהתכנית עם קוד שגיאה – ראו פירוט בשלב 5להלן.
(3) ניתן לקרא מה-tokenizer את התו הבא (עבור האופרטור) ע״י ביצוע השורה הבאה:
char c = (char) tokenizer.ttype
שלבים:
1) הריצו את האלגוריתם הנ”ל “על יבש” עם הביטוי האחרון בטבלה.2) הורידו את הממשק גנריil.ac.telhai.ds.stack.Stack עם השיטותpush, pop, top, isEmptyשימו לב המנשקStack , צריך להיות בחבילהil.ac.telhai.ds.stack , ואין לשנות זאת.
3) כלומר כיתבו את המחלקה) il.ac.telhai.ds.stack.DLinkedListStack כתבו מחלקה גנרי
( il.ac.telhai.ds.stack בחבילהDLinkedListStack
המממשת את הנ”ל ומשתמשת במחלקהDLinkedList ממעבדה 3.
הוסיפו שיטהtoString המחזירהString המתאר את המחסנית בפורמט הבא (דייקו רווחים)
[a1, a2, …, an]
כאשרa1 הוא ראש המחסנית,a2 תחתיו וכן הלאה עד ל-an שבתחתית המחסנית.
אם המחסנית ריקה יודפס [].
האיברים במחסנית מטיפוסT מודפסים על ידי שימוש ב-toString של המחלקהT .
שימו לב להשתמש ב-StringBuilder כמקובל.
הוסיפו בנאי או בנאים למחלקה לפי הצורך.
4) בדקו את המחלקה הנ”ל בעזרת מחלקת הבדיקהDLinkedListStackTest (הנמצאת באותהחבילה) ונתונה לכם.
5) השלימו את המחלקהil.ac.telhai.ds.stack.EvaluatePostfix כך שהיא תקלוט ביטוי בודדבכתיב פולני הפוך תוך כדי שימוש בStreamTokenizer שלמדנו במעבדה הראשונה.
קריאת הקלט תסתיים בקליטתTT_EOF (סיום קובץ הקלט, ניתן לסמלץ זאת באמצעותctrl+D אוctrl+Z), או בקליטת המילהquit .
אם הביטוי תקין, התכנית תדפיס את ערך הביטוי ל-System.out .
אחרת, כאשר מתגלית השגיאה התכנית תדפיס את מצב הStreamTokenizer (בעזרת השיטהtoString שלה) לתוך פלט השגיאה (System.err) ובשורה הבאה תדפיס את תוכן המחסנית(בעזרת השיטהtoString שלה) גם כן לתוך פלט השגיאה (System.err), ותצא מההרצה עם קודשגיאה 1.
כלומר בעת גילוי השגיאה על התכנית לבצע:
System.err.println(tokenizer);
System.err.println(myStack);
System.exit(1);
כאשר המשתנהtokenizer מטיפוסStreamTokenizer , ו-myStack הוא המשתנה של המחסנית.
סדר העבודה ופרטים טכניים
:GITHUB מתוךDS-Lab05-Stack שליפת הפרויקט●
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הקודמת יש לבצע שליפהמחדש לפי ההוראות במעבדה 4.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
■ עכבר ימני
Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab05_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם כאשר הם נמצאים בתיקייה
il/ac/telhai/ds/stack
כלומר, השורש של קובץ ההגשה יכיל רק תיקייה בשםil שמכילה את כל ההיררכיה של קבצים.
ומכיל את כל קבצי -java . להמחשה תמונה של קובץ כזה שנפתח ב -WindowsExplorer

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