目录

1.递归
2.表达式求值

1.递归

1.1 概念

在函数调用过程中，调用自己本身。

1.2 计算 1~n 的和

解析：

一旦有确切的返回值结果，该函数就需要在栈内存中释放空间。

注：栈内存跟栈一样，满足先进后出，后进先出。

2.表达式求值

2.1

计算机只认识后缀表达式，不认识中缀表达式。

2.2 后缀表达式计算

提前准备好一个栈，如果是数值，就将其压入到栈中。当遇到运算符时，将运算符放到运算符的位置上，将栈中的数出栈，先出栈的放到op2的位置上，后出栈放到op1，然后计算即可，得到的结果再压回到栈中，后续同理。

2.3 中缀表达式转后缀表达式

（1）先在栈中放入一个优先级最低的东西（不是数字0，这里画的有问题，是\0）。

（2）如果是操作数，直接输出。

（3）如果是运算符，判断优先级，如果优先级大于栈顶元素，压入栈中。如果优先级小于等于栈顶元素，先将栈顶元素出栈并输出，然后将当前运算符压入栈中。 直至遇到 \0，将栈中剩余的所有元素全部出栈，\0不出栈。

注：当左括号在栈外时，属于最高优先级，当左括号在栈里时，属于最低优先级。

注：如果是右括号，且栈顶元素不是左括号，栈里的元素持续出栈并输出，直到栈顶为左括号，此时左括号出栈，但不输出。右括号也不会输出，然后继续扫描中缀表达式。

（4）后缀表达式中不会出现左括号和右括号。