# HDU - 1237 simple calculator (infix expression evaluation)

Read in a non negative integer calculation expression containing only +, -, *, / and calculate the value of the expression.

Input

The test input contains several test cases. Each test case occupies one line with no more than 200 characters. Integers and operators are separated by a space. No illegal expression. When there is only 0 in a line, the input ends and the corresponding result is not output.

Output

Output 1 line for each test case, that is, the value of the expression, accurate to 2 decimal places.

Sample Input

```1 + 2
4 + 2 * 5 - 7 / 11
0```

Sample Output

```3.00
13.36```

Problem solving ideas:

https://blog.csdn.net/MM__1997/article/details/78115962

analysis:

Infix expression evaluation ， no parentheses in the title ， parentheses in the code

First, we know the precedence of operators computing method

Set two stacks, one symbol stack and one number stack

Initialize the symbol stack #, and press a "#" into the space

Treat the resulting string as containing only numbers and operators, and add "#" at the end of #

Scan processed string

If it is scanned as an operator, the operator is compared with the operator at the top of the symbol stack

If the priority of the operator at the top of the stack is lower than the operator, the operator is put on the stack

If the priority of the top of stack operator is equal to this operator, * bracket operation, * pop up the top of stack operator

If the top of the stack operator has higher priority than this operator ， pop up two numbers from the number stack and operate with the top of the stack operator ， press the calculation result back into the number stack ， and pop up the top of the stack operator ， put this operator on the stack

If the scan is digital, press the number into the digital stack

Finally, the top element of the digital stack is the result

King's way explanation: AC Code:

```#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<stack>
using namespace std;

char str;
char ans;
char *sep=" ";//Separator
char *p;

double cal(double a,double b,char c)
{
if(c=='+') return a+b;
if(c=='-') return a-b;
if(c=='*') return a*b;
if(c=='/') return a/b;
}

int judge(char p1,char p2)
{
if(p1=='+'||p1=='-')
{
if(p2=='+'||p2=='-'||p2==')'||p2=='#') return 1;
else return -1;
}
else if(p1=='*'||p1=='/')
{
if(p2=='(') return -1;
else return 1;
}
else if(p1=='(')
{
if(p2==')') return 0;
else return -1;
}
else if(p1==')') return 1;
else if(p1=='#')
{
if(p2=='#') return 0;
else return -1;
}
}

int main()
{
while(gets(str))
{
int len=strlen(str);
str[len]=' ';
str[len+1]='#';
stack<char> s1;//Symbol stack
stack<double> s2;//Digital stack
s1.push('#');
p=strtok(str,sep);
int l=0;
memset(ans,0,sizeof(ans));
do
{
strcpy(ans[l++],p);
}while
(
p=strtok(NULL,sep)
);
if(!strcmp(ans,"0")&&l==2) break;
int index=0;
while(ans[index]!='#'||s1.top()!='#')
{
if(!isdigit(ans[index]))//As operator
{
char temp=s1.top();
int tt=judge(temp,ans[index]);
if(tt==-1)
{
s1.push(ans[index]);
index++;
}
else if(tt==0)
{
s1.pop();
index++;
}
else if(tt==1)
{
double a=s2.top();
s2.pop();
double b=s2.top();
s2.pop();
s2.push(cal(b,a,s1.top()));
s1.pop();
}
}
else//As operator
{
s2.push(atof(ans[index]));
index++;
}
}
printf("%.2lf\n",s2.top());
}
return 0;
}```

Tags: acm Hdu

Posted by stormcloud on Sat, 21 May 2022 19:24:15 +0300