👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚正在更新中的专栏：
《数据结构与算法》😊😊😊
《leetcode hot 100》🥰🥰🥰🤩🤩🤩
《数据库mysql》
💕作者简介：后端学习者
栈
概念：栈是一种先进后出（LIFO，Last In First Out） 的线性数据结构，类比生活中叠盘子——最后叠上去的盘子先被拿走，最下面的盘子最后取出，核心操作仅围绕“入栈”和“出栈”展开。和队列类似。
只允许在栈顶出入和删除；
例：1,2,3,4四个数字按顺序进栈，则可能的出栈顺序是？
A，3,1,4,2 B.2,4,1,3 C.1,3,2,4 D.3,4,1,2
答：C；
A:进1,2,3，出3，此时栈为1,2；此时只能先出2再出1 ，所以1不可能在2前面；
B:进1,2，出2，再进3,4，出4，此时栈为1,3，只能先出3，
C:进1，出1，进2,3出3，此时栈为2，出2，进4出4，可
D:进1,2,3出3，进4出4，此时栈为1,2；只能先出2
1.相关操作概念
1、入栈（Push）：将一个元素添加到栈顶，使其成为新的栈顶元素。入栈操作需要将元素放到栈顶位置，并更新栈顶指针。
2、出栈（Pop）：将栈顶元素删除，并返回该元素的值。出栈操作需要将栈顶元素删除，并更新栈顶指针。
3、判空（Empty）：判断栈是否为空，即栈中是否没有任何元素。
作用：检查栈内是否有元素
如果栈中没有任何元素，返回 true （表示“空”）；
如果栈中存在元素，返回 false （表示“非空”）。
4、获取栈顶元素（Top）：获取栈顶元素的值，但不删除该元素。
5、销毁栈（DestroyStack）：销毁栈，并释放栈占用的存储空间。
2.算术表达式的前中后缀表达式
对于平时的四则运算表达式，也称作中缀表达式，存在先乘除，后加减，从左到右，先括号内后括号外的运算法则，使得计算机在计算四则运算时非常复杂，因此出现了后缀表达式。
中转后是从左到右保证栈顶的符号优先级最高，遇到相等级别的也要排除栈里的，就是说要保证栈顶的元素是最新的最大级别的运算符号；相同要弹出
中转钱是从右往左走，也是保证栈顶是最大优先级别的，但是遇到相同级别的不会弹出；
| 特性 | 中缀 → 后缀 | 中缀 → 前缀 |
| 扫描方向 | 从左到右 | 从右到左 |
| 操作数输出 | 直接输出 | 直接输出（但顺序会反转） |
| 栈的优先级规则 | 栈顶优先级最高 | 栈顶优先级最高（但比较时用原优先级） |
| 括号处理 | ( 入栈，) 弹到 ( | ) 入栈，( 弹到 )（括号互换） |
| 最终结果 | 直接得到 | 需要反转 |
| 特性 | 中缀 → 后缀 | 中缀 → 前缀 |
| 扫描方向 | 从左到右 | 从右到左 |
| 栈的目标 | 保证栈顶是当前最高优先级 | 保证栈顶是当前最高优先级 |
| 相同优先级处理 | 弹出（先来的先走） | 不弹出（后来的直接进） |
| 括号处理 | ( 入栈，) 弹到 ( | ) 入栈，( 弹到 ) |
| 最后操作 | 直接输出 | 反转输出 |
后缀表达式
后缀表达式中所有的字符都出现在运算数字后面。
中缀表达式转后缀表达式：从左至右遍历中缀表达式，遇到数字则输出，遇到字符就比较其与栈顶符号的优先级，是右括号或优先级小于等于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，一直到所有字符都输出完成。
后缀表达式的运算：从左至右遍历后缀表达式，遇到数字则入栈，遇到运算符则将处于栈顶的两个数字出栈进行运算，运算结果入栈，直到计算结束。
前缀表达式
前缀表达式的运算：从右至左遍历前缀表达式，遇到数字则入栈，遇到运算符则将处于栈顶的两个数字出栈进行运算，运算结果入栈，直到计算结束。
中缀表达式转前缀表达式：从右至左遍历中缀表达式，遇到数字便输出，遇到运算符则比较其与栈顶符号的优先级，若是左括号或优先级小于栈顶符号则输出，并将当前符号进栈，一直到所有字符输出结束。
简易版转化方法
将中缀表达式(a+b)*c+d-(e+g)*h转换为前缀表达式
法 1: 加括号法/直接法
注意每一个配对的括号内都包含两个子表达式和一个运算符
((((a+b)*c)+d)-((e+g)*h))
随后将同一括号内的运算符提取到括号前
-(+(*(+(ab)c)d)*(+(eg)h))
随后将括号去除得到: -+*+abcd*+egh即为前缀表达式
变体:
将该中缀表达式转换为后缀表达式
使用加括号法得到((((ab)+c)*d)+((eg)+h)*)-
去掉括号从而得到ab+c*d+eg+h*-
例：
栈与中缀转后缀（逆波兰表达式）详解
在计算机科学中，表达式求值是一个非常经典的问题，而栈是解决中缀表达式转后缀表达式（逆波兰表达式）的利器。本文详细讲解这一过程，并附带完整 C++ 示例代码。
一、问题背景
输入：中缀表达式（如
3+4*2/(1-5)^2^3）输出：后缀表达式（如
3 4 2 * 1 5 - 2 3 ^ ^ / +）
目的：后缀表达式便于计算机直接计算，因为它不需要括号即可确定运算顺序。
二、栈的作用
核心思想：
栈用于保存运算符
遇到操作数直接输出
遇到运算符比较优先级决定是否弹栈
遇到括号做特殊处理
三、算法步骤
初始化一个空栈
ops保存运算符，空字符串output保存后缀表达式从左到右遍历中缀表达式的每个字符：
如果是操作数 → 直接输出到
output如果是左括号
(→ 入栈如果是右括号
)→ 弹出栈顶运算符直到遇到左括号如果是运算符：
栈非空且栈顶运算符优先级高（或相等且左结合） → 弹栈输出
当前运算符入栈
遍历结束后，将栈中剩余运算符依次弹出输出
四、运算符优先级与结合性
优先级：
+,-→ 1*,/→ 2^→ 3
结合性：
+,-,*,/→ 左结合^→ 右结合
结合性影响栈中运算符弹出顺序。例如，2^3^2要从右向左结合。
五、完整 C++ 代码示例
#include <iostream> #include <string> #include <stack> #include <cctype> using namespace std; // 获取运算符优先级 int priority(char op) { switch(op) { case '+': return 1; case '-': return 1; case '*': return 2; case '/': return 2; case '^': return 3; default: return 0; } } // 判断是否为右结合运算符 bool isRightAssoc(char op) { return op == '^'; } int main() { string s; cin >> s; stack<char> ops; string output = ""; for (int i = 0; i < s.length(); i++) { char c = s[i]; if (isdigit(c)) { output += c; output += ' '; } else if (c == '(') { ops.push(c); } else if (c == ')') { while (!ops.empty() && ops.top() != '(') { output += ops.top(); output += ' '; ops.pop(); } if (!ops.empty()) ops.pop(); } else { while (!ops.empty() && ops.top() != '(') { if (isRightAssoc(c)) { if (priority(c) < priority(ops.top())) { output += ops.top(); output += ' '; ops.pop(); } else break; } else { if (priority(c) <= priority(ops.top())) { output += ops.top(); output += ' '; ops.pop(); } else break; } } ops.push(c); } } while (!ops.empty()) { output += ops.top(); output += ' '; ops.pop(); } if (!output.empty()) output.pop_back(); cout << output << endl; return 0; }六、执行示例
输入：
3+4*2/(1-5)^2^3输出：
3 4 2 * 1 5 - 2 3 ^ ^ / +
