表达式求值

Description

给出的表达式全为合法的四则运算表达式，含括号。

Input

每行一个表达式，数字全为int型整数，长度不超过100字符

Output

输出表达式的值，一律保留小数点后4位。

Sample Input

1
1+2
-1+2
-1+(-2)

Sample Output

1.0000
3.0000
1.0000
-3.0000

解法一：

//即使程序写的再差，也要坚持把它写完！
/*
不同的思路，所以写出的程序也有所不同，所以并不存在好坏，没有最好的程序，只有更好的，不是别人的都比自己的好，借鉴别人的一些技巧，没必要全部模仿!
*/
#include <cstdio>
#include <cstring>
int _cp[1<<7][1<<7];
void Init()
{
	memset(_cp,-1,sizeof(_cp));
	_cp['+']['+']=_cp['-']['-']=_cp['+']['-']=_cp['-']['+']=0;
	_cp['*']['*']=_cp['/']['/']=_cp['*']['/']=_cp['/']['*']=0;
	_cp['*']['+']=_cp['*']['-']=_cp['/']['+']=_cp['/']['-']=1;//后面优先级比前面低
	_cp['(']['+']=_cp['(']['-']=_cp['(']['*']=_cp['(']['/']=1;
	//小技巧：对使用到的情况进行初始化
}
bool IsDigit(char c)
{
	if(c>='0' && c<='9')
		return 1;
	return 0;
}
double operation(double f1,char c,double f2)
{
	switch(c)
	{
	case '+':
		return f1+f2;
		break;
	case '-':
		return f1-f2;
		break;
	case '*':
		return f1*f2;
		break;
	case '/':
		return f1/f2;
		break;
	default:
		break;
	}
}
int main()
{
	freopen("data.in","r",stdin);
	const int nMax=105;
	char line[nMax];
	while(gets(line))
	{
		int len=strlen(line);
		line[len]=')';
		line[len+1]='\0';
		double data_stack[nMax];
		char ope_stack[nMax];
		int data_top=-1;
		int ope_top=0;
		ope_stack[0]='(';
		Init();
		bool first=true;
		for(int i=0;i<=len;)
		{
			if(line[i]==')')//括号中内容历编完成的情况
			{
				double f1,f2;
				f2=data_stack[data_top--];
				while(ope_top>=0 && ope_stack[ope_top--]!='(')
					f2=operation(data_stack[data_top--],ope_stack[ope_top+1],f2);
				data_stack[++data_top]=f2;
				i++;
			}
			else if(IsDigit(line[i]))//扫描到数字
			{
				first=false;
				int num=0;
				while(IsDigit(line[i]))//当表达式中可为浮点数时只需要追加小数点判断就行。
				{
					num+=num*10+line[i]-'0';
					i++;
				}
				data_stack[++data_top]=num;
			}
			else if(first && (line[i]=='+' || line[i]=='-'))//+，- 表示数的符号
			{
				int sign=1;
				if(line[i]=='-') sign=-1;
				i++;
				int num=0;
				while(IsDigit(line[i]))
				{
					num+=num*10+line[i]-'0';
					i++;
				}
				data_stack[++data_top]=sign*num;
				first=false;
			}
			else if(_cp[ope_stack[ope_top]][line[i]]>=0)//后面操作符优先级低于前面的情况
			{
				if(ope_stack[ope_top]!='(')
				{
					char c=ope_stack[ope_top--];
					double result=operation(data_stack[data_top-1],c,data_stack[data_top]);
					data_top-=2;
					data_stack[++data_top]=result;
				}
				ope_stack[++ope_top]=line[i];
				i++;
			}
			else
			{
				if(line[i]=='(')
					first=true;
				ope_stack[++ope_top]=line[i++];
			}
		}
		printf("%.4lf\n",data_stack[0]);
	}
	return 0;
}

另一种思路（推荐）：

/*
用栈转换成逆波兰式求解，这个解法较上一解法更清楚一些！推荐
主要步骤：
1）去空字符
2）初始化优先级
3）转换：其中需要注意有:
① +，- 被用作数字符号的判断
② 括号匹配中注意点
③ 运算操作
*/
#include <cstdio>
#include <cstring>
const int nMax=105;
char line[nMax];
double data_stack[nMax];
char opt_stack[nMax];
int data_top,opt_top;
int insp[1<<7],outsp[1<<7];
void init()
{
	insp['#']=outsp['#']=0;

	insp['(']=1;
	outsp[')']=1;
	outsp['(']=6;
	
	insp['+']=insp['-']=2;
	outsp['+']=outsp['-']=3;

	insp['*']=insp['/']=4;
	outsp['*']=outsp['/']=5;
}
void delete_blank()
{
	int i,j;
	for(i=0,j=0;line[i];i++)
	{
		if(line[i]!=' ' && line[i]!='\t')
			line[j++]=line[i];
	}
	line[j]='\0';
}
bool is_digit(char c)
{
	if(c>='0' && c<='9')
		return 1;
	return 0;
}
double calculate(char c)//③
{
	double f2=data_stack[data_top--];
	double f1=data_stack[data_top--];
	switch(c)
	{
	case '+':
		return data_stack[++data_top]=f1+f2;
		break;
	case '-':
		return data_stack[++data_top]=f1-f2;
		break;
	case '*':
		return data_stack[++data_top]=f1*f2;
		break;
	case '/':
		return data_stack[++data_top]=f1/f2;
		break;
	default:
		break;
	}
}
double exchange()
{
	int len=strlen(line);
	for(int i=0;i<len;i++)
	{
		if((line[i]=='+' || line[i]=='-') && (i==0 || line[i-1]=='('))
			data_stack[++data_top]=0;//①
		if(is_digit(line[i]))
		{
			double num=0;
			while(is_digit(line[i++]))
				num+=num*10+line[i]-'0';
			data_stack[++data_top]=num;
			i--;
		}
		else if(insp[opt_stack[opt_top]]<outsp[line[i]])
			opt_stack[++opt_top]=line[i];
		else 
		{
			do
			{
				calculate(opt_stack[opt_top--]);
			}while(insp[opt_stack[opt_top]]>outsp[line[i]]);
			if(opt_stack[opt_top]!='(')
				opt_stack[++opt_top]=line[i];
			else
				opt_top--;//②
		}
	}
	while(opt_stack[opt_top]!='#')
		calculate(opt_stack[opt_top--]);
	return data_stack[0];
}
int main()
{
	freopen("data.in","r",stdin);
	init();
	while(gets(line))
	{
		delete_blank();
		data_top=opt_top=-1;
		opt_stack[++opt_top]='#';
		printf("%.4f\n",exchange());
	}
	return 0;
}

/*
解法二：使用递归实现，很不错的解法。
推荐！
*/

#include <cstdio>
#include <cstring>
const int nMax=105;
char line[nMax];
void init()
{
	int i,j;
	for(i=j=0;line[i];i++)
		if(line[i]!=' ' && line[i]!='\t')
			line[j++]=line[i];
	line[j]='\0';
}
bool is_num(int l,int r)
{
	for(int i=l;i<=r;i++)
		if(line[i]<'0' || line[i]>'9')
			return false;
	return true;
}
double calculate(int l,int r)
{
	int i;
	if(l>r) return 0;
	if(is_num(l,r))
	{
		/*double num=0;
		for(i=l;i<=r;i++)
			num=num*10+line[i]-'0';
		return num;*/
		//方法二：
		double num;
		sscanf(line+l,"%lf",&num);
		return num;
	}
	int p;
	//只需要保证先加减后乘除即可
	for(p=0,i=l;i<=r;i++)
	{
		if(line[i]=='(') p++;
		else if(line[i]==')') p--;
		if(!p && line[i]=='+')
			return calculate(l,i-1)+calculate(i+1,r);
	}
	//for(p=0,i=r;i>=l;i--)//无需逆向搜索
	for(p=0,i=l;i<=r;i++)
	{
		if(line[i]=='(') p++;
		else if(line[i]==')') p--;
		if(!p && line[i]=='-')
			return calculate(l,i-1)-calculate(i+1,r);
	}
	for(p=0,i=1;i<=r;i++)
	{
		if(line[i]=='(') p++;
		else if(line[i]==')') p--;
		if(!p && line[i]=='*')
			return calculate(l,i-1)*calculate(i+1,r);
	}
	//for(p=0,i=r;i>=0;i--)
	for(p=0,i=l;i<=r;i++)
	{
		if(line[i]=='(') p++;
		else if(line[i]==')') p--;
		if(!p && line[i]=='/')
			return calculate(l,i-1)/calculate(i+1,r);
	}
	return calculate(l+1,r-1);
}
int main()
{
	freopen("e:\data.in","r",stdin);
	while(gets(line))
	{
		init();
		printf("%.4lf\n",calculate(0,strlen(line)-1));
	}
	return 0;
}