In this article, you will write a C++ program to convert infix expression to a postfix expression using stack operations.
This program is written using Turbo C++ compiler on a Windows 7 64-bit PC. You can use any other suitable C++ compiler and it will still work. Make sure to change the syntax according to the compiler you are using.
Problem Definition
The program requires infix expression as an input. Once the input is received, it will do following to convert the infix expression into a postfix expression. This program use a character stack.
- Receive the input expression with a ‘$’ sign at the end.
- Read the characters one at a time.
- If the character is alphabet, do not put on the stack, but print it.
- If the character is non-alphabet then put it on the stack, and print it if the priority is higher than the next character.
- If the character read is ‘(‘, print every thing from the stack until you reach ‘)’ character.
- Stack become empty, you continue with the rest of the expression.
- If you encounter a ‘$’ sign, the infix to postfix is completed.
Source Code – Infix to Postfix
/* C++ Program To Convert Infix Expression
To Postfix Expression */
#include "iostream.h"
#include "string.h"
#include "ctype.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
class ex1 {
char str[50];
public:
void input();
int strprt(char);
int expprt(char);
void convert();
};
//Class declaration ends here
void ex1::input() {
cout << "Enter the Infix expression"<< endl;
cout << "End with $ sign:"<< endl;
cin >> str;
}
int ex1::strprt(char c) {
int pr;
switch(c) {
case '#':
pr = -1;
break;
case '(':
case ')':
pr = 0;
break;
case '*':
case '/':
pr = 2;
break;
case '+':
case '-':
pr = 1;
break;
}
// Switch-Case ends here
return(pr);
}
int ex1::expprt(char c) {
int pr;
switch(c) {
case '(':
pr = 4;
break;
case ')':
pr = 0;
break;
case '*':
case '/':
pr=2;
break;
case '+':
case '-':
pr = 1;
break;
}
return(pr);
}
void ex1::convert() {
int i = 0;
int top = 0;
char stk[50],item;
while(str[i]!= '$') {
item = str[i];
if(isalpha(item)) {
cout<< item;
}
else {
if(item == ')') {
while(stk[top]!='(') {
cout << stk[top];
--top;
}
--top;
}
else {
while((strprt(str[top])) > expprt(item)) {
cout << stk[top];
--top;
}
++top;
stk[top] = item;
}
}
i++;
}
while(top >= 1) {
cout << stk[top];
--top;
}
}
//Function convert ends here
// Main Function
void main() {
ex1 ob;
clrscr();
ob.input();
ob.convert();
getch();
}Output – Infix to Postfix
Enter the Infix expression End with the ‘$’ sign:
(X+(Y*Z))/(X*Z)
Output:
XYZ*+XZ*/
