#include <bits/stdc++.
h>
using namespace std;
int defining(char op){
if(op=='^') return 3;
if(op=='*' || op=='/') return 2;
if(op=='+' || op=='-') return 1;
return -1;
}
//infix= operator between operands
//prefix= operator before operands
//postfix= operator after operands
INFIX->POSTFIX
string infixTOpostfix(string s){
stack<char> st;
string res="";
for(int i=0; i<[Link](); i++){
char c= s[i];
//if operand, add to output
if(isalnum(c)){
res+=c;
}
//if'(', push to stack
else if(c=='('){
[Link](c);
}
//if')', pop until '('
else if(c==')'){
while(![Link]() && [Link]()!='('){
res+=[Link]();
[Link]();
}
[Link]();//remove'('
}
//operator
else{
while(![Link]() && defining([Link]()) >= defining(c)){
res+=[Link]();
[Link]();
}
[Link](c);
}
}
//pop remaining operators
while(![Link]()){
res+=[Link]();
[Link]();
}
return res;
}
INFIX->PREFIX
string infixTOprefix(string s){
reverse([Link](), [Link]()) ;
for(int i=0; i<[Link](); i++){
if(s[i]=='(') s[i]=')';
else if(s[i]==')') s[i]='(';
}
stack<char> st;
string res= "";
for(int i=0; i<[Link](); i++){
char c= s[i];
if(isalnum(c)){
res+=c;
else if(c=='('){
[Link](c);
}
else if(c==')'){
while(![Link]() && [Link]()!='('){
res+=[Link]();
[Link]();
}
if(![Link]()) [Link]();
}
else{
while(![Link]() && defining([Link]()) > defining(c)){
res+=[Link]();
[Link]();
}
[Link](c);
}
}
while(![Link]()){
res+=[Link]();
[Link]();
}
reverse([Link](), [Link]());
return res;
}
bool isoperator(char c){
return (c=='+' || c=='-' || c=='*' || c=='/' || c=='^');
}
POSTFIX->INFIX
string postfixTOinfix(string s){
stack<string> st;
for(char c:s){
if(isoperator(c)){
//operator mila toh 2 operands pop kro
string op2= [Link](); [Link]();
string op1= [Link](); [Link]();
//new infix expression bnao
string expr= "(" + op1 + c+ op2 + ")";
[Link](expr);
}
else{
//operand mila->stack me push
[Link](string(1,c));
}
}
return [Link](); //final infix
}
PREFIX->INFIX
string prefixTOinfix(string s){
stack<string> st;
for(int i=[Link]()-1; i>=0; i--){
char c= s[i];
if(isoperator(c)){
string op1= [Link](); [Link]();
string op2= [Link](); [Link]();
string expr= "(" + op1 + c+ op2 + ")";
[Link](expr);
}
else{
[Link](string(1,c));
}
}
return [Link]();
}
POSTFIX->PREFIX
string postfixTOprefix(string s){
stack<string> st;
for(int i=0; i<[Link](); i++){
char c= s[i];
//oprand
if(isalnum(c)){
string op(1,c);
[Link](op);
}
else if(isoperator(c)){
string op1= [Link](); [Link]();
string op2= [Link](); [Link]();
string expr= c+ op2 + op1;
[Link](expr);
}
}
return [Link]();
}
PREFIX->POSTFIX
string prefixTOpostfix(string s){
stack<string> st;
for(int i=[Link]()-1; i>=0; i--){
char c= s[i];
//oprand
if(isalnum(c)){
string op(1,c);
[Link](op);
}
else if(isoperator(c)){
string op1= [Link](); [Link]();
string op2= [Link](); [Link]();
string expr= op1 + op2 + c;
[Link](expr);
}
}
return [Link]();
}
int main(){
string infix= "(a+b-c)^d*(e/f)/g";
cout<<"infix: "<<infix<<endl;
//after conversion from infix to postfix
string postfix= infixTOpostfix(infix);
cout<<"postfix: "<<postfix<<endl;
//after conversion from infix to prefix
string prefix= infixTOprefix(infix);
cout<<"prefix: "<<prefix<<endl;
//after conversion from postfix to infix
string new_infix_frm_postfix= postfixTOinfix(postfix);
cout<<"new infix: "<<new_infix_frm_postfix<<endl;
//after conversion from prefix to infix
string new_infix_frm_prefix= prefixTOinfix(prefix);
cout<<"new infix: "<<new_infix_frm_prefix<<endl;
//after conversion from postfix to prefix
string new_prefix_frm_postfix= postfixTOprefix(postfix);
cout<<"new prefix: "<<new_prefix_frm_postfix<<endl;
//after conversion from prefix to postfix
string new_postfix_frm_prefix= prefixTOpostfix(prefix);
cout<<"new postfix: "<<new_postfix_frm_prefix<<endl;
return 0;
}