Evaluate Reverse Polish Notation
ניתן לך ביטוי חשבוני בסימון פולני הפוך, כמערך של אסימונים. בסימון הזה כל אופרטור מופיע מיד אחרי שני האופרנדים שלו, לכן 3 4 + פירושו 3 + 4 ו-3 4 + 2 * פירושו (3 + 4) * 2, ואין צורך בסוגריים. כל אסימון הוא מספר שלם או אחד מהאופרטורים +, -, * ו-/.
חשבו את ערך הביטוי והחזירו אותו. בחילוק נשמר רק החלק השלם והתוצאה נקטעת לכיוון אפס: 7 / 2 הוא 3 ו--7 / 2 הוא -3.
פונקציה
- tokensstring-array
- המספרים והאופרטורים של הביטוי, לפי הסדר
- מחזירהinteger
- הערך של הביטוי
אילוצים
1 ≤ tokens.length ≤ 104- כל אסימון הוא
+,-,*,/, או מספר שלם בין-200ל־200שנכתב בשיטה העשרונית, עם סימן מינוס מוביל אם הוא שלילי. tokensהוא ביטוי תקין בסימון פולני הפוך.- לא מתרחשת חלוקה באפס, וכל ערך ביניים וערך סופי גדול מ־
-231וקטן מ־231.
דוגמאות
- קלט
- tokens = ["8", "3", "-", "4", "*"]
- פלט
- 20
- הסבר
- הפעולה
-חלה על שני המספרים שלפניה לפי הסדר שלהם, 8 ואז 3, ולכן התוצאה היא 5, ולא -5. לאחר מכן*מכפיל את 5 הזה ב-4, והתוצאה היא 20.
- קלט
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- פלט
- -6
- הסבר
- האופרטור הראשון,
/, משתמש בשני הערכים האחרונים: 9 חלקי 3 הם 3. לאחר מכן-מחשב 2 פחות 3, שהם -1, ו-*מכפיל את 6 ב--1.
- קלט
- tokens = ["10", "-7", "2", "/", "+"]
- פלט
- 7
- הסבר
- האסימון
-7הוא מספר, לא אופרטור. -7 חלקי 2 הם -3.5, שנחתך לכיוון אפס ל־-3 במקום לעגל כלפי מטה ל־-4, ו־10 ועוד -3 שווה ל־7.
+18 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל לבנות מחדש את הביטוי בסימון רגיל, כמו (3 + 4) * 2, ולהוסיף סוגריים רק במקומות שבהם הם משנים את המשמעות?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא את האסימונים משמאל לימין. כשאתה נתקל באופרטור, על אילו שני ערכים הוא פועל? שים לב לסדר שבו הערכים האלה נוצרו.
אופרטור פועל תמיד על שני הערכים האחרונים שאף אופרטור עדיין לא השתמש בהם, והתוצאה שלו הופכת לערך חדש עבור האופרטורים הבאים. "האחרון שעדיין לא נעשה בו שימוש" הוא בדיוק מה שמחסנית מספקת.
דחפו כל מספר. כשמגיעים לאופרטור, הוציאו תחילה את האופרנד הימני ואז את האופרנד השמאלי, שלבו אותם בסדר הזה ודחפו את התוצאה. כשנגמרים האסימונים, נשאר ערך אחד במחסנית: התשובה. ודאו שהחלוקה שלכם מעגלת לכיוון אפס.
פתרון
סימון פולני הפוך אינו זקוק לסוגריים, כי סדר האסימונים כבר קובע את סדר הפעולות: כל אופרטור פועל על שני הערכים שמופיעים ממש לפניו, וכל אחד מהערכים האלה עשוי להיות תוצאה של אופרטור קודם. מחסנית של ערכים מחשבת את הביטוי כולו במעבר יחיד משמאל לימין. המכשולים נמצאים בפרטים: סדר האופרנדים עבור - ו־/, ההבחנה בין האופרטור - לבין המספר -7, וחלוקה שנקטעת לכיוון אפס.
כווץ את האופרטור הראשון, חזור
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
כך היית פותר את זה על נייר. מצא את האופרטור השמאלי ביותר. אין לפניו אופרטור, ולכן שני האסימונים שמופיעים מיד לפניו הם מספרים רגילים, והם האופרנדים שלו. חשב את התוצאה והחלף את שלושת האסימונים האלה במספר אחד. הביטוי כעת קצר יותר ועדיין משמעו אותו הדבר. חזור על כך עד שנשאר מספר אחד.
קח את ["6", "2", "9", "3", "/", "-", "*"]. האופרטור הראשון הוא /, ולכן 9 3 / הופך ל־3: ["6", "2", "3", "-", "*"]. אחר כך 2 3 - הופך ל־-1: ["6", "-1", "*"]. אחר כך 6 -1 * הופך ל־-6, התשובה.
זה נכון כי בכל סבב מחליפים חלק שלם a b op בערך שלו, והאופרטורים שאחריו רואים את הערך בדיוק במקום שבו החלק הזה היה. זה איטי כי בכל סבב מחפשים שוב מההתחלה ואז סוגרים רווח באמצע המערך. כשיש 5,000 מספרים ואחריהם 4,999 אופרטורים, האופרטור הראשון נמצא בערך באמצע לאורך כל 4,999 הסבבים, ולכן החיפושים לבדם בודקים בערך 1.25 × 10^7 אסימונים. המספרים שמשמאל לאופרטור כמעט אינם משתנים מסבב אחד למשנהו, ובכל זאת קוראים אותם שוב בכל סבב.
אלגוריתם
- העתיקו את האסימונים לרשימה שאפשר לשנות.
- סרקו מההתחלה עד לאופרטור הראשון, במיקום
k. - הפעילו אותו על המספרים במיקומים
k-2(משמאל) ו-k-1(מימין). - החליפו את שלושת האסימונים במיקומים
k-2,k-1ו-kבתוצאה. - חזרו על הפעולה עד שיישאר אסימון אחד, והחזירו אותו כמספר.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])מעבר אחד עם מחסנית של ערכים
האינטואיציה
גישת הצמצום דורשת לקרוא שוב ושוב את המספרים שמימין לאופרטור. השתמשו במחסנית במקום זאת. קראו את האסימונים פעם אחת, משמאל לימין. מספר נכנס למחסנית. אופרטור שולף את שני הערכים העליונים מהמחסנית, משלב אותם ומחזיר את התוצאה למחסנית, שם היא ממתינה לאופרטור הבא כמו כל ערך אחר.
עברו על ["6", "2", "9", "3", "/", "-", "*"]. ארבעת המספרים נכנסים למחסנית: [6, 2, 9, 3]. האופרטור / שולף את 3 ואז את 9 ודוחף 9 / 3 = 3: [6, 2, 3]. האופרטור - שולף את 3 ואז את 2 ודוחף 2 - 3 = -1: [6, -1]. האופרטור * שולף את -1 ואז את 6 ודוחף 6 * -1 = -6. נשאר ערך אחד, והוא התשובה.
למה זה עובד: בכל רגע המחסנית מכילה את הערכים של החלקים השלמים שנקראו עד כה, לפי הסדר, ואופרטור תמיד פועל על שני האחרונים שבהם. ראש המחסנית הוא האופרנד הימני, כי הוא נוצר אחרון, ולכן שולפים אותו ראשון. טעות בסדר הזה מתגלה רק עם - ועם /, שבהם 8 3 - חייב להיות 5 ולא -5.
חלוקה דורשת זהירות בשפות מסוימות. הביטוי מעגל לכיוון אפס, אבל // של Python, / של Ruby ו-%/% של R מעגלים כלפי מטה, מה שהופך את -3.5 ל--4. כל מספר נדחף פעם אחת, וכל אופרטור שולף שני ערכים ודוחף אחד, ולכן המעבר נמשך O(n) זמן, והמחסנית לעולם אינה מכילה יותר מ-n ערכים.
אלגוריתם
- התחל עם מחסנית ריקה.
- עבור כל אסימון שהוא מספר, דחוף את הערך שלו.
- עבור כל אופרטור, שלוף את האופרנד הימני, ואז את האופרנד השמאלי.
- חשב
left op right, תוך עיגול לכיוון אפס עבור/, ודחוף את התוצאה. - אחרי האסימון האחרון, החזר את הערך היחיד שבמחסנית.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
מלכודות ומקרי קצה
לולאת המחסנית קצרה; רוב התשובות השגויות נובעות מסדר האופרנדים ומהאופן שבו שפה מבצעת חילוק.
- החלפת סדר האופרנדים. הערך הראשון שנשלף הוא האופרנד הימני:
["3", "5", "-"]הוא -2, ו-["2", "9", "/"]הוא 0, לא 4. - זיהוי אופרטורים לפי התו הראשון שלהם.
-7מתחיל בסימן מינוס, אבל הוא מספר. השוו את האסימון כולו, או בדקו שאורכו תו אחד. - עיגול כלפי מטה במקום קטיעה.
-7 / 2חייב להחזיר -3, ו--1 / 3חייב להחזיר 0.//של Python, /של Ruby, %/%של R ו-math.floorשל Lua מחזירים -4 ו--1. - הדפסת
-0. ב-JavaScript וב-Lua כל מספר הוא מספר נקודה צפה, ולכן0 * -5ו-Math.trunc(-1 / 3)מחזירים אפס שלילי, שמודפס כ--0. הוסיפו 0 לערך הסופי כדי להפוך אותו ל-0. - קריאת מספר ספרה אחת בכל פעם. לאסימונים כגון
13ו--200יש כמה תווים; נתחו את האסימון כולו. - הנחה שהאסימון האחרון הוא אופרטור. מספר יחיד, כגון
["7"], הוא ביטוי תקין שערכו 7.
שאלות נפוצות4
מהי סיבוכיות הזמן של Evaluate Reverse Polish Notation?
פתרון המחסנית פועל בזמן O(n) עבור n אסימונים: כל מספר נדחף פעם אחת, וכל אופרטור מבצע שתי שליפות ודחיפה אחת. המחסנית יכולה להכיל עד בערך n/2 ערכים, לכן המקום הנדרש הוא O(n). צמצום האופרטור הראשון שוב ושוב אורך זמן O(n²), כי בכל סבב מתבצע חיפוש מחדש מההתחלה.
למה סימון פולני הפוך אינו זקוק לסוגריים?
בסימון רגיל, 3 + 4 * 2 נדרש כלל קדימות או סוגריים כדי לציין איזו פעולה מתבצעת קודם. בסימון פולני הפוך, אופרטור תמיד חל על שני הערכים שמופיעים ממש לפניו, ולכן סדר האסימונים אומר הכול: 3 4 2 * + הוא 11 ו-3 4 + 2 * הוא 14. לכן מחסנית יחידה יכולה לחשב את התוצאה בלי להציץ קדימה.
איך מבצעים חלוקה עם עיגול לכיוון אפס ב-Python?
השתמשו ב־int(a / b). האופרטור // מעגל כלפי מטה, לכן -7 // 2 הוא -4, ואילו int(-7 / 2) הוא -3. חלוקת נקודה צפה מדויקת מספיק כאן, כי הערכים מתאימים ל־32 סיביות. עבור מספרים שלמים גדולים כרצונכם, חלקו את הערכים המוחלטים באמצעות // והחזירו את הסימן לאחר מכן.
איך ממירים ביטוי רגיל לסימון פולני הפוך?
אלגוריתם חצר המיון עושה זאת במעבר אחד באמצעות מחסנית של אופרטורים. המספרים עוברים ישירות לפלט. לפני שאופרטור נדחף למחסנית, כל אופרטור במחסנית שקדימותו גבוהה או שווה מועבר לפלט; סוגריים פותחים נדחפים למחסנית, וסוגריים סוגרים מעבירים אופרטורים לפלט עד שהם פוגשים את הסוגר התואם. בסוף, האופרטורים שנותרו מועברים לפלט.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def evalRPN(tokens):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
tokens = ["8", "3", "-", "4", "*"]
צפוי
20