לפני שנבין את ההמרה מ-infix ל-postfix, עלינו לדעת על סימון ה-infix וה-postfix בנפרד.
אינפיקס ופוסט-תיקון הם הביטויים. ביטוי מורכב מקבועים, משתנים וסמלים. סמלים יכולים להיות אופרטורים או סוגריים. יש לסדר את כל הרכיבים הללו על פי קבוצת כללים כך שניתן יהיה להעריך את כל הביטויים הללו באמצעות קבוצת הכללים.
דוגמאות לביטויים הם:
5 + 6
א - ב
(P * 5)
לכל הביטויים לעיל יש מבנה משותף, כלומר, יש לנו אופרטור בין שני האופרנדים. אופרנד הוא אובייקט או ערך שעליו יש לבצע את הפעולה. בביטויים לעיל, 5, 6 הם האופרנדים ואילו '+', '-' ו-'*' הם האופרטורים.
מהו סימון אינפיקס?
כאשר האופרטור נכתב בין האופרנדים, הוא ידוע בשם סימון אינפיקס . אופרנד לא חייב להיות תמיד קבוע או משתנה; זה יכול להיות גם ביטוי עצמו.
לדוגמה,
(p + q) * (r + s)
בביטוי לעיל, שני הביטויים של אופרטור הכפל הם האופרנדים, כלומר, (p + q) , ו (r + s) הם האופרנדים.
בביטוי לעיל, ישנם שלושה אופרטורים. האופרנדים לאופרטור הפלוס הראשון הם p ו-q, האופרנדים לאופרטור הפלוס השני הם r ו-s. תוך כדי ביצוע ה פעולות על הביטוי, עלינו לעקוב אחר סט כללים כדי להעריך את התוצאה. בתוך ה הביטוי לעיל, פעולת החיבור תתבצע בשני הביטויים, כלומר, p+q ו-r+s, ולאחר מכן תבוצע פעולת הכפל.
תחביר של סימון אינפיקס ניתן להלן:
אם יש רק אופרטור אחד בביטוי, איננו דורשים להחיל שום כלל. לדוגמה, 5 + 2; בביטוי זה, ניתן לבצע פעולת חיבור בין שני האופרנדים (5 ו-2), והתוצאה של הפעולה תהיה 7.
אם יש מספר אופרטורים בביטוי, יש לפעול לפי כלל כלשהו כדי להעריך את הביטוי.
אם הביטוי הוא:
4+6*2
אם אופרטור הפלוס מוערך תחילה, הביטוי ייראה כך:
10 * 2 = 20
אם אופרטור הכפל מוערך תחילה, אז הביטוי ייראה כך:
4 + 12 = 16
מיזוג מיון java
ניתן לפתור את הבעיה שלעיל על ידי ביצוע כללי קדימות המפעיל. בביטוי האלגברי, סדר עדיפות האופרטור ניתן בטבלה הבאה:
| מפעילים | סמלים |
|---|---|
| מַאֲמָר מוּסְגָר | ( ), {}, [ ] |
| מעריכים | ^ |
| כפל וחילוק | *, / |
| חיבור וחיסור | + , - |
העדפה ראשונה ניתנת לסוגריים; ואז העדפה הבאה ניתנת למעריכים. במקרה של מספר אופרטורים מעריכים, הפעולה תיושם מימין לשמאל.
לדוגמה:
2^2^3 = 2^8
= 256
לאחר מעריך, אופרטורים כפל וחילוק מוערכים. אם שני האופרטורים קיימים בביטוי, הפעולה תיושם משמאל לימין.
ההעדפה הבאה ניתנת לחיבור וחיסור. אם שני האופרטורים זמינים בביטוי, נעבור משמאל לימין.
האופרטורים בעלי אותה קדימות נקראים אסוציאטיביות של מפעיל . אם נלך משמאל לימין, אז זה ידוע בתור שמאלי-אסוציאטיבי. אם נלך מימין לשמאל, אז זה ידוע בתור אסוציאטיבי ימני.
בעיה עם סימון אינפיקס
כדי להעריך את ביטוי האינפקס, עלינו לדעת על ה עדיפות מפעיל כללים, ואם למפעילים יש את אותה קדימות, אז עלינו לפעול לפי אסוציאטיביות כללים. השימוש בסוגריים חשוב מאוד בסימון אינפיקס כדי לשלוט בסדר שבו יש לבצע את הפעולה. סוגריים משפרים את קריאות הביטוי. ביטוי אינפיקס הוא הדרך הנפוצה ביותר לכתיבת ביטוי, אך לא קל לנתח ולהעריך את ביטוי האינפיק ללא עמימות. אז, מתמטיקאים ולוגיקאים חקרו בעיה זו וגילו שתי דרכים אחרות לכתיבת ביטויים שהם קידומת ופוסט-פיקס. שני הביטויים אינם דורשים כל סוגריים וניתן לנתח אותם ללא עמימות. זה לא דורש קדימות אופרטור וכללי אסוציאטיביות.
ביטוי Postfix
הביטוי postfix הוא ביטוי שבו האופרטור נכתב אחרי האופרנדים. לדוגמה, ניתן לכתוב את הביטוי שלאחר התיקון של סימון אינפיקס (2+3) כ-23+.
כמה נקודות מפתח לגבי הביטוי שלאחר התיקון הן:
- בביטוי postfix, הפעולות מתבצעות לפי סדר הכתיבה משמאל לימין.
- זה לא דורש שום סוגריים.
- איננו צריכים ליישם כללי קדימות אופרטור וכללי אסוציאטיביות.
אלגוריתם להערכת ביטוי postfix
- סרוק את הביטוי משמאל לימין עד שנתקל באופרטור כלשהו.
- בצע את הפעולה
- החלף את הביטוי בערך המחושב שלו.
- חזור על השלבים מ-1 עד 3 עד שלא קיימים יותר אופרטורים.
בואו נבין את האלגוריתם לעיל באמצעות דוגמה.
ביטוי אינפיקס: 2 + 3 * 4
נתחיל לסרוק משמאל את רוב הביטוי. אופרטור הכפל הוא אופרטור המופיע ראשון בזמן סריקה משמאל לימין. כעת, הביטוי יהיה:
מה זה 10 מתוך מיליון
ביטוי = 2 + 34*
= 2 + 12
שוב, נסרוק משמאל לימין, והביטוי יהיה:
ביטוי = 2 12 +
= 14
הערכה של ביטוי postfix באמצעות מחסנית.
- סרוק את הביטוי משמאל לימין.
- אם אנו נתקלים באופרנד כלשהו בביטוי, אז אנו דוחפים את האופרנד בערימה.
- כאשר אנו נתקלים באופרטור כלשהו בביטוי, אנו מקפיצים את האופרנדים המתאימים מהמחסנית.
- כשאנחנו מסיימים עם סריקת הביטוי, הערך הסופי נשאר בערימה.
בואו נבין את ההערכה של ביטוי postfix באמצעות מחסנית.
דוגמה 1: ביטוי Postfix: 2 3 4 * +
| קֶלֶט | לַעֲרוֹם | |
|---|---|---|
| 2 3 4 * + | ריק | דחיפה 2 |
| 3 4 * + | 2 | דחיפה 3 |
| 4*+ | 3 2 | דחיפה 4 |
| *+ | 4 3 2 | פתחו 4 ו-3, ובצעו 4*3 = 12. דחפו 12 לערימה. |
| + | 12 2 | קפוץ 12 ו-2 מהערימה, ובצעו 12+2 = 14. דחפו 14 לתוך הערימה. |
התוצאה של הביטוי לעיל היא 14.
דוגמה 2: ביטוי Postfix: 3 4 * 2 5 * +
| קֶלֶט | לַעֲרוֹם | |
|---|---|---|
| 3 4 * 2 5 * + | ריק | דחיפה 3 |
| 4*2 5*+ | 3 | דחיפה 4 |
| *2 5 * + | 4 3 | קפץ 3 ו-4 מהערימה ובצע 3*4 = 12. דחף 12 לתוך הערימה. |
| 2 5 * + | 12 | דחיפה 2 |
| 5*+ | 2 12 | דחף 5 |
| *+ | 5 2 12 | קפוץ 5 ו-2 מהערימה ובצעו 5*2 = 10. דחפו 10 לתוך הערימה. |
| + | 10 12 | קפוץ 10 ו-12 מהערימה ובצעו 10+12 = 22. דחפו 22 לערימה. |
התוצאה של הביטוי לעיל היא 22.
אלגוריתם להערכת ביטוי postfix
- קרא דמות
- אם התו הוא ספרה, המר את התו ל-int ודחוף את המספר השלם לתוך הערימה.
- אם הדמות היא אופרטור,
- קפץ את האלמנטים מהערימה פעמיים והשיג שני אופרנדים.
- בצע את הפעולה
- דחפו את התוצאה לתוך הערימה.
המרה של אינפיקס ל-postfix
כאן, נשתמש במבנה הנתונים מחסנית להמרה של ביטוי אינפיקס לביטוי קידומת. בכל פעם שמפעיל יתקל, אנו דוחפים מפעיל לערימה. אם אנו נתקלים באופרנד, אז נצרף את האופרנד לביטוי.
כללים להמרה מביטוי infix לביטוי postfix
- הדפס את האופרנד כשהם מגיעים.
- אם הערימה ריקה או מכילה סוגריים שמאלי למעלה, דחוף את האופרטור הנכנס אל הערימה.
- אם הסמל הנכנס הוא '(', דחף אותו לערימה.
- אם הסמל הנכנס הוא ')', פתח את הערימה והדפיס את האופרטורים עד שיימצא הסוגרי השמאלי.
- אם לסמל הנכנס יש עדיפות גבוהה יותר מהחלק העליון של הערימה, דחוף אותו על הערימה.
- אם לסמל הנכנס יש קדימות נמוכה יותר מהחלק העליון של הערימה, הקפץ והדפיס את החלק העליון של הערימה. לאחר מכן בדוק את האופרטור הנכנס מול החלק העליון החדש של הערימה.
- אם לאופרטור הנכנס יש את אותה קדימות עם החלק העליון של הערימה אז השתמש בכללי האסוציאטיביות. אם האסוציאטיביות היא משמאל לימין אז קפץ והדפיס את החלק העליון של הערימה ואז לחץ על האופרטור הנכנס. אם האסוציאטיביות היא מימין לשמאל אז דחוף את האופרטור הנכנס.
- בסוף הביטוי, פופ והדפיס את כל האופרטורים של הערימה.
בואו נבין דרך דוגמה.
ביטוי אינפיקס: K + L - M*N + (O^P) * W/U/V * T + Q
| ביטוי קלט | לַעֲרוֹם | ביטוי Postfix |
|---|---|---|
| ק | ק | |
| + | + | |
| ל | + | ק ל |
| - | - | K L+ |
| M | - | K L+M |
| * | - * | K L+M |
| נ | - * | K L + M N |
| + | + | K L + M N* K L + M N* - |
| ( | + ( | K L + M N *- |
| O | + ( | K L + M N * - O |
| ^ | + (^ | K L + M N* - O |
| פ | + (^ | K L + M N* - O P |
| ) | + | K L + M N* - O P ^ |
| * | + * | K L + M N* - O P ^ |
| IN | + * | K L + M N* - O P ^ W |
| / | + / | K L + M N* - O P ^ W * |
| IN | + / | K L + M N* - O P ^W*U |
| / | + / | K L + M N* - O P ^W*U/ |
| IN | + / | KL + MON*-UP^W*U/F |
| * | + * | KL+MON*-UP^W*U/F/ |
| ט | + * | KL+MN*-UP^W*U/F/T |
| + | + | MON+MON*-UP^W*U/F/T* KL+MN*-UP^W*U/F/T*+ |
| ש | + | KL+MN*-OP^W*U/V/T*Q |
| KL+MN*-OP^W*U/V/T*+Q+ |
הביטוי הסופי שלאחר התיקון של ביטוי אינפיקס (K + L - M*N + (O^P) * W/U/V * T + Q) הוא KL+MN*-OP^W*U/V/T*+Q+ .