Infix to Prefix Conversion
“Infix to prefix conversion” is a classic example of stack data structure. Stack can be used to convert given infix expression to corresponding prefix expression.
Operator: Operator are symbols that instruct the computer to perform simple and single tasks. Examples of operators includes + (Addition), – (Subtraction), * (multiplication),… and many more.
Operand: Operands are values or variable on which operator works its tasks. Examples of Operand includes “a”, “b”, 23, 12,.. and many more
Steps for infix to prefix conversion:
- Scan the valid infix expression from right to left.
- Initialize the empty character stack and empty prefix string.
- If the scanned character is an operand, add it to prefix string.
- If the scanned character is closing parenthesis, push it to the stack.
- If the scanned character is opening parenthesis, pop all the characters of the stack and concatenate to the end of the prefix string until closing parenthesis occurs.
- Pop the closing parenthesis.
- If the scanned character is an Operator and the stack is not empty, compare the precedence of the character with the element on top of the stack. If top element of the Stack has higher precedence over the scanned character, pop the stack else push the scanned character to stack. Repeat this step until the stack is not empty and top Stack has precedence over the character.
- Repeat steps 3 to 7 until all characters are scanned.
- If the stack is empty, reverse and return the prefix string.
- Else, pop the elements of the stack and add it to prefix string, and then reverse and return the prefix string.
Example:
Suppose, we want to convert the following infix expression to prefix expression:
Algorithm for converting infix to prefix expression:
Algo infix_to_prefix (infix)
{
// input – valid infix expression.
// output- corresponding prefix expression.
1. i= sizeof(infix)-1;
2. Loop(i>=0)
{
1.If(infix[i] == ‘)’ )
Then push infix[i] into stack.
2.Else if(infix[i] == ‘(‘ )
{
a.Token = popstack();
b.Loop (Token! = ‘)’ )
{
Concatenate Token to prefix string.
Token = popstack ();
}
}
3.Else if(infix[i] is an operator)
{
Ch=peep ();
Loop (stack not empty AND Priority (infix[i]) <priority (Ch))
{
Ch=popstack ();
Concatenate ch to prefix string
Ch=peep ();
}
push infix[i] into stack.
}
4.Else if(infix[i] is an operand)
Then push infix[i] into stack.
}
3. Loop(stack not empty)
{
Ch=popstack ();
Concatenate ch to prefix string.
}
4. Print the prefix string in reverse order.
}// End.
C++ Program for converting infix to prefix expression
/* C++ Program to convert infix to prefix expression */
#include<iostream>
#include<string>
using namespace std;
class stack
{
string item;
int top;
public:
stack()
{
top=-1;
}
void push(char ch)
{
top++;
item[top]=ch;
}
char pop()
{
char ele;
if(isempty())
{
printf("\n stack overflow!!");
return '@';
}
ele=item[top];
top--;
return ele;
}
char peep()
{
return(item[top]);
}
int isempty()
{
if(top==-1)
return 1;
return 0;
}
int priority(char ch)
{
if(ch==')')
return 1;
else if(ch=='+' || ch=='-')
return 2;
else if(ch=='*' || ch=='/')
return 3;
else
return 4;
}
};
int main()
{
string infix,prefix;
char ch,ch2,token,temp;
int i,j=0,len;
stack st;
cout<<"Enter valid infix expression: ";
cin>>infix;
len=infix.size();
for(i=len-1;i>=0;i--)
{
token=infix[i];
if(token==')')
st.push(token);
else if(token=='(')
{
ch=st.pop();
while(ch!=')')
{
prefix.push_back(ch);
ch=st.pop();
}
}
else if(token=='+' || token=='-' || token=='*' || token=='/' || token=='^')
{
ch2=st.peep();
while(!st.isempty() && st.priority(token)<st.priority(ch2))
{
ch=st.pop();
prefix.push_back(ch);
ch2=st.peep();
}
st.push(token);
}
else
st.push(token);
}
while(!st.isempty())
{
ch=st.pop();
prefix.push_back(ch);
}
cout<<"\n The Corresponding Prefix Expression: ";
for(j = prefix.size() - 1;j>=0;j--)
{
cout<<prefix[j];
}
return 0;
}
OUTPUT: Enter valid infix expression: (a+(b*c)/(d-e)) The corresponding Prefix Expression: +a/*bc-de
Related Posts:
- Infix to Postfix Conversion
- Prefix to Infix Conversion
- Prefix to Postfix Conversion
- Postfix to Infix Conversion
- Postfix to Prefix Conversion
- Check whether given Parentheses String are Balanced Parentheses or Not.
- Next Greater Element
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Merge Overlapping Intervals using Stacks
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Length of Longest Valid Substring
- Reverse a String using Stack
- Implement two stacks in a single array
- Print Bracket Number
- Next Greater Frequency Element
- Sort a Stack using Temporary Stack