RPN: خوارزمية والأساليب والأمثلة

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

أقحم

جميع المبرمجين، ومعظم الطلاب على دراية مع استخدام المشغلين. على سبيل المثال، القيم التعبير س + الجمع للمتغيرات x و y علامة الجمع المستخدمة. أقل شهرة هو حقيقة أن هذا هو استعار من الرياضيات التدوين، ودعا أقحم التدوين، في الواقع، هو مشكلة كبيرة بالنسبة للآلات. يتلقى هذا المشغل كما يتم تسجيل إدخال قيمتين على اليسار واليمين. في البرمجة تدوين تستخدم اختياريا مع عمليات علامات. على سبيل المثال، س + ص يمكن كتابة بوصفها وظيفة من أمثال (س، ص)، الذي المترجم في نهاية المطاف تحويل أقحم التدوين. ومع ذلك، والجميع يعرف الرياضيات جيدة جدا على عدم استخدام التعابير الحسابية، والتي تشكل نوعا من مصغرة اللغة الداخلية تقريبا في كل لغة البرمجة.

صيغة الترجمة

أصبحت أولى ناجحة حقا لغة البرمجة فورتران ذلك إلى حد كبير بسبب التعبير الحسابي (أي صيغة ..) وتحويلها (البث) في القانون، ومن هنا جاءت تسميته من ذلك - صيغة الترجمة. وقبل ذلك، كان عليهم أن يكتب، على سبيل المثال، مطوية في شكل وظائف (وتتكاثر (ب، ج)). في مشكلة كوبول تنفيذ صيغة تحويل التلقائي اعتبر صعبة للغاية لأن المبرمجين زيارتها لكتابة أشياء مثل اضافة A إلى B Mutliply بواسطة C.

ما هو الخطأ في أقحم؟

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

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

البادئة وبوستفيكس التدوين

اثنين من البدائل الأكثر شهرة هو لتسجيل المشغل قبل أو بعد المعاملات لها. وهي المعروفة باسم البادئة وبوستفيكس التدوين. اخترع منطقي يان لوكاسيفيش أول واحد في عام 1920. كان يعيش في بولندا، لذلك يسمى سجل البولندية. بوستفيكس نسخة، على التوالي، ودعا عكسي البولندية الترقيم (ARF). والفرق الوحيد بين هاتين الطريقتين هو الاتجاه الذي لقراءة سجل (من اليسار إلى اليمين أو من اليمين إلى اليسار)، لذلك يكفي أن تنظر في التفاصيل واحد منهم فقط. هو مكتوب المشغل OPN بعد المعاملات لها. وهكذا، فإن التعبير AB + يمثل مثالا RPN لA + B.

عدد غير محدود من المعاملات

ميزة فورية من التدوين هو أنه يلخص المشغل ن أديك وأقحم التدوين هو حقا يعمل فقط مع اثنين من المعاملات، ر. E. هل تصلح بطبيعتها فقط لعمليات ثنائي. على سبيل المثال، ABC @ هو التعبير البولندي العكسي باستخدام علامة تكاملي ثلاثي وهو الحد الأقصى لقيمة A، B و C. وفي هذه الحالة يعمل المشغل على اليسار من المعامل الثلاثة نفسها، ويتوافق مع استدعاء دالة @ (A، B، C). إذا كنت تحاول كتابة الرمز @ كما أقحم، مثل A @ BC أو شيء من هذا القبيل، يصبح من الواضح أنه ببساطة لا يعمل.

إعطاء الأولوية حسب الترتيب

RPN لديها ميزة أخرى في أن الأولوية للشركات يمكن أن يمثله ترتيب مظهرهم. في نفس الوقت لا تحتاج الأقواس، على الرغم من أنها قد تكون مدرجة في عمليات الأحرف لتسهيل التحويل من ترميز مقحم. على سبيل المثال، AB + C * - لا لبس فيه أي ما يعادل (A + B) * C، لذلك لا يمكن حساب الضرب حتى إضافة المنجز، الذي يعطي المعامل الثاني للتكاثر. وهذا هو، إذا كان محسوب AB + C * قبل مشغل واحد في وقت واحد، وحصلنا على AB + C * -> (AB +) * C -> (A + B) * C.

خوارزمية حسابية

المشغل OPN تبدو هي نفسها بوصفها وظيفة التي تأخذ كوسائط قيمتين مكتوبة على يسارها. وبالإضافة إلى ذلك، بل هو تدوين الطبيعي للاستخدام في لغات البرمجة، وطريقة حسابها يتوافق مع عمليات المكدس ويتم التخلص من الحاجة للتحليل. على سبيل المثال، فإن صواعق في التعبير 5 + 6 * 7 تبدو وكأنها 5، 6، 7 *، +، وأنه يمكن حساب ببساطة عن طريق المسح الضوئي من اليسار إلى اليمين وكتابة القيم في المكدس. كلما علامة مشتركة من العملية، يتم اختيارهم بواسطة العنصر العلوي 2 من ذاكرة الكمبيوتر، ويستخدم المشغل وعادت النتيجة إلى الذاكرة. عندما النتيجة النهائية للتعبير حساب سوف يكون في الجزء العلوي من المكدس.

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

• S = () 5، 6، 7، *، + 5 وضعت على المكدس.
• S = (5) 6، 7، *، + 6 وضعت على المكدس.
• S = (5، 6)، 7 * 7 + وضع المكدس.
• S = (5، 6، 7)، * 2 + اختيار القيم من المكدس، واستخدام * ووضع النتيجة في كومة.
• S = (5، 6 * 7) = (5، 42) + 2 القيم المحددة من المكدس، لتطبيق + ووضع النتيجة في كومة.
• S = (5 + 42) = اكتمال (47) الحساب، ويتم تخزين النتيجة في الجزء العلوي من المكدس.

هذه الخوارزمية يمكن التحقق من RPN مرارا وتكرارا، ولكن في كل مرة أنها ستعمل، بغض النظر عن مدى تعقيد التعبير الحسابي.

ترتبط OPN ومداخن عن كثب. يوضح هذا المثال كيفية استخدام الذاكرة لحساب قيمة التدوين البولندي العكسي. أقل وضوحا هو أنه يمكنك استخدام المكدس، تحويل التعبير أقحم القياسي في الفشل الكلوي الحاد.

أمثلة من لغات البرمجة

أدركت باسكال RPN مثل هذه (يظهر جزء من البرنامج).

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

toktype: = الأسطوانات.

قراءة (ق)؛

إذا ج في [ '+'، '-'، '*'، '/'] ثم تبدأ

إذا eoln ثم CN: = '' آخر قراءة (CN)؛

إذا CN = '' ثم

حالة

'+': Toktype: = إضافة. '-': toktype: = الفرعية.

'*': Toktype: = MUL. '/': Toktype: = شعبة

نهاية

آخر يبدأ

إذا كان = '-' ثم SGN: = -1 خطأ آخر: = ج <> '+'؛

مع: = CN

نهاية

ينتهي.

إذا (لا خطأ) و (toktype = الأسطوانات) ثم getnumber.

إذا toktype <> الأسطوانات ثم تبدأ

ذ = البوب. س: = البوب.

إن لم يكن خطأ ثم

حالة toktype من

إضافة: ض: = س + ذ؛ الفرعي: ض: = س-ص. MUL: ض: = س * ذ؛ شعبة: ض: = س / ص

نهاية

دفع (ض)؛

RPN C-تنفيذ (الجزء المعروض البرنامج):

ل(ق = strtok (ق، ث)؛ ق؛ ق = strtok (0، ث)) {

و= strtod (ق، وه).

إذا (ه> الصورة) دفع (أ)؛

# تعريف rpnop (خ) printf ( "٪ ج:" *، ق)، ب = البوب ()، و= البوب ()، ودفع (خ)

الا اذا (ق * == '+') rpnop (أ + ب)؛

الا اذا (ق * == '-') rpnop (أ - ب).

الا اذا (ق * == '*') rpnop (أ * ب)؛

الا اذا (ق * == '/') rpnop (أ / ب).

rpnop #undef

}

تطبيقات الأجهزة

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

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

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

فما هو معنى النكات حول النقانق عكسي البولندية؟

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