栈的应用-递归和计算器

  • A+

递归

一种在方法内调用自己的思想

它会一层一层调用自己

从而实现调用一次方法

实际调用了很多次该方法

但它必须要有出口

就是到达某些条件后就退出

然后一层一层的往上退出

如果没有出口,你可以自己想一下

while(true)

我在这里用递归测试下

这种思想是不是栈的方式

①这里只要调用方法,就认为它入栈

②只要方法内返回数据,就认为它出栈

我们调用一下Fbi(4)

结果

栈的应用-递归和计算器
可以看出完全符合栈的特性

后进先出

这里就不详细说了

毕竟没有学过编译原理,我不敢乱说


计算器(四则运算表达式求值)

使用后缀表示法(逆波兰法)

①将输入的表达式(中缀表达式)转化为计算机喜欢的后缀表达式

②利用后缀表达式得出结果


思想

中缀表达式转后缀表达式

规则:从左到右遍历中缀表达式,

①如果是数字就直接输出成为后缀表达式的一部分;

②如果是运算符号,则判断它与栈顶的优先级,如果栈为空或栈顶符号优先级低于等于它或是左括号,就将它入栈,否则输出所有优先级大于等于它的运算符号直到栈空或遇到左括号。

③如果是左括号,直接入栈。

④如果是右括号,匹配到前面的左括号,输出之间的运算符号


后缀表达式计算结果

规则:从左遍历后缀表达式

①如果是数字就入栈

②遇到运算符号,就出栈两个数

③进行运算,先出栈的数在右

理论就这么多

实现才是重点!


①这里_expression表面意思,保存输入的表达式

②_elements这个用于顺序保存分隔好的表达式元素

因为数字可能是由好几个字符组成

而我们遍历字符串是一个个字符的处理的

所以需要匹配下区别出来数字区域

③_midStack一个功能型的中间栈用于计算出后缀表达式

再使用它和后缀表达式计算出结果

④_laterString用于顺序保存后缀表达式的元素们

⑤构造函数初始化为100的大小

因为是计算机,使用固定内存是比较实际的(个人看法)


总的计算方法思路

①在做其他操作之前先清空一下各个线性表

②把输入的表达式保存起来,匹配需要使用

③匹配出表达式的所有元素并检查表达式的合法性

④将匹配出来的表达式转换为后缀表达式

⑤利用后缀表达式计算出结果并返回


一、清空

因为每次计算都需要使用这些线性表保存数据

为了保证上一次的计算不会影响到下一次的计算

所以清空一下,保证清清白白的


二、匹配表达式元素

这里用一个index保存遍历进度

exprLength为输入表达式的长度

记录左右括号数的lKuo和rKuo

用while循环遍历整个字符串的所有字符

取得当前字符和下一个字符(如果有,用于判断合法性)

-------------------------------------------------------

如果当前字符是左括号(

1.判断非法情况,非法的情况为:

①(不能表达式的最后一个字符

②它下一个字符是右括号

③它的下一个字符为运算符号

2.如果合法

左括号计数器加一,并保证左括号多于右括号

3.添加左括号到表达式元素中

进度加一

-------------------------------------------------------

如果是右括号

1.右括号计数器+1

2.判断是否为特殊情况的最后字符

是的话直接添加到表达式元素中

进度+1,退出这次循环

3.如果不是,判断合法性,非法条件为:

①)不能是第一个字符

②下一个字符为左括号

③下一个字符是数字

4.检查一下括号的左右对应个数

5.添加)括号到表达式元素中,进度+1

-------------------------------------------------------

剩下的就是运算符号和数字或是非法字符了

这里如果是运算符号

1.判断非法情况,非法的情况为:

①运算符为表达式的第一个字符

②运算符为最后一个字符

③下一个字符为右括号

④下一个字符为运算符

2.合法了,添加运算符到表达式元素中,进度+1,退出这次循环

-------------------------------------------------------

剩下的情况只能是数字了

1.先判断如果不是数字,那么就是非法字符了

2.用一个临时变量用于记录数字的长度(字符长度)

一个临时变量记录是否为小数

3.从当前位置向后寻找数字和小数点

计算出这个数字的字节长度

直到遇到非数字或小数点或到达表达式的最后一个字节

4.从表达式中截取出刚刚得出长度的数字

5.添加数字到表达式元素中,进度+数字的字节长度

-------------------------------------------------------

所有的表达式字符都匹配检查完后

检查一些左括号和右括号数量是否相等


三、中缀转后缀

检查表达式元素数组是否为空

遍历表达式的每个元素

如果是左括号,直接进栈,下一个元素

如果是右括号

匹配前面的左括号

之间的运算符号都出栈加入到后缀表达式中

下一个元素

-------------------------------------------------------

如果是加号或者是减号

①特殊情况,如果栈为空,直接入栈

②获取栈顶元素,比较它们的优先级

③如果栈顶为*或/,优先级较高

符号依次出栈加入到后缀表达式中

知道遇到(或栈中无元素

④将加号或减号入栈

下一个元素

-------------------------------------------------------

如果是*或/号

直接入栈,因为+-*/中它们的优先级高

剩下的元素为数字,直接加入到后缀表达式中

如果该数字为表达式的最后一个元素

则将中转栈中剩余的符号全部出栈加入到后缀表达式中

这样子就可以得到后缀表达式了

保存在_laterString中


四、利用后缀表达式计算出结果

先判断后缀表达式是否为空

-------------------------------------------------------

遍历整个后缀表达式的元素

如果是符号加减乘除

则在栈中出栈两个数字(这时是字符串)

将他们转换成双进度浮点数

进行相应的运算(后出的 运算符 先出的)

得到的结果转换回字符串在加入中转栈中

-------------------------------------------------------

 

排除了加减乘数

剩下就是数字了,直接加入中转栈

遍历完后缀表达式所有元素后

栈中会有一个元素

它就是最后计算出的结果了

取出它,返回它

任务结束


匹配时的判断方法


测试

结果

栈的应用-递归和计算器

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: