Evaluate Reverse Polish Notation

Q: ما هو التعقيد الزمني لتقييم تدوين بولندي عكسي؟

يعمل حل المكدس في زمن O(n) بالنسبة إلى n من الرموز: يُدفع كل عدد مرة واحدة، ويُجري كل عامل عمليتي سحب وعملية دفع واحدة. يمكن أن يحتوي المكدس على ما يصل إلى نحو n/2 من القيم، لذا فإن المساحة هي O(n) . أما اختزال العامل الأول مرارًا وتكرارًا فيستغرق زمنًا قدره O(n²) ، لأن كل جولة تبحث من البداية من جديد.

Q: لماذا لا تحتاج الكتابة البولندية العكسية إلى أقواس؟

في التدوين المعتاد، يحتاج 3 + 4 * 2 إلى قاعدة أسبقية أو أقواس لتحديد العملية التي تُنفَّذ أولًا. في التدوين البولندي العكسي، يُطبَّق العامل دائمًا على القيمتين اللتين تسبقانه مباشرةً، لذا فإن ترتيب الرموز يوضّح كل شيء: 3 4 2 * + يساوي 11 و 3 4 + 2 * يساوي 14. لذلك يمكن لمكدس واحد تقييم التعبير من دون الحاجة إلى النظر مسبقًا.

Q: كيف تقسم مع الاقتطاع نحو الصفر في Python؟

استخدم int(a / b) . عامل التشغيل // يقرّب إلى الأسفل، لذا فإن -7 // 2 يساوي -4، بينما int(-7 / 2) يساوي -3. القسمة باستخدام الأعداد العشرية دقيقة بما يكفي هنا لأن القيم تقع ضمن 32 بت. بالنسبة إلى الأعداد الصحيحة الكبيرة جدًا، اقسم القيم المطلقة باستخدام // وأعد الإشارة بعدها.

متوسطالمكدس

+10

لديك تعبير حسابي بترميز بولندي عكسي، على هيئة مصفوفة من الرموز. في هذا الترميز يأتي كل عامل بعد معامليْه مباشرةً، لذا فإن 3 4 + تعني 3 + 4، و3 4 + 2 * تعني (3 + 4) * 2، دون الحاجة إلى أقواس. كل رمز هو عدد صحيح أو أحد العوامل + و- و* و/.

احسب قيمة التعبير وأعِدها. تحتفظ القسمة بالجزء الصحيح فقط، وتُقرّب باتجاه الصفر: 7 / 2 تساوي 3، و-7 / 2 تساوي -3.

الدالة

evalRPN(tokens: string-array) → integer

tokensstring-array: الأعداد والعوامل في التعبير، بالترتيب
تُرجعinteger: قيمة التعبير

القيود

1 ≤ tokens.length ≤ 10⁴
كل رمز هو + أو - أو * أو /، أو عدد صحيح من -200 إلى 200 مكتوب بالنظام العشري، مع إشارة سالب في البداية إذا كان سالبًا.
tokens تعبير صالح بالتدوين البولندي العكسي.
لا تحدث أي قسمة على صفر، وكل قيمة وسيطة ونهائية أكبر من -2³¹ وأقل من 2³¹.

أمثلة

المدخلات: tokens = ["8", "3", "-", "4", "*"]
المخرجات: 20
الشرح: يُطبَّق - على العددين اللذين يسبقانه حسب ترتيبهما، 8 ثم 3، لذا يعطي 5، وليس -5. ثم يضرب * ذلك العدد 5 في 4، فيكون الناتج 20.

المدخلات: tokens = ["6", "2", "9", "3", "/", "-", "*"]
المخرجات: -6
الشرح: يستخدم العامل الأول، /، أحدث قيمتين: 9 مقسومة على 3 تساوي 3. ثم يحسب - ناتج طرح 3 من 2، وهو -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

ما هو التعقيد الزمني لتقييم تدوين بولندي عكسي؟

يعمل حل المكدس في زمن 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", "*"]

المتوقع