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
ما هو التعقيد الزمني لتقييم التدوين البولندي العكسي؟
يعمل حل المكدس بزمن 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 بت. بالنسبة إلى الأعداد الصحيحة الأكبر، اقسم القيم المطلقة باستخدام // ثم أعد الإشارة.
كيف تحوّل تعبيرًا عاديًا إلى تدوين بولندي عكسي؟
تنفّذ خوارزمية ساحة التحويل ذلك في مرور واحد باستخدام مكدّس من المعاملات. تنتقل الأعداد مباشرةً إلى المخرجات. قبل دفع معامل إلى المكدّس، انقل إلى المخرجات كل معامل مكدّس ذي أسبقية أعلى أو مساوية. ينقل القوس الأيمن المعاملات إلى الخارج حتى يصل إلى القوس الأيسر المقابل له. في النهاية، انقل الباقي إلى المخرجات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def evalRPN(tokens):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
tokens = ["8", "3", "-", "4", "*"]
الإخراج المتوقع
20