#include <iostream>
using namespace std;
class Node
{
public:
char data;
Node *next;
};
class stack
{ public:
Node *top;
stack()
{ top=NULL;
}
void push(char x);
char pop();
void display();
};
void stack::push(char x)
{
Node *t=new Node;
t->data=x;
top->next=top;
top=t;
}
char stack::pop()
{ char x;
Node *t=top;
x=top->data;
top=top->next;
delete t;
return x;
}
int isOperand(char x)
{
if(x=='+'||x=='-'||x=='*'||x=='/')
return 0;
else return 1;
}
int pre(char x)
{
if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/')
return 2;
else return 0;
}
int main()
{ stack st;
string infix="a+b*c+d";
st.push('#');
string postfix;
int i=0, j=0;
while(infix[i]!='\0')
{
if(isOperand(infix[i]))
postfix[j++]=infix[i++];
else
{
if(pre(infix[i])>pre(st.top->data))
st.push(infix[i++]);
else
postfix[j++]=st.pop();
}
}
while(st.top)
{
postfix[j++]=st.pop();
}
postfix[j]='\0';
cout<<postfix;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjbGFzcyBOb2RlCnsKICBwdWJsaWM6CiAgY2hhciBkYXRhOwogIE5vZGUgKm5leHQ7Cn07CmNsYXNzIHN0YWNrCnsgcHVibGljOgogIE5vZGUgKnRvcDsKICBzdGFjaygpCiAgeyB0b3A9TlVMTDsKICB9CiAgdm9pZCBwdXNoKGNoYXIgeCk7CiAgY2hhciBwb3AoKTsKICB2b2lkIGRpc3BsYXkoKTsKfTsKdm9pZCBzdGFjazo6cHVzaChjaGFyIHgpCnsKICBOb2RlICp0PW5ldyBOb2RlOwogIHQtPmRhdGE9eDsKICB0b3AtPm5leHQ9dG9wOwogIHRvcD10Owp9CmNoYXIgc3RhY2s6OnBvcCgpCnsgY2hhciB4OwogIE5vZGUgKnQ9dG9wOwogIHg9dG9wLT5kYXRhOwogIHRvcD10b3AtPm5leHQ7CiAgZGVsZXRlIHQ7CiAgcmV0dXJuIHg7Cn0KCmludCBpc09wZXJhbmQoY2hhciB4KQp7CiAgaWYoeD09JysnfHx4PT0nLSd8fHg9PScqJ3x8eD09Jy8nKQogIHJldHVybiAwOwogIGVsc2UgcmV0dXJuIDE7Cn0KaW50IHByZShjaGFyIHgpCnsKICBpZih4PT0nKyd8fHg9PSctJykKICByZXR1cm4gMTsKICBlbHNlIGlmKHg9PScqJ3x8eD09Jy8nKQogIHJldHVybiAyOwogIGVsc2UgcmV0dXJuIDA7Cn0KCmludCBtYWluKCkKeyBzdGFjayBzdDsKICAgc3RyaW5nIGluZml4PSJhK2IqYytkIjsKICBzdC5wdXNoKCcjJyk7CiAgc3RyaW5nIHBvc3RmaXg7CiAgaW50IGk9MCwgaj0wOwogIHdoaWxlKGluZml4W2ldIT0nXDAnKQogIHsKICAgIGlmKGlzT3BlcmFuZChpbmZpeFtpXSkpCiAgICBwb3N0Zml4W2orK109aW5maXhbaSsrXTsKICAgIGVsc2UKICAgIHsKICAgICAgaWYocHJlKGluZml4W2ldKT5wcmUoc3QudG9wLT5kYXRhKSkKICAgICAgc3QucHVzaChpbmZpeFtpKytdKTsKICAgICAgZWxzZQogICAgICBwb3N0Zml4W2orK109c3QucG9wKCk7CiAgICAgIAogICAgfQogIH0KICB3aGlsZShzdC50b3ApCiAgewogICAgcG9zdGZpeFtqKytdPXN0LnBvcCgpOwogIH0KICAgIHBvc3RmaXhbal09J1wwJzsKICAgIGNvdXQ8PHBvc3RmaXg7CiAgfQ==