تحويل التعبير المرتّب بعديًا إلى تعبير مرتّب قبليًا

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

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

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

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

مثال:

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

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

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

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 postToPre(string post_exp) 
{ 
	stack<string> s; 

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

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

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

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

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

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

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

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

	// stack[0] التعبير المرتّب قبليًا موجود في
	return s.top(); 
} 

// اختبار الدالتين السابقتين 
int main() 
{ 
	string post_exp = "ABC/-AK/L-*"; 
	cout << "Prefix : " << postToPre(post_exp); 
	return 0; 
}

• بايثون:

# تتحقق الدالة ممّا إذا كان الحرف المعطى عاملًا أو معاملًا 
def isOperator(x) : 
	
	if x == "+" : 
		return True
		
	if x == "-" : 
		return True
		
	if x == "/" : 
		return True

	if x == "*" : 
		return True
		
	return False; 

# تحوّل الدالة التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا
def postToPre(post_exp) : 

	s = []; 

	# طول التعبير 
	length = len(post_exp); 

	# قراءة التعبير من اليمين إلى اليسار 
	for i in range(length) : 

		# التحقق من كون الرمز الحالي عاملًا 
		if (isOperator(post_exp[i])) : 

			# حذف عاملين من المكدس 
			op1 = s[-1]; 
			s.pop(); 
			op2 = s[-1]; 
			s.pop(); 

			# ربط العاملين بالمعامل الخاصّ بهما
			temp = post_exp[i] + op2 + op1; 

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

		# إن كان الرمز معاملًا 
		else : 

			# يُضاف المعامل إلى المكدس 
			s.append(post_exp[i]); 

	# stack[0] التعبير المرتّب قبليًا موجود في 
	return s[-1]; 

# اختبار الدالتين السابقتين  
if __name__ == "__main__" : 

	post_exp = "ABC/-AK/L-*"; 
	print("Prefix : ", postToPre(post_exp));

• جافا:

import java.util.*; 

class GFG { 

	// يتحقق التابع ممّا إذا كان الحرف المعطى عاملًا أو معاملًا 
	static boolean isOperator(char x) 
	{ 

		switch (x) { 
		case '+': 
		case '-': 
		case '/': 
		case '*': 
			return true; 
		} 
		return false; 
	} 

	// يحوّل التابع التعبير المرتّب بعديًا إلى تعبير مرتب قبليًا 
	static String postToPre(String post_exp) 
	{ 
		Stack<String> s = new Stack<String>(); 

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

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

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

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

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

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

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

				// يُضاف المعامل إلى المكدس
				s.push(post_exp.charAt(i) + ""); 
			} 
		} 

		// stack[0] التعبير المرتّب قبليًا موجود في
		return s.peek(); 
	} 

	// اختبار التابعين السابقين 
	public static void main(String args[]) 
	{ 
		String post_exp = "ABC/-AK/L-*"; 
		System.out.println("Prefix : " + postToPre(post_exp)); 
	} 
}

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

Prefix : *-A/BC-/AKL

مصادر

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