تحويل التدوين البولندي العكسي

Question

هل هناك أي طريقة لتفسير التدوين البولندي العكسي إلى تدوين رياضي "عادي" عند استخدام C++ أو C#؟أنا أعمل في شركة هندسية، لذا فهم يستخدمون RPN أحيانًا ونحتاج إلى طريقة لتحويله.أي اقتراحات؟

Answer 1

نعم.فكر في كيفية عمل حاسبة RPN.الآن، بدلاً من حساب القيمة، يمكنك بدلاً من ذلك إضافة العملية إلى الشجرة.لذلك، على سبيل المثال، 2 3 4 + *, ، عندما تصل إلى +، بدلاً من وضع 7 في المكدس، تضع (+ 3 4) على المكدس.وبالمثل عندما تصل إلى * (ستبدو مجموعتك كما هي 2 (+ 3 4) * في تلك المرحلة)، يصبح (* 2 (+ 3 4)).

هذا هو تدوين البادئة، والذي يتعين عليك بعد ذلك تحويله إلى infix.اجتياز الشجرة من اليسار إلى اليمين، العمق أولا.بالنسبة لكل "مستوى داخلي"، إذا كانت أسبقية العامل أقل، فسيتعين عليك وضع العملية بين قوسين.وهنا ستقول إذن 2 * (3 + 4), ، لأن + له أسبقية أقل من *.

أتمنى أن يساعدك هذا!

يحرر:هناك دقة (بصرف النظر عن عدم النظر في العمليات الأحادية في ما سبق):لقد افترضت مشغلي اليسار الترابطي.للحق النقابي (على سبيل المثال، **)، ثم تحصل على نتائج مختلفة ل 2 3 4 ** ** ⇒ (** 2 (** 3 4)) عكس 2 3 ** 4 ** ⇒ (** (** 2 3) 4).

عند إعادة بناء infix من الشجرة، تظهر كلتا الحالتين أن الأسبقية لا تتطلب وضع قوسين، ولكن في الواقع تحتاج الحالة الأخيرة إلى وضع قوسين ((2 ** 3) ** 4).لذلك، بالنسبة لمشغلي الاقتران الأيمن، يجب أن يكون للفرع الأيسر أسبقية أعلى (بدلاً من أعلى أو يساوي) لتجنب الأقواس.

هناك أيضًا أفكار أخرى مفادها أنك تحتاج إلى أقواس للفرع الأيمن من - و / المشغلين أيضا.

Answer 2

يتم استخدام خوارزمية Shunting Yard لتحويل Infix (أي.جبري) إلى RPN.وهذا عكس ما تريد.

هل يمكن أن تعطيني مثالاً على إدخال RPN الخاص بك؟أنا مستخدم/مبرمج مخضرم لآلة حاسبة HP.أفترض أن لديك مكدسًا يحتوي على جميع المدخلات والمشغلين.أعتقد أنك بحاجة إلى إعادة بناء شجرة التعبير ثم اجتياز الشجرة لإنشاء نموذج infix.

Answer 3

لا تحتوي لغة C# على دعم مدمج لتحليل الترميز البولندي العكسي (RPN). ستحتاج إلى كتابة المحلل اللغوي الخاص بك، أو العثور على واحد عبر الإنترنت.

هناك العشرات من البرامج التعليمية لتحويل نموذج postfix (RPN) إلى infix (المعادلة الجبرية).نلقي نظرة على هذا, ، ربما تجده مفيدًا ويمكنك محاولة "الهندسة العكسية" له لتحويل تعبيرات postfix إلى نموذج infix، مع الأخذ في الاعتبار أنه يمكن أن يكون هناك العديد من تدوينات infix لرمز لاحق محدد.هناك عدد قليل جدًا من الأمثلة المفيدة التي تناقش بالفعل تحويل postfix إلى infix.إليك إدخالًا مكونًا من جزأين وجدته مفيدًا جدًا.كما أن لديها بعض التعليمات البرمجية الزائفة:

• من PostFix إلى Infix:تحويل RPN إلى تعبيرات جبرية
• Postfix إلى Infix، الجزء 2:إضافة الأقواس

Answer 4

إذا كنت تستطيع قراءة روبي، ستجد بعض الحلول الجيدة لهذا هنا

Answer 5

أحد الأساليب هو أخذ المثال من الفصل الثاني من كتاب كتاب التنين والذي يشرح كيفية كتابة محلل للتحويل من تدوين infix إلى postfix وعكسه.

Answer 6

إذا كان لديك نص مصدر (سلسلة/نصوص) تريد تحويله من RPN (تدوين لاحق) إلى "تدوين عادي" (infix)، فمن المؤكد أن هذا ممكن (وربما ليس صعبًا للغاية).

تم تصميم RPN للأجهزة القائمة على المكدس، حيث أن الطريقة التي تم بها تمثيل العملية ("2 + 3" -> "2 3 +") تتناسب مع كيفية تنفيذها فعليًا على الأجهزة (اضغط "2" على المكدس، واضغط "3" "على المكدس، قم بإخراج الوسيطتين العلويتين من المكدس وأضفهما، ثم ادفعهما للخلف إلى المكدس).

في الأساس، تريد إنشاء شجرة بناء جملة من RPN الخاص بك عن طريق إنشاء التعبيرين اللذين تريد تشغيلهما على "العقد الورقية" والعملية نفسها، والتي تأتي بعد ذلك، "العقدة الأصلية".من المحتمل أن يتم ذلك من خلال النظر بشكل متكرر إلى سلسلة الإدخال الخاصة بك (قد ترغب في التأكد من أن التعبيرات الفرعية موضوعة بين قوسين بشكل صحيح لمزيد من الوضوح، إذا لم تكن كذلك بالفعل).

بمجرد حصولك على شجرة بناء الجملة هذه، يمكنك إخراج تدوين البادئة أو infix أو postfix ببساطة عن طريق إجراء ترتيب مسبق أو ترتيب لاحق أو اجتياز ترتيب لتلك الشجرة (مرة أخرى، ضع بين قوسين مخرجاتك للتوضيح إذا رغبت في ذلك).

يمكن العثور على بعض المعلومات الإضافية هنا.

Answer 7

لقد كتبت للتو نسخة في جافا، انها هنا وواحد في Objective-C، انتهى هنا.

خوارزمية محتملة:نظرًا لأن لديك مكدسًا يحتوي على الإدخال في rpn حيث يقوم المستخدم بإدخاله، على سبيل المثال.8، 9، *.يمكنك التكرار عبر المصفوفة من الأول إلى الأخير، كما تقوم دائمًا بإزالة العنصر الحالي.هذا العنصر الذي تقوم بتقييمه.إذا كان مُعاملًا، فيمكنك إضافته إلى مجموعة النتائج.عندما يكون عامل تشغيل، فإنك تقوم بإخراج مكدس النتائج مرتين (للعمليات الثنائية) للمعاملات وتكتب سلسلة النتائج في مكدس النتائج.

مع إدخال المثال "8, 9, +, 2, *"تحصل على هذه القيم في مجموعة النتائج (بين قوسين مربعين للإشارة إلى العناصر الفردية):

الخطوة 1: [8]

الخطوة 2: [8], [9]

الخطوه 3: [(8 + 9)]

الخطوة 4: [(8 + 9)], [2]

الخطوة 5: [(8 + 9) * 2]

عندما تكون مكدس الإدخال فارغًا، تكون قد انتهيت ويكون العنصر الوحيد في resultStack هو نتيجتك.(لاحظ مع ذلك أن الإدخال يمكن أن يحتوي على إدخالات متعددة أو لا معنى لها، مثل عملية بادئة:"+2 3 /".)

لا تستخدم التطبيقات الموجودة في الروابط عمدًا أي أنواع ذاتية الصنع على سبيل المثال.المشغلين أو المعاملات ولا ينطبق على سبيل المثالنمط مركب.إنها نظيفة وبسيطة بحيث يمكن فهمها بسهولة ونقلها إلى أي لغة أخرى.

يعد نقله إلى C# أمرًا مباشرًا.