数据结构3.2栈的应用--表达式求值

• • 算法说明
  • • 代码实现
    • 运行结果

在课上听了上一级学长的代码，觉得受益匪浅。奈何学艺不精，只能在理解代码之后用自己会的c语言来尝试实现。

在上课听的时候，我就在想表达式求值的逻辑究竟是怎样的。首先，我们需要两个栈，一个用于存放数字，一个用于存放运算符。有一个难点是运算符是有优先级顺序的，究竟应该怎么去实现这个优先级，这里借鉴了别人的算法：二维数组。并且（）’优先级最高，‘（’和‘）’优先级相同，故若优先级相同，则说明是括号。如果栈顶运算符和扫描到的运算符相同，则栈顶运算符优先级高。例如：栈顶运算符为‘+’，扫描到的运算符为‘+’或‘-’，则栈顶运算符优先级高运算符优先级解决之后，问题就变得简单多了。

拿（2+3*6）*2+3这个算式来举例子，我们首先遇到（，将其存到运算符栈中，然后是2，把2存到数字栈，接着遇到加号，也存入运算符栈，3存入数字栈，这个时候我们遇到乘号了，
乘号和+的优先级进行比较，乘号优先，又将数字栈中的3取出，让其与乘号之后的6相乘，得到的18存入运算符栈，然后遇到 ），加）与乘号的优先级比较，然后取出2和18，将这两个相加得到20存入数字栈，后面的操作都是同理的。

这里也只展示几段核心代码。
优先级的设置：

#include 
struct Sqstack {
	int data[100];
	int top;
};
char opset[10] = {'+', '-', '*', '/', '(', ')', '#'};
//用来进行比较运算符优先级的矩阵,3代表'=',2代表'>',1代表'<',0代表不可比 
int  cmp[7][7]  = {
        { 2, 2, 1, 1, 1, 2, 2 },
        { 2, 2, 1, 1, 1, 2, 2 },
        { 2, 2, 2, 2, 1, 2, 2 },
        { 2, 2, 2, 2, 1, 2, 2 },
        { 1, 1, 1, 1, 1, 3, 0 },
        { 2, 2, 2, 2, 0, 2, 2 },
        { 1, 1, 1, 1, 1, 0, 3 }  };
Sqstack Num;
Sqstack Oper;

判断运算符:

int In(char ch, char operArr[10]) {
	
	for(int i = 0; i < 7; i++) {
		if(ch == operArr[i]) {
			return 1;
		}
	}
	return 0;
	
}

比较优先级：

char Compare(char oper1, char oper2) {
	int m = 0, n = 0, i, ans;
	char ch;
	for(i = 0; i < 7; i++) {
		if(oper1 == opset[i]) {
			m = i;
		}
		if(oper2 == opset[i]) {
			n = i;
		}
	}
	ans = cmp[m][n];
	switch (ans) {
		case 2:
        	return (char)('<');
    	case 1:
       		return (char)('>');
    	case 3:
        	return (char)('=');
    	default:
     	    printf("表达式错误!n");
       		break;
    }
}

计算：

int Count(int x1, char op, int x2) {
	int val;
	switch(op) {
		case '+': val = x1 + x2; break;
		case '-': val = x1 - x2; break;
		case '*': val = x1 * x2; break;
		case '/': val = x1 / x2; break;
	}
	return val;
}

最重要的函数，也就是进行一系列对表达式的读取分析：

int Cal() {
	
	char ch, x, op, a1, a2, val;
	int data, ans;
	InitStack(Num);//初始化操作数栈 
	InitStack(Oper);//初始化运算符栈
	Push(Oper, '#');//在运算符栈中加入终止符为了进行比较，结束运算
	printf("请输入一个表达式：n");
	ch = getchar();
	while(ch != '#' || GetTop(Oper) != '#') {
		//opset为运算符集合 
		if(!In(ch, opset)) {//如果读入的是操作数 
			data = ch - '0';
			ch = getchar();
			while(!In(ch, opset)){//读入的不是运算符，是操作数
			 	data = data * 10 + ch - '0';//读入操作数的各位数码，并转化为十进制数data 
			 	ch = getchar();
			}
			Push(Num, data);//操作数入栈
		} else {
			switch(Compare(GetTop(Oper), ch)) {
				case '>': 
					Push(Oper, ch); 
					ch = getchar(); 
					break;
				case '=': 
					Pop(Oper, x); 
					ch = getchar(); 
					break;
				case '<': 
					Pop(Oper, op); 
					Pop(Num, a2); 
					Pop(Num, a1); 
					val = Count(a1, op, a2); 
					Push(Num, val); 
					break;
			}
		}
	}
	val = GetTop(Num);
	return val; 
	
} 

请输入一个表达式：
(2+3*6)*2-10#
30