main.cpp

数据结构中表达式求值算法问题

/****************************************************************************************************************************
     								计算算术表达式			
1.任务：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。
假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符"#"，如：#（7+15）*（23-28/4）#。
引入表达式起始、结束符是为了方便。编程利用"算符优先法"求算术表达式的值。
2.要求：（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
		（2） 显示输入序列和栈的变化过程。
		（3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。                                    
****************************************************************************************************************************/

#include  <stdlib.h>
#include  <stdio.h>
#include <string.h>

typedef struct
{
    char *base;     //指向栈顺序存储结构数组的指针
  
    char *top;      //栈顶指针，指向栈顶元素下一个位置
  
    int stacksize; //当前已分配的存储空间，即栈的最大容量，以元素为单位

}char_stack;//操作符栈

typedef struct
{
	int *base;     //指向栈顺序存储结构数组的指针
	
	int *top;      //栈顶指针，指向栈顶元素下一个位置
	
	int stacksize; //当前已分配的存储空间，即栈的最大容量，以元素为单位
	
}int_stack;//操作数栈

//初始化操作符栈
int  init_char_stack(char_stack &s)
{
     s.base=(char *)malloc(100*sizeof(char));
	 
	 if(!s.base)    //存储分配失败
		 exit(0);
	 
	 s.top=s.base;
	 s.stacksize=100;

	 return  1;
}

//初始化操作数栈
int  init_int_stack(int_stack &s)
{
	s.base=(int *)malloc(100*sizeof(int));
	
	if(!s.base)    //存储分配失败
		exit(0);
	
	s.top=s.base;
	s.stacksize=100;
	
	return  1;
}

//判空函数
int empty_char_stack(char_stack s) 
{
	if(s.top==s.base) //空栈返回1
		return 1;
	else 
		return 0;
}

//判空函数
int empty_int_stack(int_stack s) 
{
	if(s.top==s.base) //空栈返回1
		return 1;
	else 
		return 0;
}

//返回操作符栈顶元素的值
char get_char_top(char_stack s, char &e)
{
	if(s.base==s.top)//对空栈最特殊判断
	{	
		printf("此栈为空！");
	    return 0;
	}
	
	e=*(--s.top);
	
	return e;
}

//返回操作数栈顶元素的值
int get_int_top(int_stack s, int &e)
{
	if(s.base==s.top)//对空栈最特殊判断
	{	
		printf("此栈为空！");
		return 0;
	}
	
	e=*(--s.top);
	
	return e;
}

//操作符栈压栈操作
int char_push (char_stack &s,char e)
{
	if (s.top-s.base>=s.stacksize)//栈满，追加存储空间
	{
		s.base =(char *)realloc(s.base,(s.stacksize+10)*sizeof(char));
		
		if(!s.base) //存储分配失败
			exit(0);
		
		s.top=s.base+s.stacksize;
		
		s.stacksize+=10;//设存储空间增量为10
	}

   *s.top++=e;//元素插入栈顶

   return 1;
}

//操作数栈压栈操作
int int_push (int_stack &s,int e)
{
	if (s.top-s.base>=s.stacksize)//栈满，追加存储空间
	{
		s.base =(int *)realloc(s.base,(s.stacksize+10)*sizeof(int));
		
		if(!s.base) //存储分配失败
			exit(0);
		
		s.top=s.base+s.stacksize;
		
		s.stacksize+=10;//设存储空间增量为10
	}
	
	*s.top++=e;//元素插入栈顶
	
	return 1;
}

//操作符栈出栈操作
char char_pop(char_stack &s,char &e)
{ 
	if (s.base==s.top) //对空栈最特殊判断
	{
		printf("此栈为空！");
		return 0;
	}

	s.top--; //删除栈顶元素
	e=*s.top;
	
	return e;
}

//操作数栈出栈操作
int int_pop(int_stack &s,int &e)
{ 
	if (s.base==s.top) //对空栈最特殊判断
	{
		printf("此栈为空！");
		return 0;
	}
	
	s.top--; //删除栈顶元素
	e=*s.top;
	
	return e;
}

/************************************************************************** 
//int check(char *c) 
//参数： 
//char *c: 输入的字符串 
//返回值： 
//0：字符串中有不符合规定的字符 
//1: 字符串字符符合规定，没有不符合规定的字符. 
//功能： 
//检查字符串中有否除了 0-9, +,-,*,/,(,),#，之外的其他字符， 
//如果有，则返回0, 表示出现错误。 
//若没有，则返回1,表式字符串符合规定。 
**************************************************************************/ 
int check(char *c) 
{ 
	int k=0; 
	char *p;
	p=c;

	while(*c!='\0') //"\0"为结尾
	{ 
		if((*c>='0' && *c<='9') || *c=='+' || *c=='-' || *c=='*' || *c=='/' || *c=='.' || *c=='(' || *c==')' || *c=='#') 
		{ 
			if (*c=='#' && *(c+1)!='\0')//如果'#'出现在不是末尾的位置，则为非法字符
			{
				printf("输入错误，您输入的表达式含有非法字符！\n"); 
				return 0;
			}
			
		} 
		else 
		{ 
			printf("输入错误，您输入的表达式含有非法字符！\n"); 
			return 0; 
		} 
		
		if(*c=='(') 
		{
			k++;
		}
		else if(*c==')') 
		{
			k--;
		}
		
		c++; 
	} 
	if(k!=0) 
	{ 
		printf("输入错误，您输入的表达式括号不匹配！\n"); 
		return 0; 
	} 
	if (*(--c)!='#')//末位之前应该有界限符'#'
	{
		printf("您没有在表达式末尾输入界限符'#'！\n");
		return 0;
	}
	while (*p!='\0')
	{
		if ((*p=='+' || *p=='-' || *p=='*' || *p=='/') && (*(p+1)=='+' || *(p+1)=='-' || *(p+1)=='*' || *(p+1)=='/' || *(p+1)=='#'))
		{
			printf("输入错误，不能出现类似于++,+*,之类的符号！\n");
			return 0;
		}
		p++;
	}

	return 1; 
} 


/**************************************************************************
//该函数用来判断字符C是否为运算符，若是，返回1；不是，则返回0
**************************************************************************/ 
int JudgeOperator(char c)
{
	if (c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#')
		return 1;
	else
		return 0;
}


/************************************************************************** 
//该函数用来判断算符的优先关系,参数为栈顶元素和读取符号
//返回值若为1，则temp的优先级大于c
//返回值若为-1，则temp的优先级小于c
//返回值若为0，则temp的优先级等于c
**************************************************************************/ 
int Precede(char temp,char c)
{
	switch(temp)
	{
	case '+':
	case '-':
		switch(c)
		{
		case '+':
			return 1;
			break;
		case '-':
			return 1;
			break;
		case '*':
			return -1;
			break;
		case '/':
			return -1;
			break;
		case '(':
			return -1;
			break;
		case ')':
			return 1;
			break;
		case '#':
			return 1;
			break;
		}
		break;
	case '*':
	case '/':	
		switch(c)
		{
		case '+':
			return 1;
			break;
		case '-':
			return 1;
			break;
		case '*':
			return 1;
			break;
		case '/':
			return 1;
			break;
		case '(':
			return -1;
			break;
		case ')':
			return 1;
			break;
		case '#':
			return 1;
			break;
		}
	    break;
	case '(':
		switch(c)
		{
		case '+':
			return -1;
			break;
		case '-':
			return -1;
			break;
		case '*':
			return -1;
			break;
		case '/':
			return -1;
			break;
		case '(':
			return -1;
			break;
		case ')':
			return 0;
			break;
		case '#':
			break;
		}
		break;
	case ')':
		switch(c)
		{
		case '+':
			return 1;
			break;
		case '-':
			return 1;
			break;
		case '*':
			return 1;
			break;
		case '/':
			return 1;
			break;
		case '(':
			break;
		case ')':
			return 1;
			break;
		case '#':
			return 1;
			break;
		}
		break;
	case '#':
		switch(c)
		{
		case '+':
			return -1;
			break;
		case '-':
			return -1;
			break;
		case '*':
			return -1;
			break;
		case '/':
			return -1;
			break;
		case '(':
			return -1;
			break;
		case ')':
			break;
		case '#':
			return 0;
			break;
		}
	    break;
	}
}


/*************************************************************************
//该函数用来计算num1 （op）num2
//返回值：result
**************************************************************************/ 
int Evaluate(int num1,int num2,char op)
{
	int result;
	switch(op)
	{
	case '+':
		result=num2+num1;
		break;
	case '-':
		result=num2-num1;
		break;
	case '*':
		result=num2*num1;
	    break;
	case '/':
		result=num2/num1;
	    break;
	}
	return result;
}


/************************************************************************** 
//该函数用来将字符串中连续存放数字的单元，转化为型int的整数
//返回值：该int型的整数
//参数：引用指向算术表达式字符串的指针，p指向了表达式中的一个数字，
//		引用p是为了能够，在函数结束时将其指向数字（可能是多个连续数字）后的符号，便于进行后续读取	
**************************************************************************/ 
int char_to_int(char *&p)
{
	char *p_temp1;
	char array[8]={'\0','\0','\0','\0','\0','\0','\0','\0'};//设整数的最大位数为8位,array[0]为整数十位,array[1]为整数个位，以此类推
	int i,n,j;
	int number=0;//由字符型转化为整型的最后结果
	int radix=0;//基数
	
	p_temp1=p;
	i=0;
	j=0;//记录权值的次方数
	while (!JudgeOperator(*p_temp1))//当p_temp1指向运算符号时退出循环
	{
		array[i]=*p_temp1;
		i++;
		j++;
		p_temp1++;
	}
	
	j--;//j多加了一次，减去
	for (i=0;i<8;i++)
	{
		if (array[i]=='\0')//数字读取完了
		{
			break;
		}
		else
		{
			switch(array[i])//转化单个数字
			{
			case '0':
				radix=0;
				break;
			case '1':
				radix=1;			
				break;
			case '2':
				radix=2;
				break;
			case '3':
				radix=3;
				break;
			case '4':
				radix=4;
				break;
			case '5':
				radix=5;
				break;
			case '6':
				radix=6;
				break;	
			case '7':
				radix=7;
				break;
			case '8':
				radix=8;
				break;
			case '9':
				radix=9;
				break;
			}
			if (j==0)//任何数的0次方都为1，基数就等于其本身
			{
				radix=radix*1;
			}
			if (j>0)
			{			
				for (n=j;n>0;n--)//用基数乘以权值10的次方数
				{
					radix=radix*10;
				}
			}
			number=number+radix;
			j--;//做完一次循环权值的次方数减一
		}
	}

	p=p_temp1;//将移动后的p_temp1赋给p，使其指向下个操作符
	return number;//返回最后结果
}

/************************************************************************** 
该函数用来将字符串中连续存放数字的单元，转化为int型的整数
返回值：该int型的整数
参数：  引用指向算术表达式字符串的指针，p指向了表达式中的一个数字，
		引用p是为了能够，在函数结束时将其指向数字（可能是多个连续数字）后的符号，便于进行后续读取	
**************************************************************************/ 

int EvaluateExpression (char *s)
{
	char_stack OPTR;//操作符栈
	int_stack OPND;//操作数栈
	int a,b;
	int final;//存放最后的结果
	int num;
	char c;
	char temp;//暂存栈顶元素
	char op;//暂存操作符
	char *p_s1;//读取字符串的指针
	p_s1=s;

	init_char_stack(OPTR);
	char_push(OPTR,'#');//'#'作为界限符率先入栈
	init_int_stack(OPND);

	c=*p_s1;
	while (c!='#' || get_char_top(OPTR,temp)!='#')
	{
		if (!JudgeOperator(c))//不是运算符则进栈
		{
			num=char_to_int(p_s1);
			int_push(OPND,num);//将操作数入栈
			c=*p_s1;//p_s1此时已经指向后面的操作符
		}
		else//若为运算符
		{
			switch(Precede(get_char_top(OPTR,temp),c))
			{
			case -1://栈顶元素优先级低
				char_push(OPTR,c);
				p_s1++;
				c=*p_s1;
				break;
			case 0://脱括号并接受下个字符
				char_pop(OPTR,c);
				p_s1++;
				c=*p_s1;
			    break;
			case 1://退栈并将运算结果入栈
				char_pop(OPTR,op);
				int_pop(OPND,a);
				int_pop(OPND,b);
				int_push(OPND,Evaluate(a,b,op));//将运算结果入栈
			    break;
			}
		}
	}
	final=get_int_top(OPND,final);
	return final;
}


void main(void) 
{ 
	char str[100]; 
	int sum=0; 
	int judge=1; 
	
	printf("一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。");
	printf("假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符#，如：#（7+15）*（23-28/4）#。");	
	printf("算符优先法求算术表达式的值。\n");

	printf("\n本程序有效的输入应当仿照本例：1+2*4/2+333-21/(3+4)#\n");
	printf("若您的输入有误本程序会给与相应的提示\n");
	while(1) 
	{ 
		printf("\n\n输入表达式（如果您输入英文小写exit则会退出程序）: \n"); 
		scanf("%s",str); 
		judge=strcmp(str,"exit"); 
		if(judge==0)//如果用户输入了exit
		{
			break; 
		}
		judge=check(str);//判断算术表达式是否有错

		if(judge==0)//如果表达式有错	
		{
			continue; 
		}
		sum=EvaluateExpression(str); //计算算术表达式的值
		printf("%s=%d",str,sum); //屏幕上输出
		printf("\n"); 
	} 
	system("pause");
	system("cls");
	printf("程序结束。\n谢谢使用。\n"); 
}