In this article, we will discuss how to convert infix expression to prefix expression using stack.
Infix Expression: Infix expressions are in form Operand Operator Operand. Example, a + b.
Prefix Expression: Prefix expressions are in form Operator Operand Operand. Example, + a b.
For example,
Input Prefix Expression: A + ( B * C ) / F Output Prefix Expression: + A / * B C F
Infix to Prefix Algorithm
- First, reverse the input infix expression.
- After that convert the reversed infix expression to postfix expression.
- Reverse the postfix expression obtained in step 2.
- The expression obtained in step 3 is the corresponding prefix expression of input infix expression.
Note
If you don’t know how to convert infix expression to postfix expression then go here.
Reversing Infix Expression
Reversing infix expression is different from reversing a string. If we simply reverse the infix expression then we will get an error. For example, suppose the input infix expression is A + ( B – C ), its reverse will be ) C – B ( + A which is not a valid expression. After reversing we need to replace every open bracket with a close bracket and every close bracket with an open bracket. After replacing brackets we get ( C – B ) + A.
Example,
Suppose we have an infix expression ( A + B ^ C + D / ( E * F ) ). We need to convert this expression to prefix expression.
STEP 1
Reverse the infix expression. We get, ( ( F * E ) / D + C ^ B + A )
STEP 2
Convert Reversed Infix expression to postfix expression. We get, F E * D / C B ^ – A +.
STEP 3
Reverse the postfix expression obtained in step 2. We get, + A – ^ B C / D * E F.
The required prefix expression is + A – ^ B C / D * E F.
Program
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
bool isOperand(char t)
{
if (t >= 'a' && t <= 'z') return true;
else return false;
}
bool isOperator(char t)
{
switch (t)
{
case '+':
case '-':
case '/':
case '*':
case '^':
return true;
}
return false;
}
// returns operator prece
int prece(char t)
{
if (t == '+' || t == '-') return 1;
if (t == '*' || t == '/') return 2;
if (t == '^') return 3;
return 0;
}
// returns 1 for left associativity and 0 for right associativity
int assoc(char t)
{
if (t == '+' || t == '-' || t == '*' || t == '*') return 1;
if (t == '^') return 0;
}
string convertInfixToPostfix(string infix)
{
// operator stack
stack<char> opStack;
// it stores final postfix expression
string postfix;
// it stores each token of infix expression
char token;
postfix = "";
for (int i = 0; i < infix.length(); ++i)
{
token = infix[i];
if (token == '(')
{
opStack.push(token);
}
else if (isOperand(token))
{
postfix.push_back(token);
}
else if (isOperator(token))
{
while (isOperator(opStack.top()) && (
(prece(opStack.top()) > prece(token)) ||
(prece(opStack.top()) == prece(token) && assoc(opStack.top()) && assoc(token))
)
)
{
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
opStack.push(token);
}
else if (token == ')')
{
while (opStack.top() != '(')
{
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
// pop again to remove extra '(' from the stack
// as it is already paired with ')'
opStack.pop();
}
}
return postfix;
}
// function to reverse infix expression
// Note: we cannot directly use stl to reverse infix expression
// because it we reverse parenthesis too
// we don't want to reverse the parenthesis
// we need to convert open parenthesis to close and close parenthesis to open
void reverse_infix(string &infix)
{
int n = infix.length();
for(int i=0;i<n;++i)
{
if(infix[i]=='(')
{
infix[i] = ')';
}
else if(infix[i]==')')
{
infix[i] = '(';
}
}
reverse(infix.begin(), infix.end());
}
int main()
{
string infix, postfix, prefix;
cout << "Enter Infix Expression: ";
cin >> infix;
// reversing infix expression
reverse_infix(infix);
cout<<"Reversed Infix Expression: "<<infix<<endl;
// putting the infix expression in brackets
infix = "(" + infix + ")";
// converting the reversed infix expression to postfix
postfix = convertInfixToPostfix(infix);
cout<<"Postfix of Reversed Infix Expression: "<<postfix<<endl;
prefix = postfix;
// reversing the postfix expression to obtain prefix expression
reverse(prefix.begin(), prefix.end());
cout << "Prefix Expression: " << prefix << endl;
} Output
Enter Infix Expression: a+b^c-d/(e*f)
Reversed Infix Expression: (f*e)/d-c^b+a
Postfix of Reversed Infix Expression: fe*d/cb^-a+
Prefix Expression: +a-^bc/d*ef Read