# Infix expression calculation of arithmetic

Infix expression: the operator is in the middle of the operand; for example: 1 + 2 * 3-4 / 5
Suffix expression: operator after operand; for example: 1 2 3 * 4 5 / -+
The advantages of suffix expression: read in order, and stack when encountering operands; pop up the first two operands when encountering operators, and stack the calculation results;

Transformation from infix expression to suffix expression:
Stack st1 and stack st2, st1 put operator, st2 put operand; traversal expression string:
Number encountered: press st2;
Encounter operator: press into st1, but check before pressing. If the current stack top is not empty and the priority of the operator is higher than that of the operator to be pushed (the priority of the operator can be defined by map), then press the operator at the top of the current stack out of the stack into st2 until the priority of the operator is not higher than that of the operator to be pushed.
Finally, the remaining elements of st1 are ejected and pressed into st2, and the output of st2 in reverse order is the suffix expression.

Insufficient: the decimal operand recognition and bracketed expression have not been implemented yet;
Only + - * / four expressions are supported temporarily.

Code:

```#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<map>
#include<stack>

using namespace std;

struct node{
double num;
char op;
bool flag;//true - operand false - Operator
};

string str;
stack<node> st1;
stack<node> st2;
stack<node> st3;//Postfix Expression
map<char,int> op;

double calop(double t1,double t2,char op){
if(op=='+') return t1+t2;
if(op=='-') return t1-t2;
if(op=='*') return t1*t2;
if(op=='/') return t1/t2;
}

void cal(){
while(!st2.empty()){
st3.push(st2.top());
st2.pop();
}
node temp;
double sum;
double temp1,temp2;
char op;

while(!st3.empty()){
if(st3.top().flag){
st2.push(st3.top());
st3.pop();
}else{
temp2=st2.top().num;
st2.pop();
temp1=st2.top().num;
st2.pop();
op=st3.top().op;
st3.pop();
sum=calop(temp1,temp2,op);
temp.flag=true;
temp.num=sum;
st2.push(temp);
}
}
printf("%.2f",st2.top().num);
}

void change(string str){
int len=str.length();
for(int i=0;i<len;i++){
node temp;
double num=0;
if(str[i]<='9'&&str[i]>='0'){
//It's the number.
while(i<len&&str[i]<='9'&&str[i]>='0'){
num=10*num+str[i]-'0';
i++;
}
temp.num=num;
temp.flag=true;
st2.push(temp);
i--;
}
else{
//It's a character.
temp.op=str[i];
temp.flag=false;

while(!st1.empty()&&op[str[i]]<op[st1.top().op]){
st2.push(st1.top());
st1.pop();
}
st1.push(temp);
}
}
while(!st1.empty()){
st2.push(st1.top());
st1.pop();
}
}

int main(){
//	freopen("1.txt","r",stdin);
op['+']=op['-']=1;
op['*']=op['/']=2;
cin>>str;
change(str);
cal();
//	while(!st2.empty()){
//		if(st2.top().flag){
//			printf("%.0f ",st2.top().num);
//			st2.pop();
//		}else{
//			printf("%c ",st2.top().op);
//			st2.pop();
//		}
//	}

}
```

Added by dptr1988 on Wed, 30 Oct 2019 17:42:54 +0200