中缀表达式转后缀表达式的方法,步骤和原理及后缀表达式运算方式

大家好，又见面了，我是你们的朋友全栈君。

中缀转后缀 本文大部分资料参考慕课何钦铭老师的数据结构 相关的慕课链接:表达式求值 中缀表达式是最常用的算术表达式,运算符在运算数中间,运算需要考虑运算符优先级. 后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构. 先举个简单的转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 – (后缀) 先进行乘除再进行加减 运算规律,运算数位置不变,改变的是运算符位置 可以推栈实现,用堆栈储存等待中的运算符. 将当前运算符与最后一个等待的运算符比较.

具体转换方式: 1.从左到右进行遍历 2.运算数,直接输出. 3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈) 4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出) 5.运算符,将该运算符与栈顶运算符进行比较, 如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行), 如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符. (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算) 直到优先级大于栈顶运算符或者栈空,再将该运算符入栈. 6.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符.

再来解释一下开始的简单例子

在这里插入图片描述

带括号的运算

在这里插入图片描述

选取慕课里何钦铭老师的案例

在这里插入图片描述

后缀表达式运算步骤: (以堆栈储存) 从左到右,遇到运算符就弹出相应的运算数,运算后再把结果入栈.最终结果就是栈顶数的值. (由于该运算为线性结构,具体运算时是不需要储存输出后的运算符,一般是输出一个运算符就进行一次运算,不像图中要储存输出状态.) 注意点: 有时候’-’(负号)是单目运算符,则要修改运算数. 遇到其他运算符(如幂运算)也类似.

这篇文章只是整理中缀表达式转后缀表达式的方法和理论,目的是为了理解. 具体代码实现看我的另一篇文章(模拟表达式运算). 这部分转换对于初学者来说可能很模糊,建议去看开头链接的那个视频. 如果有什么错误或不足欢迎评论指出.

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/149079.html原文链接：https://javaforall.cn