03-3.3.2_1 栈在表达式求值中的应用（上）

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

引言

大家熟悉的算数表达式

$((15÷(7-(1+1)))\times 3)-(2+(1+1))$
在我们熟悉的算数表达式中，由三个部分组成：

1. 操作数：如1, 2, 3, 4, 5这些
2. 运算符：如加减乘除这些
3. 界限符：如括号

波兰数学家的灵感

灵感：可以不用界限符也能无歧义地表达运算顺序
Reverse Polish notation（逆波兰表达式 = 后缀表达式）
Polish notation（波兰表达式 = 前缀表达式）

三种算数表达式

（1）中缀表达式

运算符在两个操作数中间：
$a+b$
$a+b-c$
$a+b-c\ast d$

（2）后缀表达式

运算符在两个操作数后面：
$ab+$
$ab+c-$ 或者也可以先算$b-c$，那么结果就是：$abc-+$
$ab+cd\ast -$
要注意操作数的左右顺序

（3）前缀表达式

运算符在两个操作数的前面：
$+ab$
$-+abc$，类似的，也可以写成别的形式
$-+ab\ast cd$

后缀表达式相关考点

（1）中缀表达式转后缀表达式

中缀转后缀的手算方法：

1. 确定中缀表达式中各个运算符的运算顺序
2. 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
3. 如果还有运算符没有被处理，就继续执行步骤 2
   根据以上步骤，在引言中的算数表达式：$((15÷(7-(1+1)))\times 3)-(2+(1+1))$
   就可以写成：$(3(15(7(11+)-)÷)\times )(2(11+)+)-$

上面算数表达式中的括号应该是去掉的
加在上面是为了便于理解
括号中的 11+，不是 11，而是两个 1

再举一个例子：$A+B\times (C-D)-E÷F$
转换为后缀表达式就应该是：$ABCD-\times +EF÷-$

运算顺序不唯一
因此对应的后缀表达式也不唯一

练习：写出$A+B\times (C-D)-E÷F$ 的另一种后缀表达式形式
答案：$ABCD-\times EF÷-+$

客观来说，两种形式都是正确的
只是“机算”的结果是前者

那么如何才能写出更精确的后缀表达式呢？
使用 “左优先原则”：只要左边的运算符能够先运算，就先计算左边的
这样可以保证运算顺序唯一
举例：$A+B-C\times D÷E+F$
转换后结果：$AB+CD\times E÷-F+$

（2）后缀表达式求值

后缀表达式的手算方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的运算顺序

用计算机机算后缀表达式

用栈实现后缀表达式的计算：

1. 从左往右扫描下一个元素，直到处理完所有元素
2. 若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 3
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1

需要注意的是：先出栈的是右操作数
若表达式合法，则最后栈中只会留下一个元素，也就是最终结果

具体代码实现：

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

#define MAX 100 // 定义栈的最大长度 

typedef struct {
	int data[MAX]; 
	int top; 
} IntStack; 

// 初始化整数栈 
void InitIntStack(IntStack *S) {
	S->top = -1; 
} 

// 判断整数栈是否为空 
int IntStackEmpty(IntStack S) {
	return S.top == -1; 
} 

// 整数元素入栈 
void IntPush(IntStack *S, int x) {
	S->data[++S->top] = x; 
} 

// 整数元素出栈 
int IntPop(IntStack *S) {
	if (IntStackEmpty(*S)) {
		return 0; // 栈空返回0 
	} 
	return S->data[S->top--]; 
} 

// 计算后缀表达式的值 
int evaluatePostfix(const char* postfix) {
	IntStack S;
	InitIntStack(&S); 
	int i = 0, num1, num2, result; 
	char ch; 
	
	while ((ch = postfix[i++]) != '\0') {
		if (isdigit(ch)) { 
			int num = 0; 
			while (isdigit(ch)) { 
				num = num * 10 + (ch - '0'); 
				ch = postfix[i++]; 
			} 
			IntPush(&S, num); 
		} else if (ch == ' ') { 
			continue; // 忽略空格 
		} else { 
			num2 = IntPop(&S); 
			num1 = IntPop(&S); 
			switch (ch) { 
				case '+': result = num1 + num2; 
				break; 
				case '-': result = num1 - num2; 
				break; 
				case '*': result = num1 * num2; 
				break; 
				case '/': result = num1 / num2; 
				break; 
			} 
			IntPush(&S, result); 
		} 
	} 
	return IntPop(&S); 
} 

int main() { 
	// 给定的后缀表达式 
	const char postfix[] = "15 7 1 1 + - / 3 * 2 1 1 + + -";
	
	int result = evaluatePostfix(postfix); 
	printf("计算结果: %d\n", result); 
	return 0; 
}

代码解释：

• const char* postfix 的意思？
  • const 表示这个字符串指针指向的数据（字符串）是不可变的，即你不能通过这个指针修改字符串的内容。
  • char* 表示这个指针指向的是一个字符（char）数组（或者说是一个 C 风格的字符串）。
  • postfix 是这个指针的变量名。
• 哪里来的 isdigit 函数？
  • isdigit 是 C 标准库函数，定义在 <ctype.h> 头文件中。
    • 这个函数接受一个字符作为参数，判断是否是数字字符（‘0’-‘9’）
    • 如果是数字字符，返回非零值（通常为1），否则返回0
• num = num * 10 + (ch - '0'); 是什么意思？
  • 这行代码用于将连续的字符数字转换成一个整数。考虑例子，同一个位置的ch是一个数字字符：
    • ch - '0' 将字符数字转换为对应的整数值。例如，‘4’ - ‘0’ 将得到整数 4。
    • num * 10 表示将之前的数向左移动一个十进制位，以便新的数字字符可以追加到末位。
    • 然后加上新的数字，这样可以将多位字符数字连接成一个完整的整数
    • 例如，处理字符串 “123”:
      • '1' - '0' = 1，num = 0 * 10 + 1 => num = 1
      • '2' - '0' = 2，num = 1 * 10 + 2 => num = 12
      • '3' - '0' = 3，num = 12 * 10 + 3 => num = 123
• ch = postfix[i++]; 是什么意思？
  • ch = postfix[i++]; 用来从字符串 postfix 中依次取得字符，并存储到 ch 变量中
    • postfix[i] 是字符串 postfix 的第 i 个字符
    • ch = postfix[i] 表示将这个字符赋值给变量 ch
    • i++ 是一个后缀自增操作，表示先使用 i 的当前值，然后再将 i 增加 1，以备下次使用

前缀表达式相关考点

（1）中缀表达式转前缀表达式

与中缀转后缀类似，不再过多赘述

（2）前缀表达式求值

手算

中缀转前缀的手算方法：

1. 确定中缀表达式中各个运算符的运算顺序
2. 选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
3. 如果还有运算符没被处理，就继续执行步骤 2

在这里使用的是右优先原则：
只要右边的运算符能先计算，就先算右边的

机算

用栈实现前缀表达式的计算：

1. 从右往左扫描下一个元素，直到处理完所有元素
2. 若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 3
3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1

注意：先出栈的是左操作数

知识回顾与重要考点

表达式求值问题

• 概念：运算符、操作符、界限符（DIY概念：左操作数、右操作数）
• 三种表达式
  • 中缀表达式：运算符在操作数中间
  • 后缀表达式（逆波兰式）：运算符在操作数后面
  • 前缀表达式（波兰式）：运算符在操作数前面
• 后缀表达式考点
  • 中缀转后缀
    • 按左优先原则确定运算符的运算顺序
    • 根据确定的顺序，依次将各个运算符和与之相邻的两个操作数按规则合体
  • 后缀转中缀
    • 从左往右扫描，每遇到一个运算符，就按规则解体
  • 计算
    • 从左往右扫描，遇到操作数就入栈，遇到运算符则弹出两个栈顶元素运算后入栈（先弹出的是右操作数）
• 前缀表达式
  • 中缀转前缀
    • 按右优先原则确定运算次序
    • 根据确定的次序，依次按规则合体
  • 计算
    • 从右往左扫描，遇到操作数入栈，遇到运算符就弹出两个栈顶元素运算后入栈（先弹出的是左操作数）