【数据结构与算法】栈的中缀转后缀 中缀转前缀

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者栈概念栈是一种先进后出LIFOLast In First Out 的线性数据结构类比生活中叠盘子——最后叠上去的盘子先被拿走最下面的盘子最后取出核心操作仅围绕“入栈”和“出栈”展开。和队列类似。只允许在栈顶出入和删除例1,2,3,4四个数字按顺序进栈则可能的出栈顺序是A3,1,4,2 B.2,4,1,3 C.1,3,2,4 D.3,4,1,2答CA:进1,2,3出3此时栈为1,2此时只能先出2再出1 所以1不可能在2前面B:进1,2出2再进3,4出4此时栈为1,3只能先出3C:进1出1进2,3出3此时栈为2出2进4出4可D:进1,2,3出3进4出4此时栈为1,2只能先出21.相关操作概念1、入栈Push将一个元素添加到栈顶使其成为新的栈顶元素。入栈操作需要将元素放到栈顶位置并更新栈顶指针。2、出栈Pop将栈顶元素删除并返回该元素的值。出栈操作需要将栈顶元素删除并更新栈顶指针。3、判空Empty判断栈是否为空即栈中是否没有任何元素。作用检查栈内是否有元素如果栈中没有任何元素返回 true 表示“空”如果栈中存在元素返回 false 表示“非空”。4、获取栈顶元素Top获取栈顶元素的值但不删除该元素。5、销毁栈DestroyStack销毁栈并释放栈占用的存储空间。2.算术表达式的前中后缀表达式对于平时的四则运算表达式也称作中缀表达式存在先乘除后加减从左到右先括号内后括号外的运算法则使得计算机在计算四则运算时非常复杂因此出现了后缀表达式。中转后是从左到右保证栈顶的符号优先级最高遇到相等级别的也要排除栈里的就是说要保证栈顶的元素是最新的最大级别的运算符号相同要弹出中转钱是从右往左走也是保证栈顶是最大优先级别的但是遇到相同级别的不会弹出特性中缀 → 后缀中缀 → 前缀扫描方向从左到右从右到左操作数输出直接输出直接输出但顺序会反转栈的优先级规则栈顶优先级最高栈顶优先级最高但比较时用原优先级括号处理( 入栈) 弹到 () 入栈( 弹到 )括号互换最终结果直接得到需要反转特性中缀 → 后缀中缀 → 前缀扫描方向从左到右从右到左栈的目标保证栈顶是当前最高优先级保证栈顶是当前最高优先级相同优先级处理弹出先来的先走不弹出后来的直接进括号处理( 入栈) 弹到 () 入栈( 弹到 )最后操作直接输出反转输出后缀表达式后缀表达式中所有的字符都出现在运算数字后面。中缀表达式转后缀表达式从左至右遍历中缀表达式遇到数字则输出遇到字符就比较其与栈顶符号的优先级是右括号或优先级小于等于栈顶符号则栈顶元素依次出栈并输出并将当前符号进栈一直到所有字符都输出完成。后缀表达式的运算从左至右遍历后缀表达式遇到数字则入栈遇到运算符则将处于栈顶的两个数字出栈进行运算运算结果入栈直到计算结束。前缀表达式前缀表达式的运算从右至左遍历前缀表达式遇到数字则入栈遇到运算符则将处于栈顶的两个数字出栈进行运算运算结果入栈直到计算结束。中缀表达式转前缀表达式从右至左遍历中缀表达式遇到数字便输出遇到运算符则比较其与栈顶符号的优先级若是左括号或优先级小于栈顶符号则输出并将当前符号进栈一直到所有字符输出结束。简易版转化方法将中缀表达式(ab)*cd-(eg)*h转换为前缀表达式法 1: 加括号法/直接法注意每一个配对的括号内都包含两个子表达式和一个运算符((((ab)*c)d)-((eg)*h))随后将同一括号内的运算符提取到括号前-((*((ab)c)d)*((eg)h))随后将括号去除得到: -*abcd*egh即为前缀表达式变体:将该中缀表达式转换为后缀表达式使用加括号法得到((((ab)c)*d)((eg)h)*)-去掉括号从而得到abc*degh*-例栈与中缀转后缀逆波兰表达式详解在计算机科学中表达式求值是一个非常经典的问题而栈是解决中缀表达式转后缀表达式逆波兰表达式的利器。本文详细讲解这一过程并附带完整 C 示例代码。一、问题背景输入中缀表达式如34*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; stackchar 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; }六、执行示例输入34*2/(1-5)^2^3输出3 4 2 * 1 5 - 2 3 ^ ^ /