Algorithms/infix prefix postfix expressions

يقدّم التعبير الرياضي B * C بعض المعلومات التي تساعد في تفسيره بطريقة صحيحة، إذ يمكن معرفة أنّ المتغير B مضروب بالمتغير C بسبب وجود العامل * في وسطهما. ويقال أنّ التعبير مرتب وسطيًا infix expression وذلك لأنّ العامل يتوسّط معاملَيْه.

ينطبق ما تقدّم على التعبير A + B * C، فالعوامل تتوسّط معاملاتها، ولكن ترتيب العوامل بهذه الطريقة يؤدي إلى ظهور مشكلة في تفسير التعبير بطريقة صحيحة، فهل سيعمل العامل + على المتغيرين A و B أولًا أم أنّ العامل * سيعمل على المتغيرين B و C أولًا؟

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

يمكن -بناءً على ما تقدّم- تفسير التعبير الرياضي A + B * C بأن يُضرب المتغيران B و C بعضهما ببعض، ثم يضاف المتغير A إلى ناتج الضرب.

يؤدي استخدام الأقواس إلى فرض الأولوية للتعبير المحاط بها، فعلى سبيل المثال تفرض الأقواس في التعبير ‎(A + B) * C إجراء عملية الجمع بين A و B قبل إجراء عملية الضرب.

ويمكن استخدام خاصية الترابطية في تفسير التعبير A + B + C إذ ستُجرى عملية الجمع بين A و B في البداية لأنّ العامل الذي يتوسّطهما موجود في الجانب الأيسر.

قد يكون ما تقدّم واضحًا بالنسبة لك، ولكن الحاسوب بحاجة إلى معرفة الترتيب الذي سيتّبعه في تنفيذ العوامل. يمكن إحاطة العمليات الرياضية بالأقواس حسب الترتيب المطلوب وتسمّى هذه التعابير بالتعابير المحاطة بالأقواس بالكامل fully parenthesized expression. يستخدم هذا النوع من التعابير زوجًا من الأقواس لكل عامل، وتصف هذه الأقواس ترتيب العمليات التي يُراد تنفيذها، وتزيل بذلك أي لبس قد يطرأ في تفسير التعبير الرياضي؛ ولا حاجة وقتئذٍ لتذكر قواعد الأولوية.

يمكن إعادة كتابة التعبير A + B * C + D ليصبح ‎((A + (B * C)) + D)‎ وذلك لنبيّن بأنّ عملية الضرب ستُجرى في البداية وتتبعها عملية الجمع في الجانب الأيسر. ويمكن إعادة كتابة التعبير A + B + C + D ليصبح (((A + B) + C) + D)‎ وذلك لأنّ عمليات الجمع تترابط مع بعضها البعض من اليسار إلى اليمين.

التعابير المرتبة قبليًا والمرتبة بعديًا

هناك نوعان آخران مهمّان من التعابير الرياضية، هما التعابير المرتّبة قبليًا والتعابير المرتّبة بعديًا.

يؤدي نقل العامل + في التعبير A + B إلى بداية التعبير (ليصبح ‎+ A B) إلى تحويله من تعبير مرتّب وسطيًا إلى تعبير مرتّب قبليًا Prefix، والذي يتطلّب أن يسبق كلّ عاملٍ المعاملين الذين يعمل عليهما. كذلك يؤدّي نقل العامل نفسه إلى نهاية التعبير (ليصبح ‎A B +‎) إلى تحويله إلى تعبير مرتّب بعديًا Postfix، والذي يتطلّب أن يتلو كلّ عاملٍ المعاملين الذين يعمل عليهما.

يمكن ترتيب التعبير A + B * C قبليًا ليصبح ‎+ A * B C، ويلاحظ أنّ عامل الضرب يأتي مباشرة قبل المعاملين A و B ليشير بذلك إلى أولوية عامل الضرب على عامل الجمع. ويلاحظ كذلك أنّ عامل الجمع يظهر قبل المعامل A ونتيجة عملية الضرب.

ويمكن ترتيب التعبير السابق بعديًا ليصبح ‎A B C * +‎. يلاحظ أنّ ترتيب العمليات لم يتغير عن التعبير السابق؛ وذلك لأنّ عامل الضرب يظهر قبل المعاملين B و C مباشرة، ليشير بذلك إلى أولويته على عامل الجمع.

ويلاحظ هنا أنّ تحريك العامل إلى أحد جانبي معامليه لن يؤدي إلى الإخلال في ترتيب المعاملين وستبقى العلاقة بينهما ثابتة.

إنّ مقارنة التعبيرين السابقين بالتعبير المرتّب وسطيًا ‎(A + B) * C تبيّن أنّ هذا التعبير يحتاج إلى الأقواس ليفرض إجراء عملية الجمع قبل عملية الضرب، ولكنّ استخدام الترتيب القبلي في كتابة هذا التعبير يؤدي إلى تحريك عامل الجمع ليصبح قبل معامليه (‎+ A B) وستصبح نتيجة هذه العملية المعامل الأول لعملية الضرب، والمعامل الثاني هو C. وبنفس الطريقة يؤدي استخدام الترتيب البعدي في كتابة هذا التعبير إلى إجراء عملية الضرب على معاملين هما ناتج عملية الجمع والمعامل C.

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

تحويل التعبير المرتّب وسطيًا إلى تعبير مرتّب بعديًا

تحوّل هذه الخوارزمية التعبير المرتّب وسطيًا إلى تعبير مرتّب بعديًا باستخدام المكدس.

تحويل التعبير المرتّب قبليًا إلى تعبير مرتب وسطيًا

تحوّل هذه الخوارزمية التعبير المرتب قبليًا إلى تعبير مرتّب بعديًا.

تحويل التعبير المرتّب قبليًا إلى تعبير مرتب بعديًا

تحوّل هذه الخوارزمية التعبير المرتب قبليًا إلى تعبير مرتّب بعديًا.

تحويل التعبير المرتّب بعديًا إلى تعبير مرتب وسطيًا

تحوّل هذه الخوارزمية التعبير المرتب بعديًا إلى تعبير مرتّب وسطيًا.

تحويل التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا

تحوّل هذه الخوارزمية التعبير المرتب بعديًا إلى تعبير مرتّب قبليًا.

مصادر

• الفصل 4.9 من كتاب Problem Solving with Algorithms and Data Structures using Python لمؤلّفيه Brad Miller و David Ranum و Luther College.