Infix to postfix conversion
/* C++ implementation to convert infix expression to postfix*/
#include<iostream>
using namespace std;
const int size = 5;
class Stack{ // Stack Class...
char arr[size];
int top;
public:
Stack()
{
top = -1;
}
void push(char x)
{
top++;
arr[top] = x;
}
char pop()
{
return arr[top--];
}
int peek()
{
return arr[top];
}
bool isfull()
{
if(top>size)
return true;
return false;
}
bool isempty()
{
if(top<-1)
return true;
return false;
}
};
int prec(char c) //Function to return precedence of operators....
{
if(c == '^' || c=='$')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
int main() // Main Driven....
{
Stack s;
string exp="(m*n/o/q^(a+b-d/q))";
string copy_string; // for Storing converstion....
int l = exp.length();
for(int i =0; i<l;i++)
{
if(exp[i] >= 'a' && exp[i] <= 'z') // If the scanned character is an operand, add it to output string....
copy_string+=exp[i];
else if(exp[i]=='(') // If the scanned character is an ‘(‘, push it to the stack....
s.push('(');
// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(exp[i]==')')
{
while(s.peek()!='\0' && s.peek() != '(' )
{
char c = s.peek();
s.pop();
copy_string+=c;
}
if(s.peek()=='(' )
{
char c= s.peek();
s.pop();
}
}
//If an operator is scanned....
else{
while(s.peek() != '\0' && prec(exp[i]) <= prec(s.peek()))
{
char c = s.peek();
s.pop();
copy_string+= c;
}
s.push(exp[i]);
}
}
//Pop all the remaining elements from the stack....
while(s.peek() != '\0')
{
char c = s.peek();
s.pop();
copy_string+= c;
}
cout << copy_string << endl;
return 0;
}
