数据结构与算法——第3章-如何用栈结构求表达式的值(3.6.1)

发表于 2023-02-01 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 3 分钟

一概述

1.什么是后缀表达式
2.后缀表达式分析
3.后缀表达式演示
4.示例代码

二什么是后缀表达式

通过前面章节的学习，读者已经了解了什么是栈以及栈存储结构的 2 种实现方式（顺序栈和链栈）。
在此基础上，本节教读者用栈解决一个实际问题：如何用栈结构求一个表达式的值？

所谓表达式，就是由变量、常量以及运算符组合而成的式子。
其中，常用的运算符无非 !（阶乘运算符）、^（指数运算符）、+、-、*、/ 、( ) 这几种，
比如 3!+4*2/(1-5)^2 就是一个表达式。

那么，如何用栈结构求一个表达式的值呢？实际上，已经有前辈设计好了一种完美的解决方案。

1929 年，波兰逻辑学家 J・卢卡西维兹提出了一种全新的表示表达式的方法，称为后缀表达式或者逆波兰表达式。

和普通表达式不同，后缀表达式习惯将运算符写在它的运算项之后，
且整个表达式中不用括号 () 表明运算的优先级关系

三后缀表达式分析

以 3! 为例，! 为运算符，3 为运算项，因此 3! 本身就是一个后缀表达式；
再以 4*2 为例，* 为运算符，4 和 2作为它的运算项，其对应的后缀表达式为 4 2+。

在此基础上，我们试着将 3!+4*2/(1-5)^2 转换成后缀表达式，
其过程也就是将表达式中所有运算符放置在它的运算项之后：
1. ! 运算符对应的运算项为 3，转换后得到 3 !；
2. + 运算符对应的运算项是 3! 和 4*2/(1-5)^2，转换之后得到：3! 4*2/(1-5)^2 +；
3. * 运算符对应的运算项是 4 和 2，转换之后得到 4 2 *；
4. / 运算符对应的运算项是 4 2 * 和 (1-5)^2，转换后得到 4 2 * (1-5)^2 /；
5. - 运算符对应的运算项是 1 和 5，转换后得到 1 5 -；
6. ^ 运算符对应的运算项是 1 5 - 和 2 ，转换后得到 1 5 - 2 ^。
整合之后，整个普通表达式就转换成了 3 ! 4 2 * 1 5 - 2 ^ / +，这就是其对应的后缀表达式。

不难发现，后缀表达式完全舍弃了表达式本该有的可读性，
但有失必有得，相比普通表达式，后缀表达式的值可以轻松借助栈存储结构求得。
具体求值的过程是：当用户给定一个后缀表达式时，按照从左到右的顺序依次扫描表达式中的各个运算项和运算符，
对它们进行如下处理：
1.遇到运算项时，直接入栈；
2.遇到运算符时，将位于栈顶的运算项出栈，对于 ! 运算符，取栈顶 1 个运算项；
其它运算符，取栈顶 2 个运算项，第一个取出的运算项作为该运算符的右运算项，
另一个作为左运算项。求此表达式的值并将其入栈。

经过以上操作，直到栈中仅存在一个运算项为止，此运算项即为整个表达式的值。

四后缀表达式演示

以 3 ! 4 2 * 1 5 - 2 ^ / +表达式为例，求值的过程为：

从 3 开始，它是运算项，因此直接入栈：

! 作为运算符，从栈顶取 1 个运算项（也就是 3），求 3! 的值（3! = 321=6）并将其入栈

将 4 和 2 先后入栈

对于 * 运算符，取栈顶 2 个运算项（ 2 和 4），其中先取出的 2 作为 * 的右操作数，4 作为左操作数。求
的 4* 2 的值 8 ，并将其入栈：

将 1 和 5 先后入栈：

对于 - 运算符，取栈顶 2 个运算项（5 和 1），计算出 1-5 的值为 -4，将其入栈

将 2 入栈：

对于 ^ 运算符，取栈顶 2 个运算项（2 和 -4），计算出 -4^2 的值 16 ，将其入栈：

对于 / 运算符，取栈顶 2 个运算项（16 和 8），计算出 8/16 的值 0.5，将其入栈：

对于 + 运算符，取栈顶 2 个运算符（0.5 和 6），计算出 6+0.5 的值 6.5，将其入栈：

由此，整个求值的过程就结束了，最终表达式的值为 6.5

五示例代码

//根据给定的后缀表达式 postexp，计算它的值
typedef struct {
	double data[MAXSIZE];
	int top;
} Stack_num;

void InitStack_num(Stack_num **s) {
	*s = (Stack_num *)malloc(sizeof(Stack_num));
	(*s)->top = -1;
}

bool Push_num(Stack_num **s, double e) {
	if ((*s)->top == MAXSIZE - 1)
		return false;
	(*s)->top++;
	(*s)->data[(*s)->top] = e;
	return true;
}

bool Pop_num(Stack_num **s, double *e) {
	if ((*s)->top == -1)
		return false;
	*e = (*s)->data[(*s)->top];
	(*s)->top--;
	return true;
}

//计算后缀表达式的值
double compvalue(char *postexp) {
	Stack_num *num;
	int i = 1;
	double result;
	double a, b;
	double c;
	double d;
	InitStack_num(&num);
	//依次扫描整个表达式
	while (*postexp != '\0') {
		switch (*postexp) {
			case '+':
				Pop_num(&num, &a);
				Pop_num(&num, &b);
				//计算 b+a 的值
				c = b + a;
				Push_num(&num, c);
				break;
			case '-':
				//计算 b-a 的值
				Pop_num(&num, &a);
				Pop_num(&num, &b);
				c = b - a;
				Push_num(&num, c);
				break;
			case '*':
				Pop_num(&num, &a);
				Pop_num(&num, &b);
				//计算 b*a 的值
				c = b * a;
				Push_num(&num, c);
				break;
			case '/':
				Pop_num(&num, &a); // a是除数
				Pop_num(&num, &b);
				//计算 b/a 的值
				if (a != 0) {
					c = b / a;
					Push_num(&num, c);
				} else {
					printf("除0错误！\n");
					exit(0);
				}
				break;
			case '^':
				Pop_num(&num, &a); // a是指数
				Pop_num(&num, &b);
				//计算 b^a 的值
				if (a != 0) {
					i = 1;
					c = 1;
					while (i <= a) {
						c = c * b;
						i++;
					}
				} else if (b != 0) {
					c = 1;
				} else {
					c = 0;
				}
				Push_num(&num, c);
				break;
			case '!':
				Pop_num(&num, &a);
				//计算 a! 的值
				c = 1;
				i = a;
				while (i != 0) {
					c = c * i;
					i--;
				}
				Push_num(&num, c);
				break;
			default:
				//如果不是运算符，就只能是字符形式的数字，将其转换成对应的整数
				d = 0;
				while (*postexp >= '0' && *postexp <= '9') {
					d = 10 * d + (*postexp - '0');
					postexp++;
				}
				Push_num(&num, d);
		}
		postexp++; //继续下一个字符
	}
	Pop_num(&num, &result);
	return result;
}

六思考

1
2
3

根据上面的讲解，我们学会了如何求后缀表达式的值。
但对于普通用户来讲，另其输入一个正确的后缀表达式显然是不实现的，我们只能要求他们输入一个正确的普通表达式。
这就引出了一个问题，即如何将一个普通表达式转换成后缀表达式？

七参考

C语言中文网—如何用栈结构求表达式的值

0%