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

التعبير المرتّب وسطيًا Infix: هو تعبير رياضي يتوسّط فيه العامل المعاملين الذين يعمل عليهما.

التعبير المرتّب بعديًا Postfix: هو تعبير رياضي يلي فيه العامل المعاملين الذين يعمل عليهما.

يمسح المصرّف Compiler التعابير الرياضية من اليمين إلى اليسار أو من اليسار إلى اليمين، فعلى سبيل المثال:

A * B + C + D

يمسح المصرّف التعبير السابق لتنفيذ عملية الضرب A * B ثم يمسح التعبير مجدّدًا لتنفيذ عملية الجمع بين ناتج عملية الضرب و C، ثم يعيد الكرّة ليجمع ناتج العملية السابق مع D.

تؤدي عمليات المسح المتكرّرة هذه إلى إبطاء عملية التصريف وجعلها غير فعالة؛ ويفضّل في هذه الحالة تحويل التعبير إلى تعبير مرتّب بعديًا (أو قبليًا) قبل تنفيذ العمليات الرياضية.

الترتيب البعدي للتعبير السابق هو AB*C+D+‎ ويكن تنفيذ العمليات التي يتضمنها باستخدام المكدس.

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

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

1. مسح التعبير المرتّب وسطيًا من اليسار إلى اليمين.
2. إن كان الحرف الممسوح من العوامل، فإنّه يُرسل إلى المخرجات.
3. إن لم يتحقق الشرط السابق:
   1. إن كانت أولوية العامل الممسوح أعلى من أولوية العامل الموجود في المكدس (أو إن كان المكدس فارغًا أو إن احتوى المكدس على القوس ')'، فإنّ العامل يُضاف إلى المكدس.
   2. إن لم يتحقق الشرط السابق، تُحذف جميع العوامل التي تتفوّق على العامل الممسوح أو تساويه في الأولوية من المكدس. بعد ذلك يُضاف العامل الممسوح إلى المكدس (إن واجهت الخوارزمية أقواسًا أثناء عملية حذف العوامل فإنّها تتوقف عند القوس وتضيف العامل الممسوح إلى المكدس).
4. إن كان الحرف الممسوح هو القوس ')' فإنّه يضاف إلى المكدس.
5. إن كان الحرف الممسوح هو القوس '(' فإنّه عناصر المكدس تُحذف وتُنقل إلى المخرجات إلى حين الوصول إلى القوس ')'، ثم يجري تجاهل القوسين كليهما.
6. تكرّر الخطوات من 2 إلى 6 إلى أن يكتمل فحص التعبير المرتّب وسطيًا.
7. طباعة المخرجات.
8. حذف عناصر المكدس وإرسالها إلى المخرجات إلى أن يصبح المكدس فارغًا.

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

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

• C++‎:

لاحظ استخدام std::stack لإجراء العمليات الخاصة بالمكادس.

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

// تعيد الدالة أولوية العوامل
int prec(char c) 
{ 
	if(c == '^') 
	return 3; 
	else if(c == '*' || c == '/') 
	return 2; 
	else if(c == '+' || c == '-') 
	return 1; 
	else
	return -1; 
} 

// الدالة الرئيسية المسؤولة عن تحويل التعبير من الترتيب الوسطي إلى الترتيب البعدي
void infixToPostfix(string s) 
{ 
	std::stack<char> st; 
	st.push('N'); 
	int l = s.length(); 
	string ns; 
	for(int i = 0; i < l; i++) 
	{ 
		// إن كان الحرف الممسوح عاملًا، يُضاف إلى سلسلة المخرجات النصية
		if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 
		ns+=s[i]; 

		// إن كان الحرف الممسوح هو القوس ')' فإنّه يضاف إلى المكدس
		else if(s[i] == '(') 
		
		st.push('('); 
		
		// إن كان الحرف الممسوح هو القوس '(' يُحذف هو وجميع العناصر التي تليه
		// وينقل إلى سلسلة المخرجات النصية وصولًا إلى القوس ')' في المكدس
		else if(s[i] == ')') 
		{ 
			while(st.top() != 'N' && st.top() != '(') 
			{ 
				char c = st.top(); 
				st.pop(); 
			ns += c; 
			} 
			if(st.top() == '(') 
			{ 
				char c = st.top(); 
				st.pop(); 
			} 
		} 
		
		// إن جرى مسح العامل
		else{ 
			while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 
			{ 
				char c = st.top(); 
				st.pop(); 
				ns += c; 
			} 
			st.push(s[i]); 
		} 

	} 
	// حذف العناصر المتبقية من المكدس
	while(st.top() != 'N') 
	{ 
		char c = st.top(); 
		st.pop(); 
		ns += c; 
	} 
	
	cout << ns << endl; 

} 

// اختبار الدالتين السابقتين
int main() 
{ 
	string exp = "a+b*(c^d-e)^(f+g*h)-i"; 
	infixToPostfix(exp); 
	return 0; 
}

• بايثون:

# يستخدم الصنف لتحويل التعبير من الترتيب الوسطي إلى الترتيب البعدي 
class Conversion: 
	
	# الدالة البانية والتي تهيّئ المتغيرات الخاصة بالصنف
	def __init__(self, capacity): 
		self.top = -1
		self.capacity = capacity 
		# This array is used a stack 
		self.array = [] 
		# إعدادات الأولوية
		self.output = [] 
		self.precedence = {'+':1, '-':1, '*':2, '/':2, '^':3} 
	
	# التحقق من خلو المكدس من العناصر
	def isEmpty(self): 
		return True if self.top == -1 else False
	
	# يعيد التابع قيمة العنصر العلوي في المكدس 
	def peek(self): 
		return self.array[-1] 
	
	# يحذف التابع العنصر من المكدس
	def pop(self): 
		if not self.isEmpty(): 
			self.top -= 1
			return self.array.pop() 
		else: 
			return "$"
	
	# يضيف التابع العنصر إلى المكدس
	def push(self, op): 
		self.top += 1
		self.array.append(op) 

	# دالة مساعدة تتحقّق من كون الحرف الحالي عاملًا أو لا
	def isOperand(self, ch): 
		return ch.isalpha() 

	# التحقّق من أنّ أولوية العامل أقل من العنصر العلوي في المكدس
	def notGreater(self, i): 
		try: 
			a = self.precedence[i] 
			b = self.precedence[self.peek()] 
			return True if a <= b else False
		except KeyError: 
			return False
			
	# الدالة الرئيسية المسؤولة عن تحويل التعبير من الترتيب الوسطي إلى الترتيب البعدي
	def infixToPostfix(self, exp): 
		
		# المرور على حروف التعبير لإجراء عملية التحويل
		for i in exp: 
			# إن كان الحرف الحالي عاملًا فإنّه يُضاف إلى المخرجات
			if self.isOperand(i): 
				self.output.append(i) 
			
			# إن كان الحرف الحالي هو القوس ')' فإنّه يُضاف إلى المكدس
			elif i == '(': 
				self.push(i) 

			# إن كان الحرف الممسوح هو القوس '(' يُحذف هو وما يليه من العناصر من المكدس
			# وصولًا إلى القوس ')'
			elif i == ')': 
				while( (not self.isEmpty()) and self.peek() != '('): 
					a = self.pop() 
					self.output.append(a) 
				if (not self.isEmpty() and self.peek() != '('): 
					return -1
				else: 
					self.pop() 

			# في حال ملاقاة أحد العوامل
			else: 
				while(not self.isEmpty() and self.notGreater(i)): 
					self.output.append(self.pop()) 
				self.push(i) 

		# حذف جميع العوامل من المكدس
		while not self.isEmpty(): 
			self.output.append(self.pop()) 

		print "".join(self.output) 

# اختبار الدوال السابقة
exp = "a+b*(c^d-e)^(f+g*h)-i"
obj = Conversion(len(exp)) 
obj.infixToPostfix(exp)

• جافا:

import java.util.Stack; 

class Test 
{ 
	// دالة مساعدة تعيد أولوية العامل المعطى
	// كلما كانت القيمة المعادة أكبر امتلك العامل أولوية أعلى
	static int Prec(char ch) 
	{ 
		switch (ch) 
		{ 
		case '+': 
		case '-': 
			return 1; 
	
		case '*': 
		case '/': 
			return 2; 
	
		case '^': 
			return 3; 
		} 
		return -1; 
	} 
	
	// التابع الرئيسي المسؤول عن تحويل التعبير من الترتيب الوسطي إلى الترتيب البعدي
	static String infixToPostfix(String exp) 
	{ 
		// تهيئة سلسلة نصية فارغة توضع فيها النتائج
		String result = new String(""); 
		
		// تهيئة مكدس فارغ
		Stack<Character> stack = new Stack<>(); 
		
		for (int i = 0; i<exp.length(); ++i) 
		{ 
			char c = exp.charAt(i); 
			
			// إن كان الحرف الحالي عاملًا فإنّه يُضاف إلى المخرجات 
			if (Character.isLetterOrDigit(c)) 
				result += c; 
			
			// إن كان الحرف الحالي هو القوس ')' فإنّه يُضاف إلى المكدس 
			else if (c == '(') 
				stack.push(c); 
			
			// إن كان الحرف الممسوح هو القوس '(' يُحذف هو وما يليه من العناصر من المكدس
			// وصولًا إلى القوس ')' 
			else if (c == ')') 
			{ 
				while (!stack.isEmpty() && stack.peek() != '(') 
					result += stack.pop(); 
				
				if (!stack.isEmpty() && stack.peek() != '(') 
					return "Invalid Expression"; // تعبير غير صحيح				 
				else
					stack.pop(); 
			} 
			else //  في حال ملاقاة أحد العوامل 
			{ 
				while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){ 
					if(stack.peek() == '(') 
						return "Invalid Expression"; 
					result += stack.pop(); 
			} 
				stack.push(c); 
			} 
	
		} 
	
		// حذف جميع العوامل من المكدس 
		while (!stack.isEmpty()){ 
			if(stack.peek() == '(') 
				return "Invalid Expression"; 
			result += stack.pop(); 
		} 
		return result; 
	} 
	
	// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		String exp = "a+b*(c^d-e)^(f+g*h)-i"; 
		System.out.println(infixToPostfix(exp)); 
	} 
}

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

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

مصادر

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