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

本文主要是介绍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 \div (7 - (1 + 1))) \times 3) - (2 + (1 + 1))$
在我们熟悉的算数表达式中，由三个部分组成：

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

波兰数学家的灵感

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

三种算数表达式

（1）中缀表达式

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

（2）后缀表达式

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

（3）前缀表达式

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

后缀表达式相关考点

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

中缀转后缀的手算方法：

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

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

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

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

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

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

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

（2）后缀表达式求值

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

用计算机机算后缀表达式

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

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到步骤 1；否则执行步骤 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）前缀表达式求值

手算

中缀转前缀的手算方法：

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

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

机算

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

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

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

知识回顾与重要考点

表达式求值问题

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