栈的应用

#括号匹配

  • 简单，通俗的话来讲的话
  • 就是
  • 遇到左括号就入栈，遇到右括号就出栈并比较是否与之匹配
  • 匹配就出栈成功，继续扫描
  • 不匹配就出栈失败，返回erro
  • 重头戏就是应用在中缀表达式转化成后缀表达式里

    • #表达式转化

  • 本质上来说的话，计算机中计算表达式的方法是把中缀表达式放入树这个结构中，得到对应的表达式树
  • 然后利用后序遍历得到的结果便是一个后缀表达式
  • 利用后缀表达式，计算机就可以计算出表达式结果
  • #手算
  • 例如(10+9\*2)\*3+(4\*(8+20\*2))/4
  • 从左往右扫
  • 10
  • 然后+号
  • 9
  • 然后\*号
  • 2
  • 得到10 9 2 \* +
  • 然后\*号
  • 得到 10 9 2 \* + 3 \*
  • 然后+号，以下开始算加号右边
  • 4
  • 然后 \*号
  • 8
  • 然后+号
  • 20
  • 然后\*号
  • 得到4 8 20 2 \* + \*
  • 然后/号
  • 得到 4 8 20 2 \* + \* 4 /
  • 最后得到 10 9 2 \* + 3 \* 4 8 20 2 \* + \* 4 / +
  • 其实就是左右操作数的问题，额，我相信，你看一遍一定能懂

    • #操作数求值

  • 得到后缀表达式后
  • 就开始将表达式逐个入栈
  • 10 入栈，9 入栈，2 入栈
  • 遇见计算符号，弹出两个数字进行计算
  • 得到18，结果压入栈
  • 遇见+，弹出 10和18计算得28入栈
  • 3 入栈
  • 遇见\*，弹出3和28，计算得84 入栈
  • 4 入栈，8入栈，20 入栈，2 入栈
  • 遇见\*，弹出20和2，计算得40 入栈
  • 遇见+，弹出40和8，计算得48 入栈
  • 遇见\*，弹出48和4，计算得192入栈
  • 4 入栈
  • 遇见/，弹出192和4，计算得48，入栈
  • 遇见+，弹出48和84，得132入栈
  • 最后弹出132，计算结果得出。

    • #栈在递归中的应用

  • 一般来说，程序执行有个叫函数栈的玩意
  • 每执行一次函数都会压入该函数入栈
  • 直到该函数执行完才会弹出
  • 递归，则是在函数体中重复调用自己
  • 所以，每次执行自己都会调用自己这个函数
  • 导致函数栈不断压入自己这个函数
  • 故而需要递归边界让达成某个事件后结束最后一个函数的递归调用
  • 否则会导致栈溢出的错误
  • #递归的属性
  • 递归深度过大，容易导致栈溢出
  • 效率低下的原因是存在大量的重复计算