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
)
)
)
×
3
)
−
(
2
+
(
1
+
1
)
)
((15÷(7-(1+1)))×3)-(2+(1+1))
((15÷(7−(1+1)))×3)−(2+(1+1))
在我们熟悉的算数表达式中，由三个部分组成：
- 操作数：如1, 2, 3, 4, 5这些
- 运算符：如加减乘除这些
- 界限符：如括号
波兰数学家的灵感
灵感：可以不用界限符也能无歧义地表达运算顺序
Reverse Polish notation（逆波兰表达式 = 后缀表达式）
Polish notation（波兰表达式 = 前缀表达式）
三种算数表达式
（1）中缀表达式
运算符在两个操作数中间：
a
+
b
a + b
a+b
a
+
b
−
c
a+b-c
a+b−c
a
+
b
−
c
∗
d
a+b-c*d
a+b−c∗d
（2）后缀表达式
运算符在两个操作数后面：
a
b
+
a b +
ab+
a
b
+
c
−
ab+c-
ab+c− 或者也可以先算
b
−
c
b-c
b−c，那么结果就是：
a
b
c
−
+
abc-+
abc−+
a
b
+
c
d
∗
−
ab+cd*-
ab+cd∗−
要注意操作数的左右顺序
（3）前缀表达式
运算符在两个操作数的前面：
+
a
b
+ a b
+ab
−
+
a
b
c
-+abc
−+abc，类似的，也可以写成别的形式
−
+
a
b
∗
c
d
-+ab*cd
−+ab∗cd
后缀表达式相关考点
（1）中缀表达式转后缀表达式
中缀转后缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
- 如果还有运算符没有被处理，就继续执行步骤 2
根据以上步骤，在引言中的算数表达式：(
(
15
÷
(
7
−
(
1
+
1
)
)
)
×
3
)
−
(
2
+
(
1
+
1
)
)
((15÷(7-(1+1)))×3)-(2+(1+1))
((15÷(7−(1+1)))×3)−(2+(1+1))
就可以写成：(
3
(
15
(
7
(
11
+
)
−
)
÷
)
×
)
(
2
(
11
+
)
+
)
−
(3(15(7(11+)-)÷)×)(2(11+)+)-
(3(15(7(11+)−)÷)×)(2(11+)+)−
上面算数表达式中的括号应该是去掉的
加在上面是为了便于理解
括号中的 11+，不是 11，而是两个 1
再举一个例子：
A
+
B
×
(
C
−
D
)
−
E
÷
F
A+B×(C-D)-E÷F
A+B×(C−D)−E÷F
转换为后缀表达式就应该是：
A
B
C
D
−
×
+
E
F
÷
−
ABCD-×+EF÷-
ABCD−×+EF÷−
运算顺序不唯一
因此对应的后缀表达式也不唯一
练习：写出
A
+
B
×
(
C
−
D
)
−
E
÷
F
A+B×(C-D)-E÷F
A+B×(C−D)−E÷F 的另一种后缀表达式形式
答案：
A
B
C
D
−
×
E
F
÷
−
+
ABCD-×EF÷-+
ABCD−×EF÷−+
客观来说，两种形式都是正确的
只是“机算”的结果是前者
那么如何才能写出更精确的后缀表达式呢？
使用 “左优先原则”：只要左边的运算符能够先运算，就先计算左边的
这样可以保证运算顺序唯一
举例：
A
+
B
−
C
×
D
÷
E
+
F
A+B-C×D÷E+F
A+B−C×D÷E+F
转换后结果：
A
B
+
C
D
×
E
÷
−
F
+
AB+CD×E÷-F+
AB+CD×E÷−F+
（2）后缀表达式求值
后缀表达式的手算方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的运算顺序
用计算机机算后缀表达式
用栈实现后缀表达式的计算：
- 从左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 3
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1
需要注意的是：先出栈的是右操作数
若表达式合法，则最后栈中只会留下一个元素，也就是最终结果
具体代码实现：
#include
#include
#include
#include
#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
", result);
return 0;
}
代码解释：
const char* postfix的意思？const表示这个字符串指针指向的数据（字符串）是不可变的，即你不能通过这个指针修改字符串的内容。char*表示这个指针指向的是一个字符（char）数组（或者说是一个 C 风格的字符串）。postfix是这个指针的变量名。
- 哪里来的
isdigit函数？isdigit是 C 标准库函数，定义在头文件中。- 这个函数接受一个字符作为参数，判断是否是数字字符（‘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]表示将这个字符赋值给变量chi++是一个后缀自增操作，表示先使用i的当前值，然后再将i增加 1，以备下次使用
前缀表达式相关考点
（1）中缀表达式转前缀表达式
与中缀转后缀类似，不再过多赘述
（2）前缀表达式求值
手算
中缀转前缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
- 如果还有运算符没被处理，就继续执行步骤 2
在这里使用的是右优先原则：
只要右边的运算符能先计算，就先算右边的
机算
用栈实现前缀表达式的计算：
- 从右往左扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 3
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1
注意：先出栈的是左操作数
知识回顾与重要考点
表达式求值问题
- 概念：运算符、操作符、界限符（DIY概念：左操作数、右操作数）
- 三种表达式
- 中缀表达式：运算符在操作数中间
- 后缀表达式（逆波兰式）：运算符在操作数后面
- 前缀表达式（波兰式）：运算符在操作数前面
- 后缀表达式考点
- 中缀转后缀
- 按左优先原则确定运算符的运算顺序
- 根据确定的顺序，依次将各个运算符和与之相邻的两个操作数按规则合体
- 后缀转中缀
- 从左往右扫描，每遇到一个运算符，就按规则解体
- 计算
- 从左往右扫描，遇到操作数就入栈，遇到运算符则弹出两个栈顶元素运算后入栈（先弹出的是右操作数）
- 中缀转后缀
- 前缀表达式
- 中缀转前缀
- 按右优先原则确定运算次序
- 根据确定的次序，依次按规则合体
- 计算
- 从右往左扫描，遇到操作数入栈，遇到运算符就弹出两个栈顶元素运算后入栈（先弹出的是左操作数）
- 中缀转前缀
