NYOJ 35

 

表达式求值

时间限制：3000 ms  |  内存限制：65535 KB

难度：4

 

描述

ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

 

输入

第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0

输出

每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入

2
1.000+2/4=
((1+2)*5+1)/4=

样例输出

1.50
4.00

#include<iostream>
#include<cstdio>//sscanf
#include<string>
#include<cstring>
#include<stack>
using namespace std;
char ch[7][7]=
{ 
    {'>','>','<','<','<','>','>'},
    {'>','>','<','<','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'<','<','<','<','<','=',' '},
    {' ',' ',' ',' ',' ',' ',' '},
    {'<','<','<','<','<',' ','='},
};
int sign(char ch)
{
	switch(ch)
	{
		case '+' : return 0;
		case '-'  : return 1;
		case '*'  : return 2;
		case '/'  : return 3;
		case '('  : return 4;
		case ')'  : return 5;
		case '=' : return 6;
		//default : exit(-1);
	}
}
char pri(char a, char b)
{
    return ch[sign(a)][sign(b)];
}
double calc(double a, char oper, double b)
{
	switch(oper)
	{
		case '+' : return a + b;
		case '-' : return a - b;
		case '*' : return a * b;
		case '/' : return a / b;
		//default : exit(-1);
	}
}
int main()
{
	int i,j,k,T;
	cin>>T;
	while(T--)
	{
        string str;
        str.clear();
    	stack <double > num;
    	stack <char> oper;
		cin>>str;
		oper.push('=');
		int d = 0;
		double temp;
		for(i=0;i<str.length();i++)
		{
            /*
            下面是我的中缀式转后缀式时对浮点数的做法 
            if(isdigit(str[i]))
            {
                j=i+1;
                while(isdigit(str[j])||str[j]=='.')
                    j++;
                for(k=i;k<=j-1;k++)
                    printf("%c",str[k]);
                putchar(' ');
                i=j-1;//不是 i=j，因为i还要自增 
            }
            */                
			if(isdigit(str[i])||str[i]=='.')
			{
				sscanf(&str[i],"%lf%n",&temp,&d);
				num.push(temp);
				i=i+d-1;
			}
			else if(!isdigit(str[i])&&str[i]!='.')
			{
				double a, b;
				char ope;
				switch(pri(oper.top(),str[i]))
				{
    				case '<' : oper.push(str[i]); break;
    				case '=' : oper.pop(); break;//左括号遇到有括号 
    				case '>' : //操作符栈里不存在括号 
    					ope = oper.top(); oper.pop();
    					b = num.top(); num.pop();//注意a,b的顺序 
    					a = num.top(); num.pop();
    					num.push(calc(a, ope, b));
    				    i--;break;//别忘了i-- 
    				default : break;
				}
			}
		}
		printf("%.2lf\n", num.top());
		while(!num.empty())
		  num.pop();
		while(!oper.empty())
		  oper.pop();
		
	}
	return 0;
}