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.
שאלת המשך
האם תוכל לבנות מחדש את הביטוי בסימון רגיל, כמו (3 + 4) * 2, ולהוסיף סוגריים רק במקומות שבהם הם משנים את המשמעות?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא את האסימונים משמאל לימין. כשאתה נתקל באופרטור, על אילו שני ערכים הוא פועל? בדוק את הסדר שבו הערכים האלה נוצרו.
אופרטור תמיד פועל על שני הערכים האחרונים שעוד לא נעשה בהם שימוש על ידי אופרטור, והתוצאה שלו הופכת לערך חדש עבור האופרטורים שבאים אחריו. "האחרון שעדיין לא נעשה בו שימוש" הוא בדיוק מה שמחסנית מספקת.
דחפו כל מספר. כשמופיע אופרטור, שלפו תחילה את האופרנד הימני ואז את האופרנד השמאלי, שלבו אותם לפי הסדר הזה ודחפו את התוצאה. כשנגמרים האסימונים, נותר ערך אחד במחסנית: התשובה. ודאו שהחלוקה שלכם מעגלת לכיוון אפס.
פתרון
כל אופרטור חל על שני הערכים שמופיעים ממש לפניו, וכל אחד מהם עשוי להיות תוצאה של אופרטור קודם. לכן מחסנית של ערכים מחשבת את הביטוי במעבר אחד. המלכודות הן סדר האופרנדים עבור - ו־/, ההבחנה בין האופרטור - לבין המספר -7, וחלוקה עם קטיעת השבר.
כווץ את האופרטור הראשון, חזור על הפעולה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מצא את האופרטור השמאלי ביותר. אין אופרטור לפניו, לכן שני האסימונים שלפניו הם מספרים, האופרנדים שלו. החלף את שלושת האסימונים האלה בתוצאה שלהם. האופרטורים שאחריו רואים את הערך הזה במקום שבו עמד הביטוי, ולכן הביטוי שומר על המשמעות שלו. חזור על הפעולה עד שנשאר מספר אחד.
בכל סבב החיפוש מתחיל שוב מההתחלה. כשיש 5,000 מספרים ואחריהם 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 / - *, ה-/ שולף תחילה את 3 ואז את 9 ודוחף את 3, ה-- שולף את 3 ואז את 2 ודוחף את -1, וה-* דוחף את 6 × -1 = -6. כל אסימון מטופל פעם אחת: זמן O(n) ומקום O(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מתחיל בסימן מינוס, אבל הוא מספר, לכן יש להשוות את האסימון כולו. - עיגול כלפי מטה במקום קטיעה.
//של Python,/של Ruby,%/%של R ו-math.floorשל Lua הופכים את-7 / 2ל-4- ואת-1 / 3ל-1-. - הדפסת
-0. ב-JavaScript וב-Lua, הביטויים0 * -5ו-Math.trunc(-1 / 3)מחזירים אפס שלילי. יש להוסיף 0 לערך הסופי.
שאלות נפוצות4
מהי סיבוכיות הזמן של Evaluate Reverse Polish Notation?
פתרון המחסנית פועל בזמן O(n) עבור n אסימונים: כל מספר נדחף פעם אחת, וכל אופרטור מבצע שתי שליפות ודחיפה אחת. המחסנית מכילה עד כ־n/2 ערכים, ולכן צריכת המקום היא 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-bit. עבור מספרים שלמים גדולים יותר, חלקו את הערכים המוחלטים באמצעות // והחזירו את הסימן.
איך ממירים ביטוי רגיל לכתיב פולני הפוך?
אלגוריתם תחנת המיון מבצע זאת במעבר אחד באמצעות מחסנית של אופרטורים. המספרים עוברים ישירות לפלט. לפני שדוחפים אופרטור, מעבירים לפלט כל אופרטור שבמחסנית שיש לו קדימות גבוהה או שווה. סוגר סוגר מעביר אופרטורים החוצה עד לסוגר הפותח התואם לו. בסוף, כל השאר עוברים לפלט.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def evalRPN(tokens):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
tokens = ["8", "3", "-", "4", "*"]
הפלט הצפוי
20