学步园

    这道题的URL:http://acm.hdu.edu.cn/showproblem.php?pid=1296

    题目的意思是，给出一个多项式和自变量的值，求出多项式的值。

    核心解题思路是每处理出多项式的一个项，便计算出该项的值，并加入最终结果中。但这道题目的边界条件不少，尤其是系数和指数都是默认的情况，处理起来需要些技巧。

    这里给一个不好处理的边界条件：

    input:

     2

     X

     output:

     2

     下面是我的AC代码，和大家分享一下。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

//高效求幂的运算方法
int power(int a, int n)
{
	int r = 1;
	int t = a;
	for(; n; n >>= 1)
	{
		if(n & 1) r *= t;
		t *= t;
	}
	return r;
}

int main()
{
	char exp[10000];
	int x, a, n, r;
	bool positive; //标志当前处理的数是整数还是负数
	bool isCoefficient; //标志当前处理的是系数还是指数
	
	while(cin >> x)
	{
		cin >> exp;
		positive = true;
		isCoefficient = true;
		a = n = 0;
		r = 0;
		int len = strlen(exp);

		//系数默认为1的情况
		if(exp[0] == 'X')
		{
			a = 1;
			isCoefficient = false;
		}
		else a = 0;
		for(int i=0; i<=len; i++)
		{
			if(exp[i] <= '9' && exp[i] >= '0')
			{
				if(isCoefficient)
				{
					a = a * 10 + exp[i] - '0';
				}
				else
				{
					n = n * 10 + exp[i] - '0';
				}
			}
			else if(exp[i] == 'X')
			{
				//指数为1的情况，即默认情况
				if(exp[i+1] == '-' || exp[i+1] == '+' || exp[i+1] == '\0') 
				{
					n = 1;
					isCoefficient = true;
				}
			}
			else if(exp[i] == '-' || exp[i] == '+') //可以求解前面出现的一个完整的项了
			{
				if(!positive) a = -a;
				if(exp[i] == '-')	positive = false;
				else positive  = true;
				r = r + a * power(x, n);
				a = n = 0;
				isCoefficient = true;
				if(exp[i+1] == 'X') a = 1; //系数默认为1的情况
			}
			else if(exp[i] == '^')
			{
				isCoefficient = false;
			}
			else //'\0'
			{
				if(!positive) a = -a;
				r = r + a * power(x, n);
				a = n = 0;
			}
		}
		printf("%d\n", r);
	}
	system("pause");
	return 0;
}