Algorithms/infix to prefix

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

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

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

1. قلب التعبير المرتّب وسطيًا، أي يتحوّل التعبير A+B*C إلى C*B+A. ويجب الانتباه إلى أنّ عملية القلب تشمل الأقواس، بمعنى أنّ كل ')' يتحول إلى '('، وكلّ '(' يتحوّل إلى ')'.
2. الحصول على التعبير المرتّب بعديًا.
3. قلب التعبير المرتّب بعديًا للحصول على تعبير مرتّبٍ قبليًا.

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

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

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

bool isOperator(char c) 
{ 
	return (!isalpha(c) && !isdigit(c)); 
} 

int getPriority(char C) 
{ 
	if (C == '-' || C == '+') 
		return 1; 
	else if (C == '*' || C == '/') 
		return 2; 
	else if (C == '^') 
		return 3; 
	return 0; 
} 

string infixToPostfix(string infix) 
{ 
	infix = '(' + infix + ')'; 
	int l = infix.size(); 
	stack<char> char_stack; 
	string output; 

	for (int i = 0; i < l; i++) { 

		// إن كان الحرف الممسوح عاملًا، يُضاف إلى سلسلة المخرجات النصية 
		if (isalpha(infix[i]) || isdigit(infix[i])) 
			output += infix[i]; 

		// إن كان الحرف الممسوح هو القوس ')' فإنّه يضاف إلى المكدس 
		else if (infix[i] == '(') 
			char_stack.push('('); 

		// إن كان الحرف الممسوح هو القوس '(' يُحذف هو وجميع العناصر التي تليه 
		//  وينقل إلى سلسلة المخرجات النصية وصولًا إلى القوس ')' في المكدس 
		else if (infix[i] == ')') { 

			while (char_stack.top() != '(') { 
				output += char_stack.top(); 
				char_stack.pop(); 
			} 

			// حذف القوس ')' من المكدس
			char_stack.pop(); 
		} 

		// إن جرى مسح العامل 
		else { 
			
			if (isOperator(char_stack.top())) { 
				while (getPriority(infix[i]) 
				<= getPriority(char_stack.top())) { 
					output += char_stack.top(); 
					char_stack.pop(); 
				} 

				// إضافة العامل الحالي إلى المكدس
				char_stack.push(infix[i]); 
			} 
		} 
	} 
	return output; 
} 

string infixToPrefix(string infix) 
{ 
	/* قلب السلسلة النصية
	استبدال الأقواس
	الحصول على التعبير المرتب بعديًا ثم قلبه */
	int l = infix.size(); 

	// قلب التعبير المرتب وسطيًا
	reverse(infix.begin(), infix.end()); 

	// تبديل الأقواس
	for (int i = 0; i < l; i++) { 

		if (infix[i] == '(') { 
			infix[i] = ')'; 
			i++; 
		} 
		else if (infix[i] == ')') { 
			infix[i] = '('; 
			i++; 
		} 
	} 

	string prefix = infixToPostfix(infix); 

	// قلب التعبير المرتب بعديًا
	reverse(prefix.begin(), prefix.end()); 

	return prefix; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	string s = ("(a-b/c)*(a/k-l)"); 
	cout << infixToPrefix(s) << std::endl; 
	return 0; 
}

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

*-a/bc-/akl

التعقيد الزمني

تنفّذ العمليات الخاصة بالمكادس مثل push()‎ و pop()‎ في تعقيد زمني خطي، ولمّا كانت الخوارزمية تجري مسحًا على جميع الحروف في التعبير المعطى مرة واحدة فإنّ التعقيد الزمني لهذه الخوارزمية خطّي ويبلغ المقدار O(n)‎.

مصادر

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