main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/********************************************************************************

  42. (算术表达式求值) 输入一个由数字、+，-，*，/ 及括号组成的算术表达式，
 求其值。

 ********************************************************************************/

#include <stdio.h>
#include <ctype.h>

//declears
#define TOKENLEN 256

typedef enum{START,INNUM,DONE}State;

typedef enum{ADD,SUB,MUL,DIV,LPAREN,RPAREN,NUM,ERROR,ENDSTR}TokenType;

//implements
static char TokenString[TOKENLEN]; 

static int index = 0;

static char String[1024];

static TokenType token;

static int getnextchar(void)
{
	return String[index++];
}

static void ungetnextchar(void)
{
	index--;
}

//词法分析
TokenType GetToken(void)
{
	int tokenStringIndex = 0;
	State state = START;
	TokenType currentToken ;
	int save ;

	while(state!=DONE)
	{
		int c = getnextchar();
		save = 1;
		switch(state)
		{
		case START:
			if(isdigit(c))
			{
				state = INNUM;
			}
			else if(c==' ' || c=='\t' || c=='\n')
			{
				save = 0;
			}
			else
			{
				state = DONE;
				switch(c)
				{
				case '+':
                    currentToken=ADD;
					break;
				case '-':
					currentToken=SUB;
					break;
				case '*':
					currentToken=MUL;
					break;
				case '/':
					currentToken=DIV;
					break;
				case '(':
					currentToken=LPAREN;
					break;
				case ')':
					currentToken=RPAREN;
					break;
				case '\0':
					currentToken=ENDSTR;
					break;
				default:
					currentToken = ERROR;
				}
			}

			break;

		case INNUM:
			if (!isdigit(c))
			{ /* backup in the input */
				ungetnextchar();
				save = 0;
				state = DONE;
				currentToken = NUM;
			}
			break;

		case DONE:
			break;
		}
		if(save)
		{
			TokenString[tokenStringIndex++]=(char)c;
		}
		if(state==DONE)
		{
			if(currentToken!=ERROR&&currentToken!=ENDSTR)
			{
				TokenString[tokenStringIndex]='\0';
//				printf("%s\n",TokenString);
			}
			else
			{
				if(currentToken==ERROR)
					printf("ERROR\n");
//				else printf("ENSTRING\n");
			}
		}
	}
	return currentToken;	
}

/*
21	exp->term { addop term }
22	addop->+ | -
23	term->factor { mulop factor }
24	mulop->* | /
25	factor->(exp) | NUM
*/
int exp();

int match(TokenType expect)
{
	int flag=1;
	if(token==expect)
		token=GetToken();
	else flag=0;
	return flag;
}

int makeNum()
{
	int i=0;
	int result=0;
	while(TokenString[i]!='\0')
	{
		result=result*10;
		result+=(int)TokenString[i]&0x0f;
		i++;
	}
	return result;
}

int factor()
{
	int result=0;
	if(token==LPAREN)
	{
		match(LPAREN);
		result=exp();
		match(RPAREN);
	}
	else if(token==NUM)
	{
		result=makeNum();
		match(token);
	}
	return result;
}

int term()
{
	int result=0;
	result=factor();
	while(token==MUL || token==DIV)
	{
		switch(token)
		{
		case MUL:
			match(token);
			result*=factor();
			break;
		case DIV:
			match(token);
			result/=factor();
			break;
		}
		
	}
	return result;
}

int exp()
{
	int result=0;
	result=term();
	while(token==ADD || token==SUB)
	{
		switch(token)
		{
		case ADD:
			match(token);
			result+=term();
			break;
		case SUB:
			match(token);
			result-=term();
			break;
		}
		
	}
	return result;
}

int calculate()
{
	token=GetToken();
	return exp();
}

void main()
{
	//获取表达式
	gets(String);
	//计算,并显示结果
	printf("%d\n",calculate());
}