栈：表达式求值，逆波兰表达式，后缀表达式

做题目的前提：了解栈相关的知识

栈的相关知识：

栈和队列栈：只能在表尾进行插入或删除操作的线性表

• 栈顶：表尾部（操作的一端）
• 栈底：表头部（固定的一端）
• 空栈：不含元素的空表
• 栈的特性：先进后出 / 后进先出
• 栈的操作：进栈（插入元素）、出栈（删除最后插入的元素）栈的顺序结构实现：
• 栈的顺序结构基于数组实现（栈顶指针对应数组下标）
• 栈声明时已预先开辟数组空间，无需动态初始化

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 个元素运算，结果入栈。

计算步骤（栈状态实时展示）

手写笔记：

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; }