#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int getWeight(char ch) {
switch (ch) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default : return 0;
}
}
void infix_postfix(vector<char>& postfix)
{
int i=0;
while(postfix.size()>1)
{
if(isdigit(postfix[i]))
{
i++;
}
else
{
switch(postfix[i])
{
case '+':
{
postfix[i-2]=(postfix[i-2]-48)+ (postfix[i-1]-48)+48;
postfix.erase(postfix.begin()+ i);
postfix.erase(postfix.begin()+ i-1);
break;
}
case '-':
{
postfix[i-2]=(postfix[i-2]-48)- (postfix[i-1]-48)+48;
postfix.erase(postfix.begin()+ i);
postfix.erase(postfix.begin()+ i-1);
break;
}
case '*':
{
postfix[i-2]=(postfix[i-2]-48)* (postfix[i-1]-48)+48;
postfix.erase(postfix.begin()+ i);
postfix.erase(postfix.begin()+ i-1);
break;
}
case '/':
{
postfix[i-2]=(postfix[i-2]-48)/ (postfix[i-1]-48)+48;
postfix.erase(postfix.begin()+ i);
postfix.erase(postfix.begin()+ i-1);
break;
}
}
i=i-1;
}
}
}
void infix2postfix(char infix[], vector<char>& postfix, int size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
while (i < size)
{
ch = infix[i];
if (ch == '(')
{
s.push(ch);
i++;
continue;
}
if (ch == ')')
{
while (!s.empty() && s.top() != '(')
{
// postfix[k++] = s.top();
postfix.push_back(s.top());
s.pop();
}
if (!s.empty())
{
s.pop();
}
i++;
continue;
}
weight = getWeight(ch);
if (weight == 0)
{
// postfix[k++] = ch;
postfix.push_back(ch);
}
else
{
if (s.empty())
{
s.push(ch);
}
else
{
while (!s.empty() && s.top() != '(' &&
weight <= getWeight(s.top()))
{
//postfix[k++] = s.top();
postfix.push_back(s.top());
s.pop();
}
s.push(ch);
}
}
i++;
}
while (!s.empty()) {
//postfix[k++] = s.top();
postfix.push_back(s.top());
s.pop();
}
// postfix[k] = 0;
}
int main() {
char infix[] = "9*5*4-(8-4/2)";
int size = strlen(infix);
// char postfix[size];
vector<char>postfix;
infix2postfix(infix,postfix, size);
cout<<"\nInfix Expression :: "<<infix;
cout<<"\nPostfix Expression :: ";
for(int i=0;i<postfix.size();i++)
cout<<postfix[i];
infix_postfix(postfix);
cout<<"\nanswer="<<(int)postfix[0];
//cout<<endl<<postfix.size()<<endl;
return 0;
}