做题目的前提：了解栈相关的知识
栈的相关知识：
栈和队列栈：只能在表尾进行插入或删除操作的线性表
- 栈顶：表尾部（操作的一端）
- 栈底：表头部（固定的一端）
- 空栈：不含元素的空表
- 栈的特性：先进后出 / 后进先出
- 栈的操作：进栈（插入元素）、出栈（删除最后插入的元素）栈的顺序结构实现：
- 栈的顺序结构基于数组实现（栈顶指针对应数组下标）
- 栈声明时已预先开辟数组空间，无需动态初始化
1. 基础定义（宏、类型、结构体）
// 栈的最大容量 #define MAXSIZE 100 // 栈存储的数据类型 typedef int ElemType; // 顺序栈的结构体定义 typedef struct { ElemType data[MAXSIZE]; int top; // 栈顶指针（取值范围：-1 ~ MAXSIZE-1） } Stack;2. 栈的初始化函数
// 初始化栈：将栈顶指针设为-1（表示空栈） void initStack(Stack *s) { s->top = -1; }3. 判断栈是否为空
// 判断栈是否为空：空栈返回1，非空返回0 int isEmpty(Stack *s) { if (s->top == -1) { printf("空的\n"); return 1; } else { return 0; } }4. 进栈（压栈）函数
// 进栈：将元素e压入栈，成功返回1，栈满返回0 int push(Stack *s, ElemType e) { // 判断栈是否已满 if (s->top >= MAXSIZE - 1) { printf("满了\n"); return 0; } // 栈顶指针上移，存入元素 s->top++; s->data[s->top] = e; return 1; }5. 出栈函数
// 出栈：取出栈顶元素存入*e，成功返回1，空栈返回0 int pop(Stack *s, ElemType *e) { // 判断栈是否为空 if (s->top == -1) { printf("空的\n"); return 0; } // 取出栈顶元素，栈顶指针下移 *e = s->data[s->top]; s->top--; return 1; }6. 获取栈顶元素函数
// 获取栈顶元素：将栈顶元素存入*e，成功返回1，空栈返回0 int getTop(Stack *s, ElemType *e) { // 判断栈是否为空 if (s->top == -1) { printf("空的\n"); return 0; } // 取出栈顶元素（不移动栈顶指针） *e = s->data[s->top]; return 1; }力扣题链接
20. 有效的括号 - 力扣（LeetCode）
视频参考
栈的拿手好戏！| LeetCode：20. 有效的括号_哔哩哔哩_bilibili
题目：
类似题：有效括号，可参考这篇博客
栈：有效括号-CSDN博客
力扣：
150. 逆波兰表达式求值 - 力扣（LeetCode）
参考视频：
栈的最后表演！ | LeetCode：150. 逆波兰表达式求值_哔哩哔哩_bilibili
pta题目：
解析题目：
看这个题目很懵，不知道怎么就得出这个数了？
在这之前，我们先了解一下逆波兰表达式，也是后缀表达式
123*+就是逆波兰表达式，（3*2）+1
笔记：
A.了解什么事后缀表达式/逆波兰表达式
1. 中缀表达式
- 定义：运算符位于两个操作数中间的表达式，称为中缀表达式。
- 示例：
1+2×3 - 编译系统的处理局限：直接从前往后读取中缀表达式时，无法区分运算符的优先级；因此实际中，编译系统会将中缀表达式转换为后缀表达式（逆波兰表达式）。
2. 后缀表达式/逆波兰表达式
- 定义：算术表达式中，运算符位于对应操作数的后面。
- 示例：中缀表达式
1+2×3对应的后缀表达式为1 2 3 × + - 计算示例（以上述后缀为例）：这个计算，也是二叉树的中序排序（参考视频中的例子），先算
2×3=6，再算1+6=7
B.核心操作
遇到数字入栈，遇到操作符出栈，计算完毕再入栈
计算目标
基于中缀表达式(1+2)×(3+4)，其对应的后缀表达式为：1 2 + 3 4 + ×，以下是该后缀表达式的计算过程。
核心规则
遇到数字 → 入栈；遇到运算符 → 弹出栈顶 2 个元素运算，结果入栈。
计算步骤（栈状态实时展示）
| 步骤 | 操作（处理后缀字符） | 栈的状态（栈顶在右侧） | 运算过程 |
|---|---|---|---|
| 1 | 处理数字1 | [1] | 数字入栈 |
| 2 | 处理数字2 | [1, 2] | 数字入栈 |
| 3 | 处理运算符+ | 先弹出2、1，运算1+2=3，结果入栈 | [3] |
| 4 | 处理数字3 | [3, 3] | 数字入栈 |
| 5 | 处理数字4 | [3, 3, 4] | 数字入栈 |
| 6 | 处理运算符+ | 先弹出4、3，运算3+4=7，结果入栈 | [3, 7] |
| 7 | 处理运算符× | 先弹出7、3，运算3×7=21，结果入栈 | [21] |
| 8 | 计算结束 | 最终栈顶值21 | 即表达式结果 |
手写笔记：
C.总结：
栈的特性适合处理 “相邻字符的消去运算操作”，是后缀表达式求值的核心数据结构。
pta答案：
c语言版
#include <stdio.h> #include <ctype.h> // 用于判断数字字符 // 1. 基础定义（仅保留必需部分） #define MAXSIZE 20 // 适配题目：表达式不超过20字符 typedef double ElemType; // 浮点型适配除法精度 typedef struct { ElemType data[MAXSIZE]; int top; // 栈顶指针（-1表示空栈） } Stack; // 2. 栈的初始化函数（必需） void initStack(Stack *s) { s->top = -1; } // 4. 进栈（压栈）函数（必需） int push(Stack *s, ElemType e) { if (s->top >= MAXSIZE - 1) { return 0; } s->top++; s->data[s->top] = e; return 1; } // 5. 出栈函数（必需） int pop(Stack *s, ElemType *e) { if (s->top == -1) { return 0; } *e = s->data[s->top]; s->top--; return 1; } // 主函数：后缀表达式求值 int main() { char expr[21]; // 存储后缀表达式（最多20字符+结束符） Stack s; // 定义栈变量 // 多组输入，处理到文件尾 while (scanf("%s", expr) != EOF) { initStack(&s); // 初始化栈 // 遍历表达式字符 for (int i = 0; expr[i] != '\0'; i++) { if (isdigit(expr[i])) { // 数字转浮点型压栈 ElemType num = (double)(expr[i] - '0'); push(&s, num); } else { // 运算符：弹出两个操作数计算 ElemType a, b, res; pop(&s, &b); // 右操作数 pop(&s, &a); // 左操作数 // 运算逻辑 switch (expr[i]) { case '+': res = a + b; break; case '-': res = a - b; break; case '*': res = a * b; break; case '/': res = a / b; break; default: res = 0; } push(&s, res); // 结果压栈 } } // 输出最终结果（保留两位小数） ElemType result; pop(&s, &result); printf("%.2f\n", result); } return 0; }力扣答案：
c语言版
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXSIZE 10000 // 适配 tokens 最大长度 10^4 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针（-1 表示空栈） } Stack; // 初始化栈 void initStack(Stack *s) { s->top = -1; } // 压栈 int push(Stack *s, int val) { if (s->top >= MAXSIZE - 1) return 0; s->data[++s->top] = val; return 1; } // 出栈（结果存入 *val） int pop(Stack *s, int *val) { if (s->top == -1) return 0; *val = s->data[s->top--]; return 1; } // 判断是否为运算符 int isOperator(char *token) { return strcmp(token, "+") == 0 || strcmp(token, "-") == 0 || strcmp(token, "*") == 0 || strcmp(token, "/") == 0; } int evalRPN(char** tokens, int tokensSize) { Stack s; initStack(&s); // 初始化栈 for (int i = 0; i < tokensSize; i++) { char *token = tokens[i]; if (isOperator(token)) { // 弹出两个操作数计算 int b, a, res; pop(&s, &b); pop(&s, &a); // 按运算符计算（除法向零截断） if (strcmp(token, "+") == 0) res = a + b; else if (strcmp(token, "-") == 0) res = a - b; else if (strcmp(token, "*") == 0) res = a * b; else res = a / b; // 除法 push(&s, res); } else { // 数字转整数压栈（支持负数） int num = atoi(token); push(&s, num); } } // 栈顶即为结果 int result; pop(&s, &result); return result; }
