خوارزمية ساحة التحويل

في علم الحاسوب ، تُعدّ خوارزمية ساحة التحويل طريقةً لتحليل التعبيرات الحسابية أو المنطقية، أو مزيج منهما، المُحددة باستخدام تدوين الوسط . ويمكنها إنتاج سلسلة تدوين لاحقة، تُعرف أيضًا باسم تدوين بولندي معكوس (RPN)، أو شجرة بناء جملة مجردة (AST). ^{[ 1 ]} ابتكر هذه الخوارزمية إدسكار ديكسترا ، ونُشرت لأول مرة في نوفمبر 1961، ^{[ 2 ]} وسُميت بهذا الاسم لأن طريقة عملها تُشبه طريقة عمل ساحة تحويل السكك الحديدية .

على غرار تقييم RPN، تعتمد خوارزمية ساحة التحويل على المكدس . تُعدّ التعبيرات الوسطية شكلاً من أشكال الترميز الرياضي المألوف لدى معظم الناس، مثل "3 + 4" أو "3 + 4 × (2 − 1)" . للتحويل، يوجد متغيران نصيان ( سلاسل نصية ): المدخلات والمخرجات. يوجد أيضًا مكدس يحتوي على المعاملات التي لم تُضَف بعد إلى قائمة انتظار المخرجات. للتحويل، يقرأ البرنامج كل رمز بالترتيب وينفذ عمليةً بناءً على ذلك الرمز. ستكون نتيجة الأمثلة السابقة ( بالترميز البولندي العكسي ) "3 4 +" و "3 4 2 1 − × +" على التوالي.

ستقوم خوارزمية ساحة المناورة بتحليل جميع التعبيرات الوسطية الصحيحة بشكل صحيح، لكنها لا ترفض جميع التعبيرات غير الصحيحة. على سبيل المثال، "1 2 +" ليس تعبيرًا وسطيًا صحيحًا، ولكنه سيُحلل على أنه "1 + 2" . مع ذلك، يمكن للخوارزمية رفض التعبيرات التي تحتوي على أقواس غير متطابقة.

تم تعميم خوارزمية ساحة التحويل لاحقًا إلى تحليل أسبقية المشغل .

1. المدخلات: 3 + 4
2. قم بدفع الرقم 3 إلى قائمة الإخراج (يتم دفع أي رقم يتم قراءته إلى قائمة الإخراج)
3. ادفع علامة الجمع (+) (أو معرّفها) إلى مكدس العمليات
4. أضف الرقم 4 إلى قائمة الإخراج
5. بعد قراءة التعبير، قم بإزالة عوامل التشغيل من المكدس وأضفها إلى الناتج.

   في هذه الحالة يوجد واحد فقط، "+".

6. الناتج: 3 4 +

هذا يُظهر بالفعل بعض القواعد:

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

رسم توضيحي للخوارزمية، باستخدام تقاطع سكة ​​حديد ثلاثي الاتجاهات . تتم معالجة المدخلات رمزًا رمزًا: إذا وُجد متغير أو رقم، يُنسخ مباشرةً إلى المخرجات (أ)، (ج)، (هـ)، (ح). إذا كان الرمز عاملًا، يُضاف إلى مكدس العوامل (ب)، (د)، (و). إذا كانت أسبقية العامل أقل من أسبقية العوامل في أعلى المكدس، أو كانت الأسبقية متساوية وكان العامل تجميعيًا يساريًا، يُزال هذا العامل من المكدس ويُضاف إلى المخرجات (ز). أخيرًا، تُزال أي عوامل متبقية من المكدس وتُضاف إلى المخرجات (ط).

بينما توجد رموز يجب قراءتها: قراءة رمز مميز إذا كان الرمز المميز هو: - رقم : ضعها في قائمة الإخراج - دالة : قم بدفعه إلى مكدس المشغل - عامل التشغيل o 1 : بينما ( يوجد عامل o 2 في أعلى مكدس العوامل وهو ليس قوسًا مفتوحًا، و ( o 2 له أسبقية أكبر من o 1 أو ( o 1 و o 2 لهما نفس الأسبقية و o 1 هو تجميعي من اليسار)) ): قم بإخراج العنصر رقم 2 من مكدس العمليات إلى قائمة انتظار الإخراج. ادفع o 1 إلى مكدس العمليات - a "," : بينما لا يكون العامل الموجود في أعلى مكدس العوامل قوسًا مفتوحًا: قم بإخراج العامل من مكدس العوامل إلى قائمة انتظار الإخراج - قوس مفتوح (أي "("): قم بدفعه إلى مكدس المشغل - قوس أيمن (أي ")"): بينما العامل الموجود في أعلى مكدس العوامل ليس قوسًا أيسر: { تحقق من أن مكدس العمليات ليس فارغًا } /* إذا نفدت المكدس دون العثور على قوس مفتوح، فهذا يعني وجود أقواس غير متطابقة. */ قم بإخراج العامل من مكدس العوامل إلى قائمة انتظار الإخراج { تأكد من وجود قوس مفتوح في أعلى مكدس المعاملات} قم بإزالة القوس الأيسر من مكدس العمليات وتخلص منه. إذا كان هناك رمز دالة في أعلى مكدس المعاملات، فإن : قم بإخراج الدالة من مكدس العمليات إلى قائمة انتظار الإخراج /* بعد انتهاء حلقة while، انقل العناصر المتبقية من مكدس المعاملات إلى قائمة الإخراج. */ while there are tokens on the operator stack: /* إذا كان رمز المعامل في أعلى المكدس قوسًا، فهذا يعني وجود أقواس غير متطابقة. */ { assert the operator on top of the stack is not a (left) bracket} قم بإزالة العامل من مكدس العوامل إلى قائمة انتظار الإخراج

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

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

المدخلات: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3

المشغل	أسبقية	الترابط
^	4	يمين
×	3	غادر
÷	3	غادر
+	2	غادر
-	2	غادر

يرمز الرمز ^ إلى عامل الأس .

رمز مميز	فعل	الناتج (بوحدة RPN )	مكدس العمليات	ملحوظات
3	أضف الرمز المميز إلى المخرجات	3
+	أضف الرمز المميز إلى المكدس	3	+
4	أضف الرمز المميز إلى المخرجات	3 4	+
×	أضف الرمز المميز إلى المكدس	3 4	× +	علامة × لها أولوية أعلى من علامة +
2	أضف الرمز المميز إلى المخرجات	3 4 2	× +
÷	قم بإزالة المكدس إلى المخرج	3 4 2 ×	+	لكل من ÷ و × نفس الأسبقية
	أضف الرمز المميز إلى المكدس	3 4 2 ×	÷ +	للقسمة (÷) أولوية أعلى من الجمع (+).
(	أضف الرمز المميز إلى المكدس	3 4 2 ×	( ÷ +
1	أضف الرمز المميز إلى المخرجات	3 4 2 × 1	( ÷ +
-	أضف الرمز المميز إلى المكدس	3 4 2 × 1	− ( ÷ +
5	أضف الرمز المميز إلى المخرجات	3 4 2 × 1 5	− ( ÷ +
)	قم بإزالة المكدس إلى المخرج	3 4 2 × 1 5 −	( ÷ +	كرر حتى يتم العثور على "("
	كومة من البوب	3 4 2 × 1 5 −	÷ +	تجاهل الأقواس المتطابقة
^	أضف الرمز المميز إلى المكدس	3 4 2 × 1 5 −	^ ÷ +	^ لها أولوية أعلى من ÷
2	أضف الرمز المميز إلى المخرجات	3 4 2 × 1 5 − 2	^ ÷ +
^	أضف الرمز المميز إلى المكدس	3 4 2 × 1 5 − 2	^ ^ ÷ +	^ يتم تقييمها من اليمين إلى اليسار
3	أضف الرمز المميز إلى المخرجات	3 4 2 × 1 5 − 2 3	^ ^ ÷ +
نهاية	قم بإخراج جميع عناصر المكدس إلى المخرج.	3 4 2 × 1 5 − 2 3 ^ ^ ÷ +

الإدخال: الخطيئة ( الحد الأقصى ( 2, 3 ) ÷ 3 × π )

رمز مميز	فعل	الناتج (بوحدة RPN )	مكدس العمليات	ملحوظات
الخطيئة	أضف الرمز المميز إلى المكدس		الخطيئة
(	أضف الرمز المميز إلى المكدس		(الجيب)
الأعلى	أضف الرمز المميز إلى المكدس		أقصى (الجيب
(	أضف الرمز المميز إلى المكدس		( max ( sin
2	أضف الرمز المميز إلى المخرجات	2	( max ( sin
،	يتجاهل	2	( max ( sin	العامل الموجود في أعلى المكدس هو قوس مفتوح
3	أضف الرمز المميز إلى المخرجات	2 3	( max ( sin
)	قم بإزالة المكدس إلى المخرج	2 3	( max ( sin	يُكرر حتى يصبح الرمز "(" في أعلى المكدس
كومة من البوب	2 3	أقصى (الجيب	تجاهل الأقواس المتطابقة
قم بإزالة المكدس إلى المخرج	2 3 كحد أقصى	(الجيب)	الوظيفة في أعلى المكدس
÷	أضف الرمز المميز إلى المكدس	2 3 كحد أقصى	÷ ( sin
3	أضف الرمز المميز إلى المخرجات	2 3 كحد أقصى 3	÷ ( sin
×	قم بإزالة المكدس إلى المخرج	2 3 كحد أقصى 3 ÷	(الجيب)
	أضف الرمز المميز إلى المكدس	2 3 كحد أقصى 3 ÷	× ( جا
π	أضف الرمز المميز إلى المخرجات	2 3 max 3 ÷ π	× ( جا
)	قم بإزالة المكدس إلى المخرج	2 3 max 3 ÷ π ×	(الجيب)	يُكرر حتى يصبح الرمز "(" في أعلى المكدس
	كومة من البوب	2 3 max 3 ÷ π ×	الخطيئة	تجاهل الأقواس المتطابقة
	قم بإزالة المكدس إلى المخرج	2 3 max 3 ÷ π × sin		الوظيفة في أعلى المكدس
نهاية	قم بإخراج جميع عناصر المكدس إلى المخرج.	2 3 max 3 ÷ π × sin

• محلل أسبقية العمليات
• التبديل القابل للفرز على المكدس

• وصف ديكسترا الأصلي لخوارزمية ساحة التحويل
• تنفيذ البرامج المكتوبة بلغة C
• عرض توضيحي لخوارزمية ساحة التحويل في لغة Rust
• تطبيق جافا صغير يوضح خوارزمية ساحة التحويل
• تحليل التعبيرات عن طريق النزول المتكرر ، ثيودور نورفيل © 1999–2001. تاريخ الوصول 14 سبتمبر 2006.
• كود Matlab، تقييم التعبيرات الحسابية باستخدام خوارزمية ساحة التحويل