栈的应用---后缀表达式的计算

步骤一:中缀表达式转后缀表达式

①设立一个操作符栈,用以临时存放操作符;设立一个数组或队列,用以存放后缀表达式。

②从左到右扫描中缀表达式,如果遇到操作数就直接把它们加入到后缀表达式中。

③如果碰到操作符op,就将其优先级与操作符栈的栈顶操作符的优先级比较

· 若op的优先级高于栈顶操作符的优先级,则压入操作符栈。

· 若op的优先级低于或等于栈顶操作符的优先级,则将操作符栈的操作符不断弹出到后缀表达式中,直到op的优先级高于栈顶操作符的优先级

④重复上述操作,直到中缀表达式扫描完毕,之后若操作符栈中仍有元素,则将它们依次弹出至后缀表达式中。

操作符的优先级:乘法==除法>加法==减法,在具体实现上可以用map建立操作符和优先级的映射。


步骤二:计算后缀表达式

从左到右扫描后缀表达式,如果是操作数,就压入栈;如果是操作符,就连续弹出两个操作数(注意:后弹出的是第一操作数,先弹出的是第二操作数),然后进行操作符的操作,生成的新操作数压入栈中。当栈中就存在一个数时,就是最终的答案。

· 注意除法可能导致浮点数,因此操作数类型要设成浮点型。

代码见胡凡算法笔记 P249

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容