מהו סימון אינפיקס?
סימון אינפיקס הוא סימון שבו ביטוי נכתב בפורמט רגיל או רגיל. זהו סימון שבו האופרטורים נמצאים בין האופרנדים. הדוגמאות לסימון אינפיקס הן A+B, A*B, A/B וכו'.
כפי שאנו יכולים לראות בדוגמאות לעיל, כל האופרטורים קיימים בין האופרנדים, כך שהם סימוני אינפיקס. לכן, ניתן לכתוב את התחביר של סימון אינפיקס כך:
ניתוח ביטויי אינפיקס
על מנת לנתח ביטוי כלשהו, עלינו לדאוג לשני דברים, כלומר, עדיפות מפעיל ו אסוציאטיביות . עדיפות מפעיל פירושה עדיפות של כל מפעיל על פני מפעיל אחר. לדוגמה:
A + B * C → A + (B * C)
מכיוון שלאופרטור הכפל יש קדימות גבוהה יותר על פני אופרטור החיבור, כך ביטוי B * C יוערך תחילה. תוצאת הכפל של B * C מתווספת ל-A.
סדר עדיפות
| מפעילים | סמלים |
|---|---|
| מַאֲמָר מוּסְגָר | { }, ( ), [ ] |
| סימון אקספוננציאלי | ^ |
| כפל וחילוק | *, / |
| חיבור וחיסור | +, - |
אסוציאטיביות פירושה כאשר האופרטורים בעלי אותה קדימות קיימים בביטוי. לדוגמה, בביטוי, כלומר, לאופרטורים A + B - C, '+' ו-'-' יש את אותה קדימות, ולכן הם מוערכים בעזרת אסוציאטיביות. מכיוון שגם '+' וגם '-' הם אסוציאטיביים לשמאל, הם יוערכו כ-(A + B) - C.
סדר אסוציאטיביות
| מפעילים | אסוציאטיביות |
|---|---|
| ^ | מימין לשמאל |
| *, / | משמאל לימין |
| +, - | משמאל לימין |
בואו נבין את האסוציאטיביות באמצעות דוגמה.
1 + 2*3 + 30/5
מכיוון שבביטוי לעיל, * ו-/ הם בעלי אותה קדימות, אז ניישם את כלל האסוציאטיביות. כפי שאנו יכולים לראות בטבלה שלמעלה כי לאופרטורים * ו-/ יש אסוציאטיביות משמאל לימין, כך נסרוק מהאופרטור השמאלי ביותר. המפעיל שיגיע ראשון יוערך ראשון. האופרטור * מופיע לפני האופרטור /, והכפל ייעשה תחילה.
1+ (2*3) + (30/5)
1+6+6 = 13
100 קמ"ש עד קמ"ש
מהו סימון קידומת?
סימון קידומת הוא צורת ביטוי נוספת אך הוא אינו דורש מידע אחר כגון קדימות ואסוציאטיביות, ואילו סימון אינפיקס דורש מידע של עדיפות ואסוציאטיביות. זה ידוע גם בשם סימון פולני . בסימון קידומת, אופרטור בא לפני האופרנדים. התחביר של סימון הקידומת ניתן להלן:
לדוגמה, אם הביטוי אינפיקס הוא 5+1, אז ביטוי הקידומת המתאים לביטוי אינפיקס זה הוא +51.
אם ביטוי האינפקס הוא:
a * b + c
↓
*ab+c
↓
+*abc (ביטוי קידומת)
שקול דוגמה נוספת:
A + B * C
סריקה ראשונה: בביטוי לעיל, לאופרטור הכפל יש עדיפות גבוהה יותר מאופרטור החיבור; סימון הקידומת של B*C יהיה (*BC).
A + *BC
סריקה שנייה: בסריקה השנייה, הקידומת תהיה:
+A *BC
בביטוי לעיל, אנו משתמשים בשתי סריקות כדי להמיר אינפיקס לביטוי קידומת. אם הביטוי מורכב, אזי אנו דורשים מספר רב יותר של סריקות. עלינו להשתמש בשיטה שדורשת רק סריקה אחת, ומספקת את התוצאה הרצויה. אם נשיג את הפלט הרצוי באמצעות סריקה אחת, אז האלגוריתם יהיה יעיל. זה אפשרי רק באמצעות מחסנית.
המרה של Infix לקידומת באמצעות Stack
K + L - M * N + (O^P) * W/U/V * T + Q
אם אנו ממירים את הביטוי מ-infix לקידומת, עלינו תחילה להפוך את הביטוי.
הביטוי ההפוך יהיה:
Q + T * V/U/W * ) P^O(+ N*M - L + K
כדי לקבל את ביטוי הקידומת, יצרנו טבלה המורכבת משלוש עמודות, כלומר, ביטוי קלט, מחסנית וביטוי קידומת. כאשר אנו נתקלים בסמל כלשהו, אנו פשוט מוסיפים אותו לביטוי הקידומת. אם ניתקל במפעיל, נדחוף אותו לערימה.
| ביטוי קלט | לַעֲרוֹם | ביטוי קידומת |
|---|---|---|
| ש | ש | |
| + | + | ש |
| ט | + | QT |
| * | +* | QT |
| IN | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| פ | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| נ | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| ל | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| ק | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
הביטוי לעיל, כלומר QTVUWPO^*//*NM*LK+-++, אינו ביטוי סופי. עלינו להפוך את הביטוי הזה כדי לקבל את ביטוי הקידומת.
כללים להמרת אינפיקס לביטוי קידומת:
- ראשית, הפוך את ביטוי האינפקס שניתן בבעיה.
- סרוק את הביטוי משמאל לימין.
- בכל פעם שהאופרנדים מגיעים, הדפס אותם.
- אם המפעיל מגיע ונמצא שהמחסנית ריקה, פשוט דחפו את המפעיל לערימה.
- אם לאופרטור הנכנס יש עדיפות גבוהה יותר מהחלק העליון של הערימה, דחוף את האופרטור הנכנס לתוך הערימה.
- אם לאופרטור הנכנס יש את אותה קדימות עם חלק העליון של הערימה, דחוף את האופרטור הנכנס לתוך הערימה.
- אם לאופרטור הנכנס יש קדימות נמוכה יותר מהחלק העליון של הערימה, הקפץ והדפיס את החלק העליון של הערימה. בדוק שוב את האופרטור הנכנס מול החלק העליון של הערימה והקפיץ את האופרטור מהמחסנית עד שהוא ימצא את האופרטור בעל קדימות נמוכה יותר או אותה קדימות.
- אם לאופרטור הנכנס יש את אותה קדימות עם החלק העליון של הערימה והאופרטור הנכנס הוא ^, אז הקפיץ את החלק העליון של הערימה עד שהתנאי יתקיים. אם התנאי אינו נכון, לחץ על האופרטור ^.
- כשנגיע לסוף הביטוי, מקפץ ומדפיס את כל האופרטורים מהחלק העליון של הערימה.
- אם האופרטור הוא ')', דחף אותו לערימה.
- אם האופרטור הוא '(', אז קפץ את כל האופרטורים מהערימה עד שהוא מוצא את תושבת הפתיחה בערימה.
- אם החלק העליון של הערימה הוא ')', דחוף את המפעיל על הערימה.
- בסוף, הפוך את הפלט.
פסאודוקוד של המרת אינפיקס לקידומת
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>