大话数据结构042栈的应用递归

一、经典递归-斐波那契数列

二、递归

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数&＃xff0c;称做递归函数。

三、四则运算表达式求值

 1. 处理括号的一种方法

2. 后缀&＃xff08;逆波兰RPN&＃xff09;表示法定义

所有的符号都是在运算数字的后面出现

3. 后缀表达式计算过程

4. 中缀表达式转后缀表达式

规则&＃xff1a;

「1」从左到右遍历中缀表达式的每个数字和符号&＃xff0c;若是数字就输出&＃xff0c;即成为后缀表达式的一部分。

「2」若是符号&＃xff0c;则判断其与栈顶符号的优先级&＃xff0c;是右括号或优先级低于栈顶符号&＃xff08;乘除优先加减&＃xff09;则栈顶元素依次出栈并输出。并将当前符号进栈&＃xff0c;一直到最后输出后缀表达式为止。

具体步骤如下&＃xff1a;