我们把平时所用的标准四则运算表达式,即a + b − a ∗ ( ( c + d ) / e − f ) + g 叫做中缀表达式。因为所有的运算符号都在两数字的中间;但是中缀表达式不方便计算机理解;现在我们的问题就是中缀到后缀的转化。
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出;
若是符号,则比较其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。
例:将中缀表达式a + b − a ∗ ( ( c + d ) / e − f ) + g 转化为相应的后缀表达式。
分析:需要根据操作符的优先级来进行栈的变化,我们用icp来表示当前扫描到的运算符ch的优先级,该运算符进栈后的优先级为isp,则运算符的优先级如下表所示isp是栈内优先( in stack priority)数,icp是栈外优先( in coming priority)数]。
我们在表达式前后面加上符号‘#’(根据下表优先级为0),表示表达式结束。具体转换过程如下:
具体图示:
转换后结果是:ab+acd+e/f-*-g+
水平有限,难免有误,欢迎大家斧正~
喜欢本文的朋友请三连哦!!!
另外本文也参考了网络上其他优秀博主的观点和实例,这里虽不能一一列举但内心属实感谢无私分享知识的每一位你们。