逆波兰表达式又叫做后缀表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式,解决了四则运算中括号改变运算符优先级的问题。
四则运算的表达式一般都是中缀表达式如 1+2*(3-4)+5,即操作符在两个操作数之间。四则运算需要两个步骤,一是把中缀表达式转为后缀表达式,二是由后缀表达生成结果
中缀表达式转为后缀表达式算法描述:
(1)首先有个包含中缀表达式元素列表sourceList,然后创建一个符号列表destList保存最终后缀表达式,创建一个操作符堆栈opStack
(2)从sourceList取出一个元素A
(3a)如是数字则加入到destList中
(3b)如果元素A是运算符,将操作符A与操作符堆栈opStack栈顶的运算符的优先关系相比较。如果,优先关系高于opStack栈顶的运算符,则将该运算符压入操作符堆栈opStack。倘若不是(低于或等于)的话,则将运算符栈opStack栈顶的运算符从栈中弹出保存到destList,重复此步骤,直到作符A压入操作符堆栈opStack。
(3c)若元素A是左括号"(",则压入操作符堆栈opStack
(3d)若元素B是右括号")",则操作符堆栈opStack弹出操作符并加入到destList中,直到弹出左括号"("。
(5)从步骤2重复上述操作,所有元素处理完毕后将操作符堆栈opStack弹出操作符并加入到destList中,这样中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
示例:
中缀表达式如 1+2*(3-4)+5,构造元素列表1,+,2,*,(,3,-,4,),5,构造一个空最终后缀表达式destList,一个操作符堆栈opStack
1、取出“1”,destList【1】,opStack【】
2、取出“+”,destList【1】,opStack【+】
3、取出“2”,destList【1,2】,opStack【+】
4、取出“*”,destList【1,2】,opStack【+,*】
5、取出“(”,destList【1,2】,opStack【+,*,(】
6、取出“3”,destList【1,2,3】,opStack【+,*,(】
7、取出“-”,destList【1,2,3】,opStack【+,*,(,-】
8、取出“4”,destList【1,2,3,4】,opStack【+,*,(,-】
9、取出“)”,destList【1,2,3,4,-】,opStack【+,*】 //操作符堆栈opStack弹出操作符并加入到destList中,直到弹出左括号"("
10、取出“+”,destList【1,2,3,4,-,*,+】,opStack【+】 //加号优先级不大于【+,*】
11、取出“5”,destList【1,2,3,4,-,*,+,5】,opStack【+】
12、处理完毕,destList【1,2,3,4,-,*,+,5,+】,opStack【】
后缀表达式到计算结果算法描述:
遍历储存后缀表达式的列表,将元素依次进栈,当遇到操作符时,连续出栈两个元素,进行运算,再将结果进栈,最后栈内留下的元素就是计算结果
示例:
后缀表达式destList【1,2,3,4,-,*,+,5,+】,结果堆栈resultStatck【】
格式
输入-->:结果
[1,2,3,4]-->:resultStatck【1,2,3,4】
[-]-->:resultStatck【1,2,3-4】
[ * ]-->:resultStatck【1,2*(3-4)】
[+]-->:resultStatck【1+2*(3-4)】
[5]-->:resultStatck【1+2*(3-4),5】
[+]-->:resultStatck【1+2*(3-4)+5】
分享到:
相关推荐
使用逆波兰表达式实现的四则运算解析库、计算器
通过把输入的中缀表达示转换为逆波兰式实现整数及小数的四则运算,为了简便,这个程序只支持小括号,中括号和大括号暂不支持,需要的话自己插入几句代码就行了。 gcc下编译通过,没在window下测试。
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验
逆波兰表达式_课程设计.doc 逆波兰表达式_课程设计.doc
易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言...
逆波兰表达式的C++实现,用类封装,用于计算逆波兰表达式
使用C++模拟了计算器的四则运算,包括加减乘除以及括号优先级运算,主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式,然后再进一步计算逆波兰表达式的值,具体算法思路在主页,资源包括一个main.cpp文件...
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
逆波兰表达式的长 度不超过一行,以 "$"作为输入结束,操作数之间用空格分隔,操作符只可能有+、—、*、/四种 运算。例如: 23434 + 2*$。 数据结构作业
基于c语言的将算术中缀表达式转化为逆波兰表达式,注释清晰且代码打头有写好的思想。
使用c语言实现,将给定的运算表达式翻译成逆波兰表达式的形式
C语言之逆波兰表达式完整代码(附算法),详细讲解其实现
工具提供四则运算解析功能。将.hpp文件引入C++工程中即可使用。详情用法参见文件中注释
【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法
源代码 博文链接:https://leon-a.iteye.com/blog/186104
逆波兰表达式及其算法实现 很好的资料 里面分析很全面
以字符串的形式输入一个算术表达式,转换为逆波兰表达式,并求取其数值。
中缀表达式转换成逆波兰表达式、c语言编写、用栈来实现
逆波兰表达式转为中缀表达式,求值,堆栈,队列,链表