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

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

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

تسمّى التعابير المرتّبة بعديًا كذلك باسم التنويت البولندي المعكوس reverse Polish notation، وعلى الرغم من أنّ تنفيذ مثل هذه التعابير سهل وفعّال بالنسبة للحواسيب، إلا أنّ قراءة هذه التعابير وتفسيرها صعب بالنسبة للبشر، ولكن يستطيع البشر قراءة التعابير الرياضية المعقّدة التي تستخدم الأقواس لتحديد أولوية العمليات الرياضية؛ ولهذا تحتّم الضرورة في بعض الأحيان إتاحة الفرصة للمستخدم النهائي في أن يتعامل مع التعابير المرتبة وسطيًا ثم تحويلها إلى تعابير مرتّبة بعديًا لغرض معالجتها من قبل الحاسوب؛ وفي بعض الأحيان تخزّن التعابير الرياضية مرتّبة بعديًا، ويكون المطلوب تحويل هذه التعابير إلى الترتيب الوسطي لغرض القراءة والتحرير.

مثال:

Input : abc++
Output : (a + (b + c))

Input  : ab*c+
Output : ((a*b)+c)

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

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

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

bool isOperand(char x) 
{ 
return (x >= 'a' && x <= 'z') || 
		(x >= 'A' && x <= 'Z'); 
} 

// تحويل التعبير المرتّب بعديًا إلى تعبير مرتّب وسطيًا 
string getInfix(string exp) 
{ 
	stack<string> s; 

	for (int i=0; exp[i]!='\0'; i++) 
	{ 
		// إضافة المعاملين
		if (isOperand(exp[i])) 
		{ 
		string op(1, exp[i]); 
		s.push(op); 
		} 

		// سنفترض أن المدخلات تحتوي على تعبير مرتّب بعديًا
		// ونتوقع وجود عامل في التعبير
		else
		{ 
			string op1 = s.top(); 
			s.pop(); 
			string op2 = s.top(); 
			s.pop(); 
			s.push("(" + op2 + exp[i] + 
				op1 + ")"); 
		} 
	} 

	// يجب أن يكون هناك عنصر واحد في المكدس في هذه المرحلة
	// وهو التعبير المرتّب وسطيًا المراد إيجاده
	return s.top(); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	string exp = "ab*c+"; 
	cout << getInfix(exp); 
	return 0; 
}

• بايثون:

def isOperand(x): 
	return ((x >= 'a' and x <= 'z') or
			(x >= 'A' and x <= 'Z')) 

# تحويل التعبير المرتّب بعديًا إلى تعبير مرتّب وسطيًا  
def getInfix(exp) : 

	s = [] 

	for i in exp:	 
		
		# إضافة المعاملين
		if (isOperand(i)) :		 
			s.insert(0, i) 
			
		# سنفترض أن المدخلات تحتوي على تعبير مرتّب بعديًا
		# ونتوقع وجود عامل في التعبير 
		else: 
		
			op1 = s[0] 
			s.pop(0) 
			op2 = s[0] 
			s.pop(0) 
			s.insert(0, "(" + op2 + i +
							op1 + ")") 
			
	# يجب أن يكون هناك عنصر واحد في المكدس في هذه المرحلة
	# وهو التعبير المرتّب وسطيًا المراد إيجاده 
	return s[0] 

# اختبار الدالة السابقة
if __name__ == '__main__': 

	exp = "ab*c+"
	print(getInfix(exp.strip()))

• جافا:

import java.util.*; 

class GFG 
{ 
	
static boolean isOperand(char x) 
{ 
	return (x >= 'a' && x <= 'z') || 
			(x >= 'A' && x <= 'Z'); 
} 

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

	for (int i = 0; i < exp.length(); i++) 
	{ 
		// إضافة المعاملين
		if (isOperand(exp.charAt(i))) 
		{ 
		s.push(exp.charAt(i) + ""); 
		} 

		// سنفترض أن المدخلات تحتوي على تعبير مرتّب بعديًا
		// ونتوقع وجود عامل في التعبير 
		else
		{ 
			String op1 = s.peek(); 
			s.pop(); 
			String op2 = s.peek(); 
			s.pop(); 
			s.push("(" + op2 + exp.charAt(i) + 
					op1 + ")"); 
		} 
	} 

	// يجب أن يكون هناك عنصر واحد في المكدس في هذه المرحلة
	// وهو التعبير المرتّب وسطيًا المراد إيجاده 
	return s.peek(); 
} 

// اختبار التابع السابق
public static void main(String args[]) 
{ 
	String exp = "ab*c+"; 
	System.out.println( getInfix(exp)); 
} 
}

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

abcd^e-fgh*+^*+i-

مصادر

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