5、栈应用-表达式求值

本章内容使用上述栈结构函数，来完成表达式求值操作。

表达式例如：3*(7-2)  或者 (0-12)*((5-3)*3+2)/(2+2) 。

1、实现思路

        a、建立OPTR（运算符）和OPND（数字）两个栈，后输入字符串以'='结束

        b、自左向右扫描表达式

                若读取到数字，直接压入操作数栈，继续处理下一个字符；
                若读取到运算符，比较栈顶算符与读取的算符的优先级：
                            栈顶算符 < 读取的算符

                                将读取的算符压入栈，继续处理下一个字符；
                            栈顶算符 > 读取的算符

                                栈顶算符出栈，从操作数栈中取出两数字，                                                                                       根据出栈算符做运算，运算结果再压入操作数栈，继续处理当前字符；
                            栈顶算符 == 读取的算符

                                  栈顶算符出栈，括号出栈不保存，继续处理下一个字符；

           c、 结束条件是算符栈已空，最后操作数栈出栈输出计算结果。

2、运算符关系表

例如：

        3*(7-2) 

3、代码实现

        3.1、定义全局数组存放合法的运算符

static char opts[] = {'+','-','*','/','(',')','\n'};

        3.2、实现函数判断当前字符是不是运算符        

// 定义函数，判断当前的字符是不是运算符,如果是返回在运算符数组中的下标，如果不是返回-1 
int isOpt(const char ch)
{	
	int len = sizeof(opts) / sizeof(char);
	int i;
	for(i=0;i<len;i++)
	{
		if(opts[i] == ch)
		{
			return i;
		}
	}
	return -1;	
} 

        3.3、实现函数判断栈顶运算符和当前输入运算符的关系

// 定义函数获取栈顶运算符和当前输入运算符之间的关系
char Precede(SElemType ch1,SElemType ch2)
{
	// 根据运算符优先级表格，使用二维数组存储字符之间的关系 
	static char optsRelationArr[7][7] = {
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=',-1},		
		{'>','>','>','>',-1,'>','>'},		
		{'<','<','<','<','<',-1,'='}
	};
	
	// 获取两个字符的排序下标 
	int idx1 = isOpt(ch1);
	int idx2 = isOpt(ch2);
	
	// 字符不存在直接返回-1 
	if(idx1 < 0 || idx2 < 0)  return -1; 
	
	// 合法返回对应关系
	return optsRelationArr[idx1][idx2]; 
}

        ​​​​3.4、实现函数根据运算符求+-*/结果                

// 定义函数进行算数运算
SElemType Operator(SElemType a,SElemType x,SElemType b) 
{
	switch(x)
	{
		case '+':
			return a + b;
		case '-':
			return a - b;
		case '*':
			return a * b;
		case '/':
			return a / b;	
	}
}

        3.5、实现函数求表达式的结果

SElemType EvalueExpression()
{
	// 定义操作数栈和运算符栈
	SqStack OPND,OPTR;
	// 定义变量存储 计算中的两个数据
	SElemType a,b;
	// 定义变量存储数据出现多位数据的运算中间量  12  45这类操作数
	SElemType d;
	// 定义变量存储 运算栈栈顶字符
	SElemType x;
	
	// 定义变量存储用户输入的字符符号
	char c;	
	
	// 初始化操作数栈和运算符栈
	InitStack(&OPND);
	InitStack(&OPTR);
	
	// 现象运算符栈中添加\n作为运算结束
	Push(&OPTR,'\n');
	x = '\n';
	
	// 接收一个字符
	c = getchar();	
	
	// 循环结束数据并运算 
	// 结束条件为 ,循环条件为相反面： !(c=='\n' && x=='\n') 
	while(!(c=='\n' && x=='\n')) 
	{			
		if(isOpt(c) >= 0)
		{			
			// c为运算符 ，比较x和c的大小
			char res = Precede(x,c);
			switch(res) 
			{
				case '<':
					// 当前运算符入栈
					Push(&OPTR,c); 
					// 继续接收下一个字符输入
					//scanf(" %c",&c);
					c = getchar();		
					// 结束匹配
					break;
				case '=':
					// 移除运算符栈顶的运算符  () 和 \n和\n相遇
					Pop(&OPTR,&x);
					// 继续接收下一个字符输入
					//scanf(" %c",&c);	
					c = getchar();	
					// 结束匹配
					break;
				case '>':
					// 移除运算符栈顶的运算符
					Pop(&OPTR,&x);
					// 移除操作数栈栈顶两个数据
					Pop(&OPND,&b);
					Pop(&OPND,&a);
					// 计算后结果入栈
					Push(&OPND,Operator(a,x,b));
					// 结束匹配 
					break;
			}
			
		}
		else if(c >= '0' && c <= '9')
		{			
			d = 0;
			// c为数字字符 -- 注意处理多个数字字符组合成一个数字的情况
			while(c >= '0' && c <= '9')
			{
				d = d * 10 + c - '0';
				// scanf(" %c",&c);	
				c = getchar();	
			}
			// 接收完毕将数据入栈					
			Push(&OPND,d);
		} 	
		else
		{			
			// 非法字符
			printf("出现非法字符\n");
			exit(OVERFLOW); 
		} 
		
		
		// 获取运算符栈顶数据，继续下一轮的运算 
		GetTop(OPTR,&x);
		
	}
	
	/***** 运算结束  *******/ 
	// 移除操作数栈 栈顶元素
	Pop(&OPND,&x);
	
	// 如果操作栈为空则结果为栈顶元素，否则表达式不正确
	if(!StackEmpty(OPND))
	{		
		printf("表达式有问题\n");
		exit(OVERFLOW);
	} 
	
	return x;	 
} 

          3.6、main函数测试结果        

int main(int argc, char *argv[]) {
	printf("请输入算数表达式，负数用(0-正数)表示："); 
	SElemType res = EvalueExpression();
	printf("%d",res);	
	
	return 0;
}