Skip to content
This repository has been archived by the owner on Jan 7, 2023. It is now read-only.

DS_Doc_2_7_栈的应用

Jump to bottom
KimYang edited this page Oct 10, 2020 · 1 revision

栈的应用

括号匹配问题

image-20200624163218954

实际过程

image-20200624163415891

####正好匹配

image-20200624163523560

####左右不匹配

image-20200624163548297

右括号单身

image-20200624163638571

左括号单身

image-20200624163721992

整个流程

image-20200624163928215

算法实现

image-20200624164327998

总结

image-20200624164420239

表达式求值

image-20200624164751528

算数表达式是什么？

由三个部分组成（操作数，运算符，界限符）

image-20200624165021200

前/后缀表达式的诞生

image-20200624165107095

中/后/前缀表达式的区别

image-20200624165500339

中转后的过程：

image-20200624165755963

上图中，后缀表达式的算术符的先后次序对应中缀表达式的生效的先后次序，但是这是一定的吗？

image-20200624170300224

左优先原则，可保证运算顺序唯一性，以确定机算算法输出结果的唯一性！!

image-20200624190745666

机算算法实现

image-20200624191112704

image-20200624191355054

中转前的过程

image-20200624191538706

中转后和中转前的区别：

image-20200624191614443

中转前的机算过程：

image-20200624191810971

总结

image-20200624191919379

"左优先"/“右优先”原则和左/右操作数不是专业说法，仅供理解！

表达式求值——具体代码实现

image-20200624192258712

中转后机算

手算过程：

image-20200624192506786

机算过程：

image-20200624193355396

中缀表达式的计算

image-20200624193844266

image-20200624194515343

CPU只能执行单个的加减乘除运算，上边这么搞的意义就是为了将高级程序语言编译成简单的机器码，让CPU去执行！

总结

image-20200624194707110

栈在递归中的应用

递归的过程就是函数调用的过程

image-20200624195132597

image-20200624195412187

适合用“递归”算法解决的问题

image-20200624195452395

求阶乘：

image-20200624195709306

使用递归时，需要注意调用栈溢出！

image-20200624200031925

可以自定义栈将递归算法改造成非递归算法！

求斐波那契数列

image-20200624200155981

总结

image-20200624200214150

Clone this wiki locally