这是一种利用了栈技术的逆波兰算法,算法思想本身不难,难是难在下面这两点:
数据互换,比如char 与double、int互换.或 double、int与string互换等(它们互换都很繁琐).
提取数字含双精度类型(尤其是表达式里提取双精度数据类型是比较繁琐的)。当然也可只提取正整数(若是含有小数则不处理该表达式)。
下面是我写的一个逆波兰算法,由于代码较多发不上来(百度限制了提交),多达500行代码左右。如果你有兴趣想拿去研究的话,可以发给你。主要是用C\C++混合编写。
当然,如果你是使用C#编程语言的话,那么你将不会面对上述的繁琐问题,因为C#有强制型的数据转换功能。
下面是运行效果截图以及主函数的部分调用代码:
逆波兰算法主要是分为两步:
第一步:中缀表达式转为后缀表达式
第二步:对后缀表达式进行计算。
下面对算法原理进行逐一讨论:
逆波兰算法中的中缀转后缀的算法原理是这样的:
第一种情况:由表达式左边开始往右遍历,如果是数字则输出拼到后缀表达式里(出栈的元素也是一 样)。
第二种情况:如果是+-*/四则运算则判断栈顶元素的运算符是否大于当前的符号.(乘除优先于加减),
模拟:如果当前元素是+(或-),而栈顶元素是*(或除),那么,此时栈顶元素依此出栈直至栈顶元素 的优先级不大于当前元素。然后当前元素进栈。
第三种情况:如果当前元素是左括号"(",则进栈。--因为它待与右括号匹配。
第四种情况:如果当前元素是右括号")"则栈顶元素依此出栈,直至与它匹配的左括号"("出栈为止。
对后缀表达式进行计算原理是这样的:
对后缀表达式由左往右方向进行扫描,遇到数字则进栈,遇到运算符号则在栈里依此出栈两组数字进行计算,计算结果依然进栈,反复此操作。最后栈底部最后一个元素就是该表达式的运算结果。