Algorithms/prefix to postfix

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

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

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

يُفضّل تحويل التعبير المرتّب قبليًا إلى تعبير مرتب بعديًا دون تحويله إلى تعبير مرتّب وسطيًا في البداية، ويجدر التنبيه إلى أن الحواسيب تنفّذ التعابير المرتّبة بعديًا.

مثال:

Input :  Prefix :  *+AB-CD
Output : Postfix : AB+CD-*
Explanation : Prefix to Infix :  (A+B) * (C-D)
              Infix to Postfix :  AB+CD-*

Input :  Prefix :  *-A/BC-/AKL
Output : Postfix : ABC/-AK/L-*
Explanation : Prefix to Infix :  A-(B/C)*(A/K)-L
              Infix to Postfix : ABC/-AK/L-*

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

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

string = operator + operand2 + operand1
وإضافة السلسلة النصية الناتجة إلى المكدس مجدّدًا.

1. تعاد الخطوات السابقة إلى أن تصل الخوارزمية إلى نهاية التعبير المرتب قبليًا.

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

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

• C++‎:

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

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

// تحوّل الدالة التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا
string preToPost(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 + op2 + pre_exp[i]; 

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

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

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

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

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

• بايثون:

• جافا:

import java.util.*; 

class GFG 
{ 

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

// يحوّل التابع التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا
static String preToPost(String pre_exp) 
{ 

	Stack<String> s= new Stack<String>(); 

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

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

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

			// ربط العاملين بالمعامل الخاصّ بهما
			String op1 = s.peek(); s.pop(); 
			String op2 = s.peek(); s.pop(); 

			// ربط العاملين بالمعامل الخاصّ بهما 
			String temp = op1 + op2 + pre_exp.charAt(i); 

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

		// إن كان الرمز معاملًا 
		else
		{ 
			// يُضاف المعامل إلى المكدس  
			s.push( pre_exp.charAt(i)+""); 
		} 
	} 

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

// اختبار التابعين السابقين
public static void main(String args[]) 
{ 
	String pre_exp = "*-A/BC-/AKL"; 
	System.out.println("Postfix : " + preToPost(pre_exp)); 
} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Postfix : ABC/-AK/L-*

مصادر

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