خوارزمية «ساحة تحويل السكك الحديدية» لحساب العبارات الرياضية

خوارزمية ساحة تحويل السكك الحديدية (Shunting-yard algorithm) هي خوارزمية يمكن استخدامها لتحليل العبارات الرياضية المكتوبة بالصيغة المعتادة المعروفة (مثل “5 + 3”)، والتي تدعى ترميزا ضمنيا (Infix notation)، وتحويلها إلى عبارات مكتوبة بصيغة مثل “5 3 +” حيث يكتب رمز كل عملية بعد معاملاتها (الأعداد) التي تعمل عليها. تدعى هذه الصيغة الأخيرة ترميز بولنديا معكوسا (Reverse Polish notation)

تعمل الخوارزمية بتوظيف بنية بيانات مشهورة وبسيطة وهي المكدس (stack)، حيث تخزن مكدسين (مكدس “عمليات” ومكدس “مخرجات”) وتحلل كل عملية ومعاملاتها وتضيفها إلى واحد من المكدسين بترتيب يراعي قواعد أولوية العمليات المعروفة في الرياضيات¹. ينتج لدينا بعدها مكدس واحد غير فارغ (وهو مكدس المخرجات) يمكن ببساطة إخراج العمليات منه بترتيب من يدخل أخيراً يخرج أولاً (Last-In-First-Out)‏ وإخراج معاملات كل عملية وإجراء العملية ثم إدخال النتيجة إلى المكدس مجددا واستخدامها كمعامل للعمليات المتبقية، ليبقى لدينا في النهاية عدد واحد في مكدس المخرجات (بافتراض أن العبارة ليس فيها أي أخطاء) هو نتيجة العبارة الرياضية كلها. كما يمكننا إنتاج عبارة جديدة بالصيغة البولندية المعكوسة من هذا المكدس بدون حساب النتيجة، إذا كان ما يهمنا هو تحويل العبارة فقط وليس حساب نتيجتها.

أمثلة

تعمل الخوارزمية على مكدسين اثنين كما قلنا: لندعُ الأول مكدس العمليات (operations)، والثاني مكدس المخرجات (output). لنأخذ العبارة التالية البسيطة كمثال عن كيفية عمل الخوارزمية: “3 + 7”.

1) نصادف أولا الرقم 3 ونضيفه إلى مكدس المخرجات.

operations: 
output: 3

2) ثم تأتي عملية الجمع فنضيفها إلى مكدس العمليات.

operations: +
output: 3

3) أخيرا يأتي الرقم 7 فنضيفه إلى مكدس المخرجات.

operations: +
output: 3 7

4) انتهينا من قراءة العبارة. الآن نخرج كل العمليات من مكدس العمليات بترتيب LIFO كما هو مبدأ عمل المكدس ونضيفها إلى مكدس المخرجات.

operations:
output: 3 7 +

5) تنتج لدينا العبارة التالية: “3 7 +”

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

كان هذا مثالا بسيطا. لنأخذ مثالا أكثر تعقيدا بقليل: “7 * 2 + 3”.

1) نضيف العدد 7 إلى مكدس المخرجات.

operations: 
output: 7

2) نضيف العملية * إلى مكدس العمليات.

operations: *
output: 7

3) نضيف العدد 2 إلى مكدس المخرجات.

operations: *
output: 7 2

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

operations: +
output: 7 2 *

5) نضيف بعدها العدد 3 إلى مكدس المخرجات.

operations: +
output: 7 2 * 3

6) انتهينا من قراءة العبارة. ننقل كل العمليات المتبقية من مكدس العمليات إلى مكدس المخرجات.

operations:
output: 7 2 * 3 +

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

operations:
output: 14 3 +

نجري الآن عملية الجمع لنحصل على 17 كناتج نهائي للعبارة.

لنأخذ عبارة شبيهة لكن هذه المرة مع أقواس لنرى كيف تتعامل معها الخوارزمية: “7 * (2 + 3)”.

1) نضيف العدد 7 إلى مكدس المخرجات.

operations: 
output: 7

2) نضيف العملية * إلى مكدس العمليات.

operations: *
output: 7

3) نضيف القوس الأيسر “)” إلى مكدس العمليات:

operations: * (
output: 7

4) نضيف العدد 2 إلى مكدس المخرجات.

operations: * (
output: 7 2

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

operations: * ( +
output: 7 2

6) نضيف العدد 3 إلى مكدس المخرجات.

operations: * ( +
output: 7 2 3

8) نصادف القوس الأيمن “(“. لا نضيفه لأي من المكدسات، بل نبدأ بإخراج عمليات من مكدس العمليات وننقلها إلى مكدس المخرجات حتى نصادف قوسا أيسر “)” أو يصبح مكدس العمليات فارغا تماما بدون أن نجد قوسا أيسر (في هذه الحالة هناك قوس ناقص يمكننا إعلام المستخدم عنه). بفرض أننا وجدنا قوسا أيسر، نخرجه من مكدس العمليات ونتخلص منه.

operations: *
output: 7 2 3 +

9) انتهينا من قراءة العبارة. ننقل كل العمليات المتبقية من مكدس العمليات إلى مكدس المخرجات.

operations:
output: 7 2 3 + *

إذا نردنا حساب النتيجة فسنتبع الخطوات التالية:

1) نبدأ بعملية الضرب ونجد أنها تعتمد على عملية قبلها وهي عملية الجمع.

2) نحسب عملية الجمع (“2 3 +”) لنحصل على العبارة التالية:

3) حصلنا على معاملات عملية الضرب العددية. نجري الآن العملية لنحصل على 35 كناتج نهائي.

لنأخذ مثالا آخر يوضح فكرة مهمة قد يسهو عنها من يريد تطبيق الخوارزمية (مثلي): “5 - 2 - 2”

1) نضيف العدد 5 إلى مكدس المخرجات.

operations:
output: 5

2) نضيف عملية الطرح إلى مكدس العمليات.

operations: -
output: 5

3) نضيف العدد 2 إلى مكدس المخرجات.

operations: -
output: 5 2

4) نأتي لعملية الطرح الثانية. ننظر لآخر عملية في مكدس العمليات ونجد العملية نفسها، لذلك فأولويات العمليتين متساويتان طبعا. ما العمل الآن؟ هل (1) نضيف العملية الحالية إلى مكدس العمليات أم (2) يجب أولا أن ننقل العملية السابقة من مكدس العمليات إلى مكدس المخرجات ثم نفعل ذلك؟ فكر بما سيحدث في كلا الحالتين وجرب رسم حالة المكدسين كما نفعل هنا على ورقة قبل الاستمرار بالقراءة.

دعنا نجرب كلا الخيارين ونرى:

إذا اخترنا (1) فسننتهي بالعبارة البولندية المعكوسة “5 2 2 - -”.

إذا اخترنا (2) فستنتج العبارة “5 2 - 2 -”.

ناتج (1) هو 5 بينما ناتج (2) هو 1. من البديهي أن الخيار (2) هو الصحيح حسب قواعد الرياضيات المعتادة.

عبارة “5 - 2 - 2” في الحقيقة يتم تحليلها كأنها كتبت “(5 - 2) - 2”.

هناك عمليات مثل الطرح والقسمة تعارف الناس على حسابها بهذا الشكل، حيث يتم تجميع عوامل كل عملية بدءًا من اليسار، بينما هناك عمليات تُحسَب من اليمين (كما سنرى لاحقا). يعرف مفهوم اتجاه إجراء العمليات المتطابقة باسم «ترابط العمليات» (operator associativity) في لغات البرمجة. تدعى عمليات مثل الطرح والقسمة left-associative operators، بينما يقال لعمليات تُجمَّع من اليمين إلى اليسار إنها right-associative operators.

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

operations: -
output: 5 2 -

لنستمر بتحليل العبارة:

5) نضيف العدد 2 إلى مكدس المخرجات.

operations: -
output: 5 2 - 2

6) انتهينا من قراءة العبارة. ننقل كل العمليات من مكدس العمليات إلى مكدس المخرجات لنحصل على:

operations:
output: 5 2 - 2 -

لنأخذ مثالا آخر يوضح فكرة ترابط العمليات أكثر: “2^2^3” (يدل ^ هنا على عملية الرفع إلى أس)

1) نضيف العدد 2 إلى مكدس المخرجات.

operations:
output: 2

2) نضيف العملية ^ إلى مكدس العمليات.

operations: ^
output: 2

3) نضيف العدد 2 إلى مكدس المخرجات.

operations: ^
output: 2 2

4) نأتي لعملية الرفع إلى أس الثانية. ننظر لآخر عملية في مكدس العمليات ونجد العملية نفسها، لذلك فأولويات العمليتين متساويتان. في المثال السابق نقلنا آخر عملية في مكدس العمليات إلى مكدس المخرجات لأن عملية الطرح left-associative، لكن هل عملية الرفع إلى أس كذلك؟ غالبا لا، عملية الرفع إلى أس تعمل من اليمين إلى اليسار، أي right-associative.² هذا يعني أن عبارة “2^2^3” يتم تحليلها كـ “2^(2^3)”. لذلك سنضيف العملية الحالية إلى مكدس العمليات ونستمر ببساطة.

operations: ^ ^
output: 2 2

5) نضيف العدد 3 إلى مكدس المخرجات.

operations: ^ ^
output: 2 2 3

6) انتهينا من قراءة العبارة. ننقل كل العمليات من مكدس العمليات إلى مكدس المخرجات.

operations:
output: 2 2 3 ^ ^

نتجت لدينا العبارة البولندية المعكوسة “2 2 3 ^ ^” والتي ناتجها هو 256، بينما لو عاملنا عملية الرفع إلى أس على أنها left-associative فستنتج العبارة “2 2 ^ 3 ^” والتي ناتجها هو 64.

استعراض تفاعلي للخوارزمية

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

اضغط على هذا الرابط إذا كانت نافذة البرنامج لا تظهر كليا أو هناك مشكلة في عرضها: https://www.abdnh.net/shunting-yard-algorithm-demo/?lang=ar

خطوات عمل الخوارزمية

بعد أن نظرنا إلى عدة أمثلة، يمكننا استنتاج خطوات عمل الخوارزمية وكتابتها بشكل شبه منهجي على النحو التالي:

1) نقرأ حدا من حدود العبارة الرياضية المدخلة إذا كان ما يزال هناك حدود.

2) إذا كان الحد عددا نضيفه إلى مكدس المخرجات

3) إذا كان الحد عملية غير الأقواس (لنقل لها O₁)، نبدأ بنقل كل عملية O₂ من مكدس العمليات إلى مكدس المخرجات ما دامت (1) ليست أقواسا و (2) أولويتها أعلى من أولوية O₁ أو للعمليتين أولويات متساوية و عملية O₁ هي left-associative، ثم ندخل O₁ إلى مكدس العمليات. يمكن التعبير عن الشرط بالسودوكود:

(o2 is not a parenthesis) AND ((o2.precedence > o1.precedence) OR (o2.precedence == o1.precedence && o1 is left-associative))

4) إذا كان الحد قوسا أيسر “)”، نضيفه إلى مكدس العمليات.

5) إذا كان الحد قوسا أيمن “(“،نبدأ بنقل عمليات من مكدس العمليات إلى مكدس المخرجات ما دامت ليست أقواسا يسرى، ثم نخرج القوس الأيسر من مكدس العمليات وتخلص منه. إذا لم يوجد قوس أيسر فهناك خطأ في العبارة.

6) بعد الانتهاء من قراءة كل حدود العبارة، ننقل كل العمليات من مكدس العمليات إلى مكدس المخرجات.

ينتج لدينا في مكدس المخرجات عبارة رياضية بالصيغة البولندية المعكوسة بعد هذه العملية. إذا كان هدفنا هو حساب ناتج العملية وليس إنتاج عبارة بصيغة مختلفة، فبدل عملية نقل العمليات إلى مكدس المخرجات المتكررة في عدة خطوات (3، 5، 6)، يمكننا ببساطة إخراج عوامل كل عملية من هذه العمليات وحساب ناتجها وإضافته إلى مكدس المخرجات.

تطبيق للخوارزمية

لتطبيق للخوارزمية بلغة C، انظر هذه المكتبة التي كتبتها: https://github.com/abdnh/math-eval

وصلات خارجية

سأضع هنا وصلات إنترنت للاستزادة أكثر حول الموضوع:

• فيديوهات يوتيوب على قناة Computerphile:
  • Reverse Polish Notation and The Stack
  • Reverse Polish Grows on Trees