الفرق بين المراجعتين لصفحة: «Algorithms/infix prefix postfix expressions»
لا ملخص تعديل |
جميل-بيلوني (نقاش | مساهمات) ط ←مصادر |
||
| (4 مراجعات متوسطة بواسطة مستخدم واحد آخر غير معروضة) | |||
| سطر 2: | سطر 2: | ||
يقدّم التعبير الرياضي <code>B * C</code> بعض المعلومات التي تساعد في تفسيره بطريقة صحيحة، إذ يمكن معرفة أنّ المتغير <code>B</code> مضروب بالمتغير <code>C</code> بسبب وجود العامل <code>*</code> في وسطهما. ويقال أنّ التعبير مرتب وسطيًا infix expression وذلك لأنّ العامل يتوسّط معاملَيْه. | يقدّم التعبير الرياضي <code>B * C</code> بعض المعلومات التي تساعد في تفسيره بطريقة صحيحة، إذ يمكن معرفة أنّ المتغير <code>B</code> مضروب بالمتغير <code>C</code> بسبب وجود العامل <code>*</code> في وسطهما. ويقال أنّ التعبير مرتب وسطيًا infix expression وذلك لأنّ العامل يتوسّط معاملَيْه. | ||
ينطبق ما تقدّم على التعبير <code>A + B * C</code>، فالعوامل تتوسّط معاملاتها، ولكن ترتيب العوامل بهذه الطريقة يؤدي إلى ظهور مشكلة في تفسير التعبير بطريقة صحيحة، فهل سيعمل العامل <code>+</code> على المتغيرين <code>A</code> و <code>B</code> أم أنّ العامل <code>*</code> سيعمل على المتغيرين <code>B</code> و <code>C</code> | ينطبق ما تقدّم على التعبير <code>A + B * C</code>، فالعوامل تتوسّط معاملاتها، ولكن ترتيب العوامل بهذه الطريقة يؤدي إلى ظهور مشكلة في تفسير التعبير بطريقة صحيحة، فهل سيعمل العامل <code>+</code> على المتغيرين <code>A</code> و <code>B</code> أولًا أم أنّ العامل <code>*</code> سيعمل على المتغيرين <code>B</code> و <code>C</code> أولًا؟ | ||
نستطيع نحن البشر التعامل مع مثل هذا التعابير وتفسيرها بطريقة صحيحة وذلك لأنّنا نعرف أنّ العوامل تتبع مستويات مختلفة لأولوية عملها على المعاملات، فالعوامل ذات الأولوية العليا تستخدم قبل العوامل ذات الأولوية الدنيا، ولا يمكن تغيير ترتيب الأولوية هذا إلا باستخدام الأقواس. وتسبق عمليتا الضرب والقسمة في الأولوية عمليتي الجمع والطرح، وإن ظهر عاملان لهما نفس الأولوية، تكون الأولوية للعامل الموجود على الجانب الأيسر أو تستخدم خاصية الترابطية associativity. | نستطيع نحن البشر التعامل مع مثل هذا التعابير وتفسيرها بطريقة صحيحة وذلك لأنّنا نعرف أنّ العوامل تتبع مستويات مختلفة لأولوية عملها على المعاملات، فالعوامل ذات الأولوية العليا تستخدم قبل العوامل ذات الأولوية الدنيا، ولا يمكن تغيير ترتيب الأولوية هذا إلا باستخدام الأقواس. وتسبق عمليتا الضرب والقسمة في الأولوية عمليتي الجمع والطرح، وإن ظهر عاملان لهما نفس الأولوية، تكون الأولوية للعامل الموجود على الجانب الأيسر أو تستخدم خاصية الترابطية associativity. | ||
يمكن -بناءً على ما تقدّم- تفسير التعبير الرياضي <code>A + B * C</code> | يمكن -بناءً على ما تقدّم- تفسير التعبير الرياضي <code>A + B * C</code> بأن يُضرب المتغيران <code>B</code> و <code>C</code> بعضهما ببعض، ثم يضاف المتغير <code>A</code> إلى ناتج الضرب. | ||
يؤدي استخدام الأقواس إلى فرض الأولوية للتعبير المحاط بها، فعلى سبيل المثال تفرض الأقواس في التعبير <code>(A + B) * C</code> إجراء عملية الجمع بين <code>A</code> و <code>B</code> قبل إجراء عملية الضرب. | يؤدي استخدام الأقواس إلى فرض الأولوية للتعبير المحاط بها، فعلى سبيل المثال تفرض الأقواس في التعبير <code>(A + B) * C</code> إجراء عملية الجمع بين <code>A</code> و <code>B</code> قبل إجراء عملية الضرب. | ||
ويمكن استخدام خاصية الترابطية في تفسير التعبير <code>A + B + C</code> إذ ستُجرى عملية الجمع بين <code>A</code> و <code>B</code> في البداية لأنّ العامل الذي يتوسّطهما موجود في الجانب الأيسر. | ويمكن استخدام خاصية الترابطية في تفسير التعبير <code>A + B + C</code> إذ ستُجرى عملية الجمع بين <code>A</code> و <code>B</code> في البداية لأنّ العامل الذي يتوسّطهما موجود في الجانب الأيسر. | ||
قد يكون ما تقدّم واضحًا بالنسبة لك، ولكن الحاسوب بحاجة إلى معرفة الترتيب الذي سيتّبعه في تنفيذ العوامل. يمكن إحاطة العمليات الرياضية بالأقواس حسب الترتيب المطلوب وتسمّى هذه التعابير بالتعابير المحاطة بالأقواس بالكامل fully parenthesized expression. يستخدم هذا النوع من التعابير زوجًا من الأقواس لكل عامل، وتصف هذه الأقواس ترتيب العمليات | قد يكون ما تقدّم واضحًا بالنسبة لك، ولكن الحاسوب بحاجة إلى معرفة الترتيب الذي سيتّبعه في تنفيذ العوامل. يمكن إحاطة العمليات الرياضية بالأقواس حسب الترتيب المطلوب وتسمّى هذه التعابير بالتعابير المحاطة بالأقواس بالكامل fully parenthesized expression. يستخدم هذا النوع من التعابير زوجًا من الأقواس لكل عامل، وتصف هذه الأقواس ترتيب العمليات التي يُراد تنفيذها، وتزيل بذلك أي لبس قد يطرأ في تفسير التعبير الرياضي؛ ولا حاجة وقتئذٍ لتذكر قواعد الأولوية. | ||
يمكن إعادة كتابة التعبير <code>A + B * C + D</code> ليصبح <code>((A + (B * C)) + D)</code> وذلك لنبيّن بأنّ عملية الضرب ستُجرى في البداية وتتبعها عملية الجمع في الجانب الأيسر. ويمكن إعادة كتابة التعبير <code>A + B + C + D</code> ليصبح <code>(((A + B) + C) + D)</code> وذلك لأنّ عمليات الجمع تترابط مع بعضها البعض من اليسار إلى اليمين. | يمكن إعادة كتابة التعبير <code>A + B * C + D</code> ليصبح <code>((A + (B * C)) + D)</code> وذلك لنبيّن بأنّ عملية الضرب ستُجرى في البداية وتتبعها عملية الجمع في الجانب الأيسر. ويمكن إعادة كتابة التعبير <code>A + B + C + D</code> ليصبح <code>(((A + B) + C) + D)</code> وذلك لأنّ عمليات الجمع تترابط مع بعضها البعض من اليسار إلى اليمين. | ||
== التعابير المرتبة قبليًا | == التعابير المرتبة قبليًا والمرتبة بعديًا == | ||
هناك نوعان آخران مهمّان من التعابير الرياضية، هما التعابير المرتّبة قبليًا والتعابير المرتّبة بعديًا. | هناك نوعان آخران مهمّان من التعابير الرياضية، هما التعابير المرتّبة قبليًا والتعابير المرتّبة بعديًا. | ||
| سطر 31: | سطر 31: | ||
يلاحظ أنّ كلا التعبيرين (القبلي والبعدي) لا يستخدم الأقواس في ترتيب أولوية العوامل، وأنّ الحاجة إلى استخدام الأقواس تظهر مع الترتيب الوسطي فقط، إذ أنّ ترتيب العمليات في التعابير المرتّبة قبليًا أو بعديًا منوط فقط بموقع العامل. | يلاحظ أنّ كلا التعبيرين (القبلي والبعدي) لا يستخدم الأقواس في ترتيب أولوية العوامل، وأنّ الحاجة إلى استخدام الأقواس تظهر مع الترتيب الوسطي فقط، إذ أنّ ترتيب العمليات في التعابير المرتّبة قبليًا أو بعديًا منوط فقط بموقع العامل. | ||
== [[Algorithms/infix to postfix|تحويل التعبير المرتّب وسطيًا إلى تعبير مرتّب بعديًا]] == | |||
تحوّل هذه الخوارزمية التعبير المرتّب وسطيًا إلى تعبير مرتّب بعديًا باستخدام [[Algorithms/stacks|المكدس]]. | |||
== [[Algorithms/infix to prefix|تحويل التعبير المرتّب وسطيًا إلى تعبير مرتّب قبليًا]] == | |||
== [[Algorithms/prefix to infix|تحويل التعبير المرتّب قبليًا إلى تعبير مرتب وسطيًا]] == | |||
تحوّل هذه الخوارزمية التعبير المرتب قبليًا إلى تعبير مرتّب بعديًا. | |||
== [[Algorithms/prefix to postfix|تحويل التعبير المرتّب قبليًا إلى تعبير مرتب بعديًا]] == | |||
تحوّل هذه الخوارزمية التعبير المرتب قبليًا إلى تعبير مرتّب بعديًا. | |||
== [[Algorithms/postfix to infix|تحويل التعبير المرتّب بعديًا إلى تعبير مرتب وسطيًا]] == | |||
تحوّل هذه الخوارزمية التعبير المرتب بعديًا إلى تعبير مرتّب وسطيًا. | |||
== [[Algorithms/postfix to prefix|تحويل التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا]] == | |||
تحوّل هذه الخوارزمية التعبير المرتب بعديًا إلى تعبير مرتّب قبليًا. | |||
== مصادر == | == مصادر == | ||
* [https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html الفصل 4.9] من كتاب Problem Solving with Algorithms and Data Structures using Python لمؤلّفيه Brad Miller | * [https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html الفصل 4.9] من كتاب Problem Solving with Algorithms and Data Structures using Python لمؤلّفيه Brad Miller و David Ranum و Luther College. | ||
[[تصنيف: الخوارزميات]] | [[تصنيف: الخوارزميات]] | ||
[[تصنيف: بنى المعطيات]] | [[تصنيف: بنى المعطيات]] | ||
[[تصنيف: الخوارزميات الرياضية]] | [[تصنيف: الخوارزميات الرياضية]] | ||
المراجعة الحالية بتاريخ 09:57، 3 مارس 2020
يقدّم التعبير الرياضي 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.