ما هو تدوين infix؟
تدوين infix هو تدوين يتم فيه كتابة التعبير بتنسيق عادي أو عادي. وهو عبارة عن تدوين يقع فيه المشغلون بين المعاملات. أمثلة تدوين infix هي A+B، A*B، A/B، وما إلى ذلك.
كما يمكننا أن نرى في الأمثلة المذكورة أعلاه، جميع العوامل موجودة بين المعاملات، لذلك فهي تدوينات infix. لذلك، يمكن كتابة صيغة تدوين infix على النحو التالي:
تحليل تعبيرات Infix
من أجل تحليل أي تعبير، نحتاج إلى الاهتمام بأمرين، أي: أسبقية المشغل و الترابط . أسبقية عامل التشغيل تعني أسبقية أي عامل على عامل آخر. على سبيل المثال:
أ + ب * ج → أ + (ب * ج)
نظرًا لأن عامل الضرب له أسبقية أعلى على عامل الجمع، فسيتم تقييم تعبير B * C أولاً. تتم إضافة نتيجة ضرب B * C إلى A.
ترتيب الأسبقية
| العاملين | حرف او رمز |
|---|---|
| أقواس | { }، ()، [ ] |
| الأسية | ^ |
| الضرب والقسمة | *، / |
| جمع وطرح | +، - |
الترابط يعني وجود عوامل التشغيل ذات الأسبقية نفسها في التعبير. على سبيل المثال، في التعبير، أي A + B - C، يكون لعوامل التشغيل '+' و'-' نفس الأسبقية، لذا يتم تقييمها بمساعدة الترابط. نظرًا لأن كلا من '+' و'-' مرتبطان باليسار، فسيتم تقييمهما كـ (A + B) - C.
ترتيب الارتباط
| العاملين | الترابط |
|---|---|
| ^ | من اليمين الى اليسار |
| *، / | من اليسار إلى اليمين |
| +، - | من اليسار إلى اليمين |
دعونا نفهم الترابط من خلال مثال.
1+2*3+30/5
التحكم في البرنامج المخزن
بما أنه في التعبير أعلاه، * و/ لهما نفس الأسبقية، لذلك سنطبق قاعدة الترابط. كما يمكننا أن نلاحظ في الجدول أعلاه أن عوامل التشغيل * و/ لها ارتباط من اليسار إلى اليمين، لذلك سنقوم بالمسح من عامل التشغيل الموجود في أقصى اليسار. سيتم تقييم المشغل الذي يأتي أولاً أولاً. يظهر عامل التشغيل * قبل عامل التشغيل /، وسيتم إجراء الضرب أولاً.
1+ (2*3) + (30/5)
1+6+6 = 13
ما هو تدوين البادئة؟
تدوين البادئة هو شكل آخر من أشكال التعبير ولكنه لا يتطلب معلومات أخرى مثل الأسبقية والترابط، في حين يتطلب تدوين البادئة معلومات الأسبقية والترابط. ومن المعروف أيضا باسم التدوين البولندية . في تدوين البادئة، يأتي عامل التشغيل قبل المعاملات. بناء جملة تدوين البادئة موضح أدناه:
على سبيل المثال، إذا كان تعبير infix هو 5+1، فإن تعبير البادئة المقابل لتعبير infix هذا هو +51.
إذا كان تعبير infix هو:
أ * ب + ج
↓
*أب+ج
↓
+*abc (تعبير البادئة)
النظر في مثال آخر:
إنشاء مثيل جافا
أ + ب * ج
أول مسح: في التعبير أعلاه، يكون لعامل الضرب أسبقية أعلى من عامل الجمع؛ سيكون تدوين البادئة B*C هو (*BC).
أ + * ق
المسح الثاني: في الفحص الثاني، ستكون البادئة:
+أ*ق.م
في التعبير أعلاه، نستخدم عمليتي مسح لتحويل infix إلى تعبير بادئة. إذا كان التعبير معقدًا، فإننا نحتاج إلى عدد أكبر من عمليات المسح. نحن بحاجة إلى استخدام تلك الطريقة التي تتطلب فحصًا واحدًا فقط، وتوفر النتيجة المرجوة. إذا حققنا المخرجات المطلوبة من خلال مسح واحد، فستكون الخوارزمية فعالة. هذا ممكن فقط باستخدام المكدس.
تحويل Infix إلى بادئة باستخدام Stack
ك + L - M * N + (O^P) * W/U/V * T + Q
إذا كنا نقوم بتحويل التعبير من infix إلى بادئة، نحتاج أولاً إلى عكس التعبير.
التعبير العكسي سيكون:
Q + T * V/U/W * ) P^O(+ N*M - L + K
للحصول على تعبير البادئة، قمنا بإنشاء جدول يتكون من ثلاثة أعمدة، أي تعبير الإدخال، والمكدس، وتعبير البادئة. عندما نواجه أي رمز، فإننا ببساطة نضيفه إلى تعبير البادئة. إذا واجهنا المشغل، فسندفعه إلى المكدس.
| تعبير الإدخال | كومة | تعبير البادئة |
|---|---|---|
| س | س | |
| + | + | س |
| ت | + | كيو تي |
| * | +* | كيو تي |
| في | +* | كيو تي في |
| / | +*/ | كيو تي في |
| في | +*/ | كيو تي في يو |
| / | +*// | كيو تي في يو |
| في | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| ص | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| يا | +*//*)^ | QTVUWPO |
| ( | +*//* | كيو تي في يوبو^ |
| + | ++ | كيو تي في يوبو ^*//* |
| ن | ++ | QTVUWPO^*//*N |
| * | +*** | QTVUWPO^*//*N |
| م | +*** | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| ل | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| ك | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
التعبير أعلاه، أي QTVUWPO^*//*NM*LK+-++، ليس تعبيرًا نهائيًا. نحتاج إلى عكس هذا التعبير للحصول على تعبير البادئة.
قواعد تحويل infix إلى تعبير بادئة:
- أولاً، قم بعكس تعبير infix الوارد في المشكلة.
- مسح التعبير من اليسار إلى اليمين.
- عندما تصل المعاملات، قم بطباعتها.
- إذا وصل المشغل ووجد أن المكدس فارغ، فما عليك سوى دفع المشغل إلى المكدس.
- إذا كان عامل التشغيل الوارد له أسبقية أعلى من الجزء العلوي من المكدس، فادفع عامل التشغيل الوارد إلى المكدس.
- إذا كان عامل التشغيل الوارد له نفس الأسبقية مع الجزء العلوي من المكدس، فادفع عامل التشغيل الوارد إلى المكدس.
- إذا كان عامل التشغيل الوارد له أسبقية أقل من الجزء العلوي من المكدس، فافتح الجزء العلوي من المكدس واطبعه. اختبر العامل الوارد مقابل الجزء العلوي من المكدس مرة أخرى، ثم أخرج العامل من المكدس حتى يجد العامل ذو الأسبقية الأقل أو نفس الأسبقية.
- إذا كان العامل الوارد له نفس الأسبقية مع الجزء العلوي من المكدس وكان العامل الوارد هو ^، فقم بفتح الجزء العلوي من المكدس حتى يصبح الشرط صحيحًا. إذا كان الشرط غير صحيح، فاضغط على عامل التشغيل ^.
- عندما نصل إلى نهاية التعبير، قم بطباعة كافة العوامل من أعلى المكدس.
- إذا كان عامل التشغيل ')'، فادفعه إلى المكدس.
- إذا كان عامل التشغيل هو '('، فقم بإخراج كافة العوامل من المكدس حتى تجد ) قوس الفتح في المكدس.
- إذا كان الجزء العلوي من المكدس هو ')'، فادفع العامل على المكدس.
- في النهاية، عكس الإخراج.
الكود الكاذب لتحويل infix إلى بادئة
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>