原文：http://www.jianshu.com/p/5728607674e4
你还在为开发中频繁切换环境打包而烦恼吗？快来试试 Environment Switcher 吧！使用它可以在app运行时一键切换环境，而且还支持其他贴心小功能，有了它妈妈再也不用担心频繁环境切换了。https://github.com/CodeXiaoMai/EnvironmentSwitcher
上一章：程序猿必修课之数据结构（六）栈1
栈的应用——递归
斐波那契（Fibonacci）是一个经典的递归例子。
斐波那契数列
数字 1，1，2，3，5，8，13......构成一个序列，它的特点是：前面相邻两项之和是后一项的值。用数学函数来定义是：
用递归实现打印出前 40 位的斐波那契数列数的代码如下：
# include<stdio.h>
int Fbi(int);
int main() {
int i;
for (i = 0; i < 40; i++) {
printf("%d ", Fbi(i));
}
return 0;
}
int Fbi(int i) {
if (i == 0)
return 0;
if (i == 1)
return 1;
/* 函数调用自己 */
return Fbi(i - 1) + Fbi(i -2);
}
函数调用自己，可以理解为调用另一个函数，只不过，这个函数和自己一样而已。
递归的定义
一个直接或通过一系列的调用语句间接的调用自己的函数，称为递归函数。
每个递归定义必须至少有一个条件满足时递归不再进行，即不再调用自己而是返回值并退出。
迭代和递归的区别
迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易理解，但是大量的递归调用会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。所以，凡事都有利有弊，我们应该视情况选择合适的方式。
栈的应用——四则运算表达式求值
后缀（逆波兰）表示法
对于"9 + (3 -1）X 3 + 10 ÷ 2" ，如果要用后缀表示法应该是"9 3 1 - 3 * + 1 0 2 / +"，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。
我们把平时所用的标准四则运算表达式 ，即 9 + ( 3-1 ) X 3 + 10 ÷ 2 叫做中缀表达式，因为所有的运算符号都在两数字的中间。那么如何将中缀表达式转换为后缀表达式呢？
中缀表达式转后缀表达式
中缀表达式转后缀表达式的规则是：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出；若是符号，就判断其与栈顶符号的优先级，如果是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，再将当前符号进栈......直到最终输出后缀表达式为止。
按照上面的规则，把 9 + ( 3 - 1 ) X 3 + 10 ÷ 2 转换为后缀表达式
用 temp 表示当前输出过的所有内容，用 stack 表示存储运算符的栈。
- 第一个字符是数字 9，temp = "9"；后面是符号“+”进栈，stack = "+";
- 第三个字符是“（”，因为它是左括号，所以进栈，stack = "+ (";
- 第四个字符是数字 3，所以 temp = "9 3"；后面是符号“-”进栈，stack = “+ （ -”；
- 第六个字符是数字 1，所以 temp = "9 3 1"；后面是“）”，所以我们要把 stack 中的栈顶符号出栈，直到“（”出栈为止。因为“（”上面只有一个“-”，所以输出“-”，temp = “9 3 1 -”,stack = "+"；
- 第八个字符是“X”，此时栈顶符号为“+”，优先级比“X”低，所以“X”进栈，stack = “+ *”；
- 第九个字符是数字 3，所以 temp = “9 3 1 - 3"；
- 第十个字符是“+”，此时栈顶元素为“ * ”比“+”的优先级高，所以栈顶元素出栈并输出（没有比“+”更低的优先级，所以全部出栈）然后再将“+”入栈，temp = "9 3 1 - 3 * +"，stack = "+"；
- 第十一个字符是数字10，temp = "9 3 1 - 3 * + 10",后面是符号“÷”，所以“/"入栈，stack = "+ /";
- 最后一个字符是数字2，temp = "9 3 1 - 3 * + 10 2";
- 因为已经到了最后，所以将栈中符号全部出栈并输出，temp = "9 3 1 - 3 * + 10 2 / +"; stack 为空栈，结束。
所以 9 + ( 3 - 1 ) X 3 + 10 ÷ 2 转换为后缀表达式结果为 temp 的值"9 3 1 - 3 * + 10 2 / +"。
后缀表达式计算方法
规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈进行运算；再将运算结果进栈，直到遍历结束。
求后缀表达式 "9 3 1 - 3 * + 10 2 / +"的值：
用 stack 表示存储符号的栈。
- 因为后缀表达式的前 3 个字符都是数字，所以“9 3 1”依次进栈，stack = “9 3 1”；
- 接下来是“-”，所以将栈顶的“1”出栈作为“减数”，再将“3”出栈作为“被减数”，计算 3 - 1 = 2，再将 2 进栈，stack = “9 2”；
- 接着是数字 3 进栈，stack = “9 2 3”；
- 再接着是“*”，所以将栈顶的“3”出栈，再将“2”出栈，2 * 3 = 6；将 6 进栈，stack = “9 6”；
- 后面是“+”，将栈中6 和 9 出栈并相加得到 15，将15进栈，stack = “15”;
- 接着是数字10 和 2，将它们依次进栈，stack = “15 10 2”；
- 后面是“/”，将 2 出栈作为除数，再将 10 出栈作为被除数，10 / 2 = 5，将 5 进栈，stack = "15 5";
- 最后一个符号是“+”，所以将 15 与 5 相加得到 20，再将 20 入栈，stack = “20”；
- 此时，已经没有符号了，所以将栈中的 20 出栈，运算结果为 20。
总结
- 将中缀表达式转为后缀表达式，栈用来存储运算符号。
- 计算后缀表达式的结果，栈用来存储运算的数字。
下一章：程序猿必修课之数据结构（八）队列
