يمكن كل RPN تعبيرات تكون ممثلة مثل أن جميع المشغلين تظهر على اليسار و جميع المعاملات تظهر على اليمين ؟

Question

لقد أقنعت نفسي أنها لا يمكن.

خذ على سبيل المثال:

4 4 + 4 /

المكدس:4 المكدس:4 4 4 + 4 = 8 المكدس:8 المكدس:8 4 8 / 4 = 2 المكدس:2

هناك نوعان من الطرق التي يمكنك كتابة التعبير أعلاه مع نفس مشغلي المعاملات مثل هذه المعاملات كل ما يأتي أولا:"4 4 4 + /" و "4 4 4 / +"ولا تقييم 2.

"4 4 4 + /" المكدس:4 المكدس:4 4 المكدس:4 4 4 4 + 4 = 8 المكدس:4 8 4 / 8 = 0.5 المكدس:0.5

"4 4 4 / +" المكدس:4 المكدس:4 4 المكدس:4 4 4 4 / 4 = 1 المكدس:4 1 4 + 1 = 5 المكدس:5

إذا كان لديك القدرة على تبديل العناصر على المكدس ثم نعم, هذا ممكن, وإلا, لا.

الأفكار ؟

Answer 1

النظر في تعبير جبري:

(a + b) * (c + d)

واضح الترجمة إلى RPN ليكون:

a b + c d + *

حتى مع عملية مقايضة المتاحة ، لا أعتقد أن هناك طريقة لجمع كل المشغلين على اليمين:

a b c d +
a b S

حيث S هو مجموع c و d.عند هذه النقطة, لا يمكنك استخدام واحدة عملية مقايضة للحصول على كل من a و b في مكان + العملية.بدلا من ذلك, كنت في حاجة أكثر تطورا كومة العملية (مثل لفة) للحصول على a و b في المكان الصحيح.أنا لا أعرف ما إذا كانت لفة العملية سيكون كافيا لجميع الحالات سواء.

Answer 2

في الواقع, لقد ليس فقط الرد ولكن دليل قاطع أيضا ، عن طريق فحص مضاد سبيل المثال وهو ما يكفي لدحض الافتراض الضمني في العنوان.

Answer 3

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

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

أنا لا أعرف إذا كان هذا له أي التطبيق العملي.انها على الارجح جدا فعالة طريقة ترميز وفك ترميز تعبيرات.ولكن ممارسة أكاديمية ، أنا متأكد من أنها غير قابلة للتطبيق.

Answer 4

يكفي أن تظهر واحدة لا يمكن أن لكي اقول لكم الجواب على هذا.

إذا لم تتمكن من إعادة ترتيب كومة المحتويات ، ثم التعبير (2+4)*(7+8) لا يمكن إعادة ترتيبها.

2 4 + 7 8 + *

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

على الأقل أعتقد ذلك.