首页 > 代码库 > NYoj-35-表达式求值-栈

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 <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
//#include <map>
#include<queue>
#include<stack>
using namespace std;
int map[7][7]=    //算符间的优先关系,100表示不会出现的情况,1表示i>j ,-1表示i<j,0表示( ) 
{
	{1,1,-1,-1,-1,1,1},
	{1,1,-1,-1,-1,1,1},
	{1,1,1,1,-1,1,1},
	{1,1,1,1,-1,1,1},
	{-1,-1,-1,-1,-1,0,100},
	{1,1,1,1,100,1,1},
	{-1,-1,-1,-1,-1,100,0}
};
int Switch(char c)
{
	switch(c)
	{
	case '+':return 0;
	case '-':return 1;
	case '*':return 2;
	case '/':return 3;
	case '(':return 4;
	case ')':return 5;
	case '#':return 6;
	}
}
double calculate(double x,char c,double y)
{
	switch(c)
	{
	case '+':return x+y;
	case '-':return x-y;
	case '*':return x*y;
	case '/':return x/y;
	}
}
int judge(char c)
{
	if('0'<=c&&c<='9'||c=='.')
    return 1;

return 0;
}
char str[1005];
char optr[1005];
double opnd[1005];
int main()
{
	int t1,t2,k,len,t,temp1,temp2;;
	char ch,zz;
	double a,b;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		gets(str);
		len=strlen(str);
		str[len-1]='#'; //处理的等于号
		t1=t2=k=0;
		optr[t1++]='#';
		ch=str[k++];
	    while(ch!='#'||optr[t1-1]!='#')
		{
	        if(judge(ch)==1)  //操作数入栈
			{
				opnd[t2++]=atof(&str[k-1]); //把字符串转换成浮点数
				while(judge(str[k])==1)
				     k++;
				ch=str[k++];
			}
			else 
			{
				temp1=Switch(optr[t1-1]);    //栈顶运算符 
				temp2=Switch(ch);           //当前运算符 
				if(map[temp1][temp2]==-1)  //栈顶运算符优先级低
				{
                      optr[t1++]=ch;
					  ch=str[k++];
				}
				else if(map[temp1][temp2]==0) //脱括号并接受下一个字符
				{
                      t1--;
					  ch=str[k++];
				}
				else    //退栈并将运算结果保存在数据栈中 
				{
                      zz=optr[--t1];
					  a=opnd[--t2];
					  b=opnd[--t2];
					  opnd[t2++]=calculate(b,zz,a);
				}
			}
		}
		printf("%.2lf\n",opnd[0]);
	}
	return 0;
}
函数说明: atof()会扫描参数nptr字符串,跳过前面的空格字符,直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时(‘\0‘)才结束转换,并将结果返回。参数nptr字符串可包含正负号、小数点或E(e)来表示指数部分,如123.456或123e-2。返回值 返回转换后的浮点型数。


NYoj-35-表达式求值-栈