What is Infix expression?
An expression which is like an "a operand b" (a*b), where an operator between any pair of operands is known as Infix expression. For example (A * B + C / D) is an infix expression.
What is a Postfix expression?
The expression which is in the form of ab operands, where an operator is followed by each and every pair of operands is known as Postfix expression. For example (A B * C D / +) is a postfix expression.
Then now, if we want to convert infix to postfix using C++? Do we have any program to convert infix to postfix using C++? Yes, now we are going to share the easiest method to do this conversion.
We have an example of what we are going to do.
|
Input (Infix expression)- A * B + C / D Output (Postfix expression)- AB*CD/+ |
Or
|
Input (Infix expression)- A * (B + C) / D Output (Postfix expression)- ABC+*D/ |
Program To Convert Infix to Postfix using C++
Algorithm
Take an infix expression as an input with a user and scan the infix expression from left to right.
If scanned character == operand, print it as output.
Else,
- If the precedence of the operator in the stack is less than the precedence of the scanned operator (either the given stack is empty or contains a ‘(‘ ), push it.
- Else pop out all the operators from the stack >= precedence of the scanned operator. Now, push the scanned operator in the stack. (If you get any parenthesis while scanning then stops and push the operator in the stack.)
If the scanned character is ‘(‘, then add it to the stack.
If the scanned character is an ‘)’, then pop out the stack and output it until a ‘(‘ is found again. Also, discard both the parenthesis.
Repeat the above methods 2 to 5 times until the infix expression is completely scanned.
Print the output as a postfix expression
Program
// Program to convert infix to postfix expression using C++ (Stack Method)
|
#include #include #define MAX 20 using namespace std;
char stk[20]; int top=-1; // Create a function to push, inserts value in stack and increments stack top by 1 void push(char oper) { if(top==MAX-1) { cout<<"stackisfull!!!!"; }
else { top++; stk[top]=oper; } } // Create a Function to remove an item from stack. It decreases top by 1 char pop() { char ch; if(top==-1) { cout<<"stackisempty!!!!"; } else { ch=stk[top]; stk[top]='\0'; top--; return(ch); } return 0; } int priority ( char alpha ) { if(alpha == '+' || alpha =='-') { return(1); }
if(alpha == '*' || alpha =='/') { return(2); }
if(alpha == '$') { return(3); }
return 0; } string convert(string infix) { int i=0; string postfix = ""; while(infix[i]!='\0') { if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z') { postfix.insert(postfix.end(),infix[i]); i++; } else if(infix[i]=='(' || infix[i]=='{' || infix[i]=='[') { push(infix[i]); i++; } else if(infix[i]==')' || infix[i]=='}' || infix[i]==']') { if(infix[i]==')') { while(stk[top]!='(') { postfix.insert(postfix.end(),pop()); } pop(); i++; } if(infix[i]==']') { while(stk[top]!='[') { postfix.insert(postfix.end(),pop()); } pop(); i++; }
if(infix[i]=='}') { while(stk[top]!='{') { postfix.insert(postfix.end(),pop()); } pop(); i++; } } else { if(top==-1) { push(infix[i]); i++; }
else if( priority(infix[i]) <= priority(stk[top])) { postfix.insert(postfix.end(),pop());
while(priority(stk[top]) == priority(infix[i])){ postfix.insert(postfix.end(),pop()); if(top < 0) { break; } } push(infix[i]); i++; } else if(priority(infix[i]) > priority(stk[top])) { push(infix[i]); i++; } } } while(top!=-1) { postfix.insert(postfix.end(),pop()); } cout<<"The converted postfix expression is : "< return postfix; }
int main() { int cont; string infix, postfix; cout<<"\n Please Enter the infix expression : "; //enter the expression cin>>infix; postfix = convert(infix); return 0; } |
 |
Read How to convert String to Arry in C++
|
Article Contributed By :
|
|
|
|
|
2566 Views |
|