Skip to content

栈和队列#

目录#

1. 栈#

1.1. 栈在表达式求值中的应用#

1.1.1. 通过后缀表达式求值#

顺序扫描表达式的每一项，然后根据它的类型做如下相应操作

  1. 若该项是操作数，则将其压入栈中
  2. 若该项是操作符\<op>，则连续从栈中退出两个操作数Y和X，形成运算指令\<op>Y，并将结果重新压入栈中

输入 ，且时，输出为 。

1.1.2. 中缀表达式转后缀表达式#

从左到右扫描中缀表达式

  1. 遇到数字时，加入后缀表达式
  2. 遇到 时，入栈
  3. 遇到 时，把栈中 中之后的表达式依次加入后缀表达式（注意出栈顺序）
  4. 遇到其他运算符，且其优先级高于除 以外的栈顶运算符时，直接入栈
  5. 优先级低于或等于除 以外的栈顶运算符时，从栈顶开始，依次弹出比当前处理的运算符优先级别高或级别相等的运算符，遇到左括号或优先级别低的则停止，最后将操作符入栈
  6. 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式

输入中缀表达式 时，输出为 。

Back to top