قبل أن نفهم التحويل من تدوين infix إلى postfix، يجب أن نعرف المزيد عن تدوين infix وpostfix بشكل منفصل.
إن infix و postfix هي التعبيرات. يتكون التعبير من ثوابت ومتغيرات ورموز. يمكن أن تكون الرموز عوامل تشغيل أو أقواس. ويجب ترتيب كل هذه المكونات وفق مجموعة من القواعد بحيث يمكن تقييم كل هذه التعبيرات باستخدام مجموعة القواعد.
ومن أمثلة التعبيرات:
5 + 6
أ - ب
(ف * 5)
جميع التعبيرات المذكورة أعلاه لها بنية مشتركة، أي أن لدينا عامل بين المعاملين. المعامل هو كائن أو قيمة سيتم تنفيذ العملية عليها. في التعبيرات المذكورة أعلاه، 5، 6 هي المعاملات بينما '+'، و'-'، و'*' هي المعاملات.
ما هو تدوين infix؟
عندما يتم كتابة العامل بين المعاملات، فإنه يعرف باسم تدوين infix . لا يجب أن يكون المعامل دائمًا ثابتًا أو متغيرًا؛ ويمكن أيضًا أن يكون تعبيرًا بحد ذاته.
على سبيل المثال،
(ع + ف) * (ص + ق)
في التعبير أعلاه، كل من تعبيرات عامل الضرب هي المعاملات، أي، (ع + ف) ، و (ص + ق) هي المعاملات.
في التعبير أعلاه، هناك ثلاثة عوامل. معاملات عامل التشغيل الأول هي p و q، معاملات عامل التشغيل الثاني هي r و s. أثناء أداء العمليات على التعبير، نحن بحاجة إلى اتباع مجموعة من القواعد لتقييم النتيجة. في ال التعبير أعلاه، سيتم إجراء عملية الجمع على التعبيرين، أي p+q وr+s، ومن ثم سيتم إجراء عملية الضرب.
ويرد أدناه بناء جملة تدوين infix:
إذا كان هناك عامل واحد فقط في التعبير، فلا نحتاج إلى تطبيق أي قاعدة. على سبيل المثال، 5 + 2؛ في هذا التعبير يمكن إجراء عملية الجمع بين المعاملين (5 و 2)، وتكون نتيجة العملية 7.
اتصالات في جافا
إذا كان هناك عوامل تشغيل متعددة في التعبير، فيجب اتباع بعض القواعد لتقييم التعبير.
إذا كان التعبير هو:
4+6*2
إذا تم تقييم عامل الجمع أولاً، فسيبدو التعبير كما يلي:
10*2 = 20
إذا تم تقييم عامل الضرب أولاً، فسيبدو التعبير كما يلي:
4 + 12 = 16
يمكن حل المشكلة المذكورة أعلاه باتباع قواعد أسبقية عامل التشغيل. في التعبير الجبري، يتم إعطاء ترتيب أسبقية المشغل في الجدول أدناه:
| العاملين | حرف او رمز |
|---|---|
| أقواس | ( )، {}، [ ] |
| الدعاة | ^ |
| الضرب والقسمة | *، / |
| جمع وطرح | +، - |
يتم إعطاء الأفضلية الأولى للأقواس؛ ثم يتم إعطاء الأفضلية التالية للأسس. في حالة وجود عوامل أس متعددة، سيتم تطبيق العملية من اليمين إلى اليسار.
على سبيل المثال:
2^2^3 = 2^8
= 256
بعد الأس، يتم تقييم عوامل الضرب والقسمة. إذا كان كلا العاملين موجودين في التعبير، فسيتم تطبيق العملية من اليسار إلى اليمين.
يتم إعطاء التفضيل التالي للجمع والطرح. إذا كان كلا العاملين متاحين في التعبير، فإننا ننتقل من اليسار إلى اليمين.
العوامل التي لها نفس الأسبقية تسمى ترابط المشغل . إذا انتقلنا من اليسار إلى اليمين، فإنه يُعرف باسم اليسار الترابطي. إذا انتقلنا من اليمين إلى اليسار، فإنه يُعرف باسم الترابط الأيمن.
مشكلة في تدوين infix
لتقييم تعبير infix، يجب أن نعرف عن أسبقية المشغل القواعد، وإذا كانت العوامل لها نفس الأسبقية، فيجب علينا اتباع الترابط قواعد. يعد استخدام الأقواس أمرًا مهمًا جدًا في تدوين infix للتحكم في الترتيب الذي سيتم تنفيذ العملية به. تعمل الأقواس على تحسين إمكانية قراءة التعبير. يعد تعبير infix هو الطريقة الأكثر شيوعًا لكتابة التعبير، ولكن ليس من السهل تحليل وتقييم تعبير infix دون غموض. لذلك، درس علماء الرياضيات وعلماء المنطق هذه المشكلة واكتشفوا طريقتين أخريين لكتابة التعبيرات وهما البادئة واللاحقة. كلا التعبيرين لا يتطلبان أي أقواس ويمكن تحليلهما دون غموض. لا يتطلب أسبقية المشغل وقواعد الارتباط.
الثعلب مقابل الذئب
تعبير بوستفيكس
تعبير postfix هو تعبير يتم فيه كتابة العامل بعد المعاملات. على سبيل المثال، يمكن كتابة تعبير postfix الخاص بتدوين infix (2+3) بالشكل 23+.
بعض النقاط الأساسية المتعلقة بتعبير postfix هي:
- في تعبير postfix، يتم تنفيذ العمليات بالترتيب الذي كتبت به من اليسار إلى اليمين.
- أنها لا تتطلب أي قوسين.
- لا نحتاج إلى تطبيق قواعد أسبقية عامل التشغيل وقواعد الارتباط.
خوارزمية لتقييم تعبير postfix
- قم بمسح التعبير من اليسار إلى اليمين حتى نواجه أي عامل.
- تنفيذ العملية
- استبدل التعبير بقيمته المحسوبة.
- كرر الخطوات من 1 إلى 3 حتى لا يوجد المزيد من العوامل.
دعونا نفهم الخوارزمية المذكورة أعلاه من خلال مثال.
تعبير Infix: 2 + 3 * 4
سنبدأ في المسح من اليسار لمعظم التعبير. عامل الضرب هو عامل يظهر أولاً أثناء المسح من اليسار إلى اليمين. الآن سيكون التعبير:
التعبير = 2 + 34*
= 2 + 12
مرة أخرى، سوف نقوم بالمسح من اليسار إلى اليمين، وسيكون التعبير كما يلي:
التعبير = 2 12 +
= 14
تقييم تعبير postfix باستخدام المكدس.
- مسح التعبير من اليسار إلى اليمين.
- إذا واجهنا أي معامل في التعبير، فإننا ندفع المعامل في المكدس.
- عندما نواجه أي عامل في التعبير، فإننا نخرج المعاملات المقابلة من المكدس.
- عندما ننتهي من مسح التعبير، تبقى القيمة النهائية في المكدس.
دعونا نفهم تقييم تعبير postfix باستخدام المكدس.
مثال 1: تعبير Postfix: 2 3 4 * +
| مدخل | كومة | |
|---|---|---|
| 2 3 4 * + | فارغ | ادفع 2 |
| 3 4 * + | 2 | ادفع 3 |
| 4*+ | 3 2 | ادفع 4 |
| * + | 4 3 2 | انبثق 4 و3، وقم بإجراء 4*3 = 12. ادفع 12 إلى المكدس. |
| + | 12 2 | انزع 12 و2 من المكدس، وقم بإجراء 12+2 = 14. ادفع 14 إلى المكدس. |
نتيجة التعبير أعلاه هي 14.
مثال 2: تعبير Postfix: 3 4 * 2 5 * +
| مدخل | كومة | |
|---|---|---|
| 3 4 * 2 5 * + | فارغ | ادفع 3 |
| 4*2 5*+ | 3 | ادفع 4 |
| *2 5* + | 4 3 | انزع 3 و4 من المكدس وقم بإجراء 3*4 = 12. ادفع 12 إلى المكدس. |
| 2 5 * + | 12 | ادفع 2 |
| 5*+ | 2 12 | ادفع 5 |
| *+ | 5 2 12 | انزع 5 و2 من المكدس وقم بإجراء 5*2 = 10. ادفع 10 إلى المكدس. |
| + | 10 12 | انزع 10 و12 من المكدس وقم بإجراء 10+12 = 22. ادفع 22 إلى المكدس. |
نتيجة التعبير أعلاه هي 22.
خوارزمية لتقييم التعبير postfix
- قراءة شخصية
- إذا كان الحرف رقمًا، فقم بتحويل الحرف إلى int وادفع العدد الصحيح إلى المكدس.
- إذا كانت الشخصية عاملاً،
- قم بإخراج العناصر من المكدس مرتين للحصول على معاملين.
- تنفيذ العملية
- ادفع النتيجة إلى المكدس.
تحويل infix إلى postfix
هنا، سوف نستخدم بنية بيانات المكدس لتحويل تعبير infix إلى تعبير بادئة. عندما يواجه عامل ما، ندفعه إلى المكدس. إذا واجهنا معاملًا، فإننا نلحق المعامل بالتعبير.
الاستعداد لاختبار mockito
قواعد التحويل من تعبير infix إلى تعبير postfix
- اطبع المعامل فور وصوله.
- إذا كانت المكدسة فارغة أو تحتوي على قوس أيسر في الأعلى، فادفع عامل التشغيل الوارد إلى المكدس.
- إذا كان الرمز الوارد هو '('، فادفعه إلى المكدس.
- إذا كان الرمز الوارد هو ')'، فقم بإخراج المكدس وطباعة العوامل حتى يتم العثور على القوس الأيسر.
- إذا كان للرمز الوارد أسبقية أعلى من الجزء العلوي من المكدس، فادفعه على المكدس.
- إذا كان للرمز الوارد أسبقية أقل من الجزء العلوي من المكدس، فقم بطباعة الجزء العلوي من المكدس. ثم اختبر المشغل الوارد مقابل الجزء العلوي الجديد من المكدس.
- إذا كان عامل التشغيل الوارد له نفس الأسبقية مع الجزء العلوي من المكدس، فاستخدم قواعد الارتباط. إذا كان الارتباط من اليسار إلى اليمين، فقم بطباعة الجزء العلوي من المكدس ثم ادفع عامل التشغيل الوارد. إذا كان الارتباط من اليمين إلى اليسار، فادفع العامل الوارد.
- في نهاية التعبير، قم بطباعة كافة عوامل تشغيل المكدس.
دعونا نفهم من خلال مثال.
تعبير Infix: K + L - M*N + (O^P) * W/U/V * T + Q
| تعبير الإدخال | كومة | تعبير بوستفيكس |
|---|---|---|
| ك | ك | |
| + | + | |
| ل | + | ك ل |
| - | - | ك ل+ |
| م | - | ك ل + م |
| * | -* | ك ل + م |
| ن | -* | ك ل + م ن |
| + | + | ك ل + م ن * ك ل + م ن* - |
| ( | + ( | ك ل + م ن *- |
| يا | + ( | ك ل + م ن * - أو |
| ^ | + (^ | ك ل + م ن* - س |
| ص | + (^ | ك ل + م ن* - أو ص |
| ) | + | ك ل + م ن* - أو ف ^ |
| * | + * | ك ل + م ن* - أو ف ^ |
| في | + * | K L + M N* - O P ^ W |
| / | + / | ك ل + م ن* - أو ف ^ ث * |
| في | + / | K L + M N* - O P ^W*U |
| / | + / | ك ل + م ن* - أو ف ^W*U/ |
| في | + / | KL + MON*-UP^W*U/F |
| * | + * | كوالالمبور+MON*-UP^W*U/F/ |
| ت | + * | KL+MN*-UP^W*U/F/T |
| + | + | الاثنين+الاثنين*-الأعلى^W*U/F/T* KL+MN*-UP^W*U/F/T*+ |
| س | + | KL+MN*-OP^W*U/V/T*Q |
| KL+MN*-OP^W*U/V/T*+Q+ |
التعبير اللاحق النهائي لتعبير infix(K + L - M*N + (O^P) * W/U/V * T + Q) هو KL+MN*-OP^W*U/V/T*+Q+ .