stack.cpp

// C++program to convert infix expression to prefix expression
//reverse a string first
//convert to postfix,then reverse the output

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

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

int priority(char a) 
{ 
	if (a == '-' || a == '+') 
		return 1; 
	else if (a == '*' || a == '/') 
		return 2; 
	else if (a == '^') 
		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 the scanned character is an 
		// operand, add it to output. 
		if (isalpha(infix[i]) || isdigit(infix[i])) 
			output += infix[i]; 

		// If the scanned character is an 
		// ‘(‘, push it to the stack. 
		else if (infix[i] == '(') 
			char_stack.push('('); 

		// If the scanned character is an 
		// ‘)’, pop and output from the stack 
		// until an ‘(‘ is encountered. 
		else if (infix[i] == ')') { 

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

			// Remove '(' from the stack 
			char_stack.pop(); 
		} 

		// Operator found 
		else { 
			
			if (isOperator(char_stack.top())) { 
				while (priority(infix[i]) 
				<= priority(char_stack.top())) { 
					output += char_stack.top(); 
					char_stack.pop(); 
				} 

				// Push current Operator on stack 
				char_stack.push(infix[i]); 
			} 
		} 
	} 
	return output; 
} 

string infixToPrefix(string infix) 
{ 
	/* Reverse String 
	* Replace ( with ) and vice versa 
	* Get Postfix 
	* Reverse Postfix * */
	int l = infix.size(); 

	// Reverse infix 
	reverse(infix.begin(), infix.end()); 

	// Replace ( with ) and vice versa 
	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 postfix 
	reverse(prefix.begin(), prefix.end()); 

	return prefix; 
} 

// Driver code 
int main() 
{ 
  cout<<"Enter a expression to convert from infix to prefix:";
	string s;
  cin>>s;
	cout << "The prefix expression is:" << infixToPrefix(s) << std::endl; 
	return 0; 
}