栈和队列题解

NO.2：表达式求值

今天讲一道学习栈时，绕不开的一道题，就是表达式的求值问题。（反正我是非常不喜欢字符处理性的题目，因为要考虑的细节太多了……）所以我尽量讲的更细致一些，也顺便巩固一下知识点。

题目要求

背景： 我们的教材（《数据结构与算法》-清华第三版）中已经介绍了表达式求值的算法，现在我们将该算法的功能进行扩展，要求可以处理的运算符包括：+、-、*、/、%（整数取余）、^（乘方）。 要求： 采用算符优先算法，计算的中间结果只保留整数。

输入： 第一行为整数N。表示下面有N个表达式 从第二行起的后面N行为N个由整数构成的表达式 输出： 共N行，每行为相应表达式的计算结果。 如果判断出表达式有错误，则输出：error. 如果在计算过程中出现除数为0的情况，则输出：Divide 0.

然后看一下它给的输入输出用例：

1. 4↵
2. 2^3↵
3. 2^0↵
4. 2^3^2↵
5. 2^(3-1)^(10-8)↵

以文本方式显示

1. 8↵
2. 1↵
3. 512↵
4. 16↵

1秒64M测试用例 2以文本方式显示

1. 11↵
2. (2+8↵
3. 2+8)↵
4. 8/0↵
5. 8/(8+5-13)↵
6. 2^(2-5)↵
7. 10-(80-30(/3*3+4↵
8. 10-80-30)/3*3+4↵
9. (2+8)(3+2)↵
10. (2)3(8)↵
11. 30(/3+3)+4↵
12. 10(20-8)+2↵

以文本方式显示

1. error.↵
2. error.↵
3. Divide 0.↵
4. Divide 0.↵
5. error.↵
6. error.↵
7. error.↵
8. error.↵
9. error.↵
10. error.↵
11. error.↵

1秒64M测试用例 3以文本方式显示

1. 2↵
2. 10(10)↵
3. 14*10-(10)2↵

以文本方式显示

1. error.↵
2. error.↵

1秒64M测试用例 5以文本方式显示

1. 14↵
2. 18-32↵
3. 18/4↵
4. 18%3↵
5. 10+20*4↵
6. 10-20/4↵
7. (18-3)*3↵
8. 10*(10)↵
9. (10+2)/(8-10)↵
10. (2*3)/(5*2)↵
11. 10-(80-30)/3*3+4↵
12. (((2+8)*2-(2+4)/2)*2-8)*2↵
13. (((8+2)*(4/2)))↵
14. 10/0↵
15. (10-80*2↵

以文本方式显示

1. -14↵
2. 4↵
3. 0↵
4. 90↵
5. 5↵
6. 45↵
7. 100↵
8. -6↵
9. 0↵
10. -34↵
11. 52↵
12. 20↵
13. Divide 0.↵
14. error.↵

1秒64M

解决思路

首先我们先简单过一遍用栈解决表达式求值问题的原理。先来画图模拟一下表达式求值的过程：

我们有两个栈，OPTR（运算符栈）和OPND（运算数栈）。当遍历到运算数时，直接入栈。而当遍历到运算符时，通过观察可以发现，若OPND为空或当前运算符优先级比运算符栈顶更高则直接入栈；但若当前运算符优先级低于OPND栈顶元素，则OPND（运算数栈）出栈两次，OPTR（运算符栈）出栈一次，然后将三者的元素结果入OPND，再将该运算符入OPTR。

然后我们提炼一下相关的操作，出入OPTR栈、出入OPND栈、比较得出两运算符优先级、计算一个最简单的表达式（两个数一个运算符），其中最关键的应该是如何得出两运算符之间的优先级，这里我们构建一个n阶矩阵：

简单解释一下这张表，

\theta _{1} \theta _{2}

分别代指先出现的符号和后出现的符号，那么当我要比较两者关系时，只需要将一组下标（i，j）对应的关系返回即可。

也就是这样：

#define Nul 0x00 /*Nul意味着不存在这两者的关系*/ char PRI[9][9]= /* 优先级表 */ { {'>','>','<','<','<','<','<','>','>'}, {'>','>','<','<','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'<','<','<','<','<','<','<','=',Nul}, {'>','>','>','>','>','>',Nul,'>','>'}, {'<','<','<','<','<','<','<',Nul,'='} };

很明显这样就建立了符号与数组下标的一一对应关系：

int signswitch( char a ) /* 符号转换 */ { switch( a ) { case '+': return 0; case '-': return 1; case '*': return 2; case '/': return 3; case '%': return 4; case '^': return 5; case '(': return 6; case ')': return 7; case '#': return 8; } }

那么我将可以过找到两个运算符构成的有序数对在表中的对应值，来输出优先级：

char refusal(int i,int j){ return PRI[i][j]; } // i、j就是先后出现的两个运算符通过int signswitch（）转换后的数字

PS：然后这道题与教材上的例题不同的是：教材上默认表达式没有语法错误，但这道题要求考虑程序健壮性，即判断出语法错误，并且做出相关输出。

代码实现

#include <stdio.h> #include <stdlib.h> #include <string.h> #include<math.h> #define Nul 0x00 char cur[100]; //用来预存表达式 char *p=cur; //用来遍历表达式的指针 int operationgFlag=0; //这个是出现除数为0的判断标记 //都使用全局变量是为了方便后续操作，访问 typedef struct optr{ char op[100]; int top; }OPTR; typedef struct opnd{ int num[100]; int top; }OPND; void initoptr(OPTR *optr){ //初始化OPTR optr->op[0]='#'; optr->top=1; } void initopnd(OPND *opnd){ //初始化OPND opnd->top=0; } void pushoptr(OPTR *optr,char a){ //OPTR入栈 optr->op[optr->top++]=a; } void pushopnd(OPND *opnd,int a){ //OPND入栈 return optr->op[--optr->top]; } char popoptr(OPTR *optr){ //OPTR出栈 return optr->op[--optr->top]; } int pooopnd(OPND *opnd){ //OPND出栈 return opnd->num[--opnd->top]; } //这里是两个栈的结构体定义，以及初始化、入栈、出栈的基本操作

然后为了方便大家理解，我就用注释的方式讲解了，大家可以一步一步的看：

//这两个子函数这里可以先不看，之后用到了再回来看 int change(){ int b=0; b=b*10+*p-'0'; p++; while(*p<='9'&&*p>='0'){ //直到不是数字字符 b=b*10+*p-'0'; p++; } return b; } //因为是使用字符输入的，所以一个两位数（及以上）必须是多个字符 //也就是我们要考虑多位数的情况，举个例子：2 3（一个两位数，但其实输入时，是 2 和 3 //两个字符） //所以出现两个连续的数字字符，我们将其合并成为一个完整的数 int operation(int x, int y, char a) { switch( a ) { case '+': return x+y; case '-': return x-y; case '*': return x*y; case '/': if ( y ) return x/y; else { printf("Divide 0.\n"); operationgFlag=1; return 0;} case '%': return ((long int) fmod(x,y)); case '^': if (y>=0 ) return pow(x,y); else { printf("error.\n"); operationgFlag=1; return 0;} } } //将刚才接受的两个运算数和一个运算符，传入并计算出结果 //然后当取商、取模运算的除数为0是输出错误提示 //当幂运算的指数小于0时，打印表示错误（就是默认不考虑这种情况）

下面是主函数部分：

int main (){
	OPTR *optr=(OPTR*)malloc(sizeof(OPTR));
	OPND *opnd=(OPND*)malloc(sizeof(OPND));
	int N;                                   //N是题目中表达式的数量
	scanf("%d\n",&N);
	int flag=0;                              //flag是用来判断括号是否已经成对的标志
	int n1,n2;                               //这三个参数，后面用到的是后你会明白的
	char op;
	while(N--){
		initoptr(optr);                      //然后是初始化这些参数
		initopnd(opnd);
		flag=0;
		operationgFlag=0;                    //判断是否除数为0的标志
		scanf("%s",cur);                     //用cur接收一个表达式
		strcat(cur,"#");                     //strcat将 # 插入cur尾部
                                             //这个地方重点说明一下，大家看一下OPND的初始化
		                                     //第一位也放了一个#，这是为了与这里放入的成对
                                             //表示一个完整表达式的结束
        while(*p!='#'||optr->op[optr->top-1]!='#'){
			if(*p<='9'&&*p>='0'){                    //然后开始遍历这个表达式
				int num=change();                    //中止条件就是p到了最后一个#，或者OPTR
				pushopnd(opnd,num);                  //中没有运算符了
			}                                        //理解了的话可以去看change
			else{
				if(*p=='('&&optr->top-1==0&&opnd->top!=0){
              	printf("error.\n");                     //然后就是这几行，目的是判断表达式
              	goto h;                                 //是否有问题，我举了例子在下面
				}
              
				if ( flag==1 && *p=='(' ) { 
	                printf("error.\n"); 
	                goto h; 
	            } 
	            else if ( *p==')')   
	                flag = 1; 
	            else            
	                flag = 0; 
				switch(refusal(optr->op[optr->top-1],*p)){ //后面的逻辑就比较简单了
					case'<':pushoptr(optr,*p);p++;break;   //当前运算符优先级更高，直接入栈
					case'=':popoptr(optr);p++;break;       //这里提醒大家看下优先级表中  
					case'>':                               //只有一种情况会相等哦
						n1=pooopnd(opnd);                  //当优先级更低时
						n2=pooopnd(opnd);                  //这里就用到n1、n2、op了
						op=popoptr(optr);                  //很好理解是什么吧？
						n2=operation(n1,n2,op);   //就是用来接收出栈的两个数和一个运算符
						if(operationgFlag==1){    //然后大家理解了这里，就可以去看operation
							goto h;
						}
						else{
							pushopnd(opnd,n2);
							break;
						}
					case Nul: 
						printf("error.\n"); 
	                	goto h; 
					}
			}
		}
		if(opnd->top-1 == 0)  //数字栈中只有一个数，那就是最终结果 
            printf("%d\n",opnd->num[opnd->top]); /* 输出 */ 
        else 
           	printf("error.\n"); 
        h:; /* 继续下一个 */ 
	}
	return 0;
}

30 ( 2 + 2 ) //也就是说在出现左括号，前面没有运算符，但却有数字出现，那这个表达式就肯定是错误的 //ps没有运算符，而且没有数子不一定是错的哦，如：( 2 + 2 ) *21 是没有错误的 30 * ( 2 - 1 ) ( 2 + 1 ) //就是当flag还没有重置为0前又出现了左括号，这个表达式也肯定是错误的 //有人可能会有疑问 30 * ( 2 - 1 ) * ( 2 + 1 ) 也错了吗？ //这当然并没有错，因为当右括号后面有别的运算符出现时，就一定会先算括号中的表达式 //那么flag就会被重置为0

最后这个判断也很巧妙：

if(opnd->top-1 == 0) //数字栈中只有一个数，那就是最终结果 printf("%d\n",opnd->num[opnd->top]); /* 输出 */ else printf("error.\n"); h:; /* 继续下一个 */ //大家可以思考一下，如果一个表达式是合法的，那么遍历结束后，OPTR（运算符栈）肯 //定就是空的了，并且OPND（运算数栈）也只会剩下一个数，那就是最终的结果 //如果OPND中还有数的话，那么这个表达式肯定就是非法的

然后我们运行一下：

给出的四个测试用例都没有问题，然后我就开心的提交了！！！

但是我真服了：

居然有一个用例没有过！！！我检查了好久（真的好久，好久……）

然后后发现了这个：

（不出意外应该是这个有关的用例）反正我当时都崩溃了，这意味这，在判断表达式是否合法上，我之前的逻辑有一部分不能用。然后我就开始摆烂了……我直接交了。那这个就留给评论区的大家吧！！！

源代码

表达式求值

写在最后

在我这一坨……的讲解下，你居然还能看到最后，你！！！没错，就是你！！！必成大器！！！我的讲解可能确实有一些繁琐，但是那些确实是我在敲代码中的所想所感，反正真的相信“书读百遍，其意自现”，只要花时间，就能熟练掌握。就像浙大翁恺老师在他的C语言课程中说到：“所有你现在觉得很高大上的东西，只不过是你还没有学了，并不是你不会！”。

希望能与君共勉！！！