Algorithms/prefix to infix

التعبير المرتّب قبليًا Prefix: هو تعبير رياضي يسبق فيه العامل المعاملين الذين يعمل عليهما، مثل (‎*+AB-CD) (يقابل التعبير المرتّب وسطيًا ‎(A+B) * (C-D)‎).

التعبير المرتّب وسطيًّا Infix: هو تعبير رياضي يتوسّط فيه العامل المعاملين الذين يعمل عليهما، مثل: ‎(A+B) * (C-D)‎.

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

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

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

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

1. قراءة التعبير المرتّب قبليًّا من اليمين إلى اليسار.
2. إن كان الرمز المقروء عاملًا operand، فإنه يُضاف إلى المكدس.
3. إن كان الرمز المقروء معاملًا operator، يُحذف معاملان من المكدس.
4. إنشاء سلسلة نصية عن طريق ربط عاملين يسبقهما المعامل الخاصّ بهما string = operator + operand2 + operand1 وإضافة السلسلة النصية الناتجة إلى المكدس مجدّدًا.
5. تعاد الخطوات السابقة إلى أن تصل الخوارزمية إلى نهاية التعبير المرتب قبليًا.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
#include <stack> 
using namespace std; 

// تتحقق الدالة ممّا إذا كان الحرف المعطى عاملًا أو معاملًا 
bool isOperator(char x) { 
switch (x) { 
case '+': 
case '-': 
case '/': 
case '*': 
	return true; 
} 
return false; 
} 

// تحوّل الدالة التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا
string preToInfix(string pre_exp) { 
stack<string> s; 

// طول التعبير
int length = pre_exp.size(); 

// قراءة التعبير من اليمين إلى اليسار
for (int i = length - 1; i >= 0; i--) { 

	// التحقق من كون الرمز الحالي عاملًا 
	if (isOperator(pre_exp[i])) { 

	// حذف عاملين من المكدس 
	string op1 = s.top(); s.pop(); 
	string op2 = s.top(); s.pop(); 

	// ربط العاملين بالمعامل الخاصّ بهما 
	string temp = "(" + op1 + pre_exp[i] + op2 + ")"; 

	// إعادة السلسلة النصية المؤقتة إلى المكدس
	s.push(temp); 
	} 

	// إن كان الرمز معاملًا 
	else { 

	// يُضاف المعامل إلى المكدس  
	s.push(string(1, pre_exp[i])); 
	} 
} 

// يحتوي المكدس على التعبير المرتب وسطيًا فقط 
return s.top(); 
} 

// اختبار الدالتين السابقتين
int main() { 
string pre_exp = "*-A/BC-/AKL"; 
cout << "Infix : " << preToInfix(pre_exp); 
return 0; 
}

مصادر

• صفحة Prefix to Infix Conversion في توثيق الخوارزميات في موقع GeeksforGeeks.