大话数据结构_栈_应用

递归—斐波那契数列

• 我们把一个直接调用自己或通过一系列的调用语句间接低调用自己的函数，称为递归函数
• 每个递归定义至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值然后退出

如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子，假设所有兔子都不死，一年后可以繁殖多少对兔子？

经分析得到：
F(n) = \begin{cases} 0&,n=0\\1&,n=1\\F(n-1)+F(n-2)&,n>1 \end{cases}

四则运算表达式求值

后缀表示法定义（逆波兰式）
示例(标准四则运算表达式)：
9 + (3 - 1)*3+10\div2
结果（逆波兰式）：
9,3,1,-,3,*,+,10,2,\div,+
解析逆波兰式计算结果的过程：

• 9入栈，3入栈，1入栈
• 遇到了减号，1出栈作为减数，3出栈作为被减数，运算3-1，结果为2，2入栈
• 3入栈
• 遇到乘号，3出栈，2出栈，相乘结果为6，6入栈
• 又遇到加号，6出栈，9出栈，相加结果为15，15入栈
• 10入栈，2入栈
• 遇到除号，2出栈作为除数，10出栈作为被除数，得到结果为5，5入栈
• 此时栈里元素为：15，5
• 遇到最后的加号，5出栈，15出栈，相加结果为20，20入栈
• 20出栈

中缀表达式（即标准四则运算表达式）转后缀表达式

9 + (3 - 1)*3+10\div2

• 初始化一个空栈，用于对符号进行栈使用
• 遇到9，输出9，遇到加号，加号进栈 ：9
• 遇到左半括号，尚未匹配，左半括号进栈
• 遇到3，输出3遇到减号,减号进栈 ：9，3
• 遇到1，输出1，遇到右半括号，匹配了先前进栈的左半括号，栈顶依次出栈并输出，直到左半括号栈为止 ：9，3，1，-
• 遇到乘号，此时栈顶符号为加号，加号优先级低于乘号，不输出，乘号进栈
• 遇到3，输出3 ：9，3，1，-，3
• 遇到加号，加号优先级低于栈顶的乘号，所有栈中元素出栈并输出 ：9，3，1，-，3，*，+
• 然后将刚才那个加号（新遇到并和乘号比较优先级的加号）入栈
• 遇到10，输出10 ：9，3，1，-，3，*，+，10
• 遇到除号，除号入栈，遇到2，输出2 ：9，3，1，-，3，*，+，10，2
• 因为公式的字符已经全部读完，所以栈中元素出栈并输出 ：9，3，1，-，3，*，+，10，2，/，+