首页 > 其他分享 >03-堆栈

03-堆栈

时间:2022-09-20 20:46:20浏览次数:54  
标签:03 中缀 栈顶 运算符 堆栈 Stack 表达式

03-堆栈

什么是堆栈

堆栈的抽象数据类型
数据对象集:一个有0个或多个元素的有穷线性表
操作集:长度为MaxSize的堆栈S ∈ Stack, 堆栈元素item ∈ ElementType

  1. Stack CreateStack(int MaxSize): 生成空堆栈,其最大的长度为MaxSize
  2. int isFull(Stack S,int MaxSize): 判断堆栈S是否为空
  3. void Push(Stack S, ElementType item): 将元素item压入堆栈
  4. int isEmpty(Stack S): 判断堆栈S是否为空
  5. ElementType Pop(Stack S): 删除并返回栈顶元素

中缀表达式和后缀表达式

中缀表达式即咱们常见的运算表达式形式例如2+9/3-5a*(b+c)/d
后缀表达式即计算机执行时的顺序例如293/+5-abc+*d/
后缀表达式在计算机中的运算,遇到数字把压入堆栈,遇到符号取出堆栈中的最近两个数值进行运算,运算结果存入堆栈

中缀表达式如何转化为后缀表达式

从头到尾读取中缀表达式的每个对象,对不同对象,按不同情况处理

  1. 运算符:直接输出
  2. 左括号:压入堆栈
  3. 右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出)
  4. 运算符:
    1. 若优先级大于栈顶运算符时,则把它压栈
    2. 若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈
  5. 若各对象处理完毕,则把堆栈中存留的运算符一并输出

标签:03,中缀,栈顶,运算符,堆栈,Stack,表达式
From: https://www.cnblogs.com/Oh-mydream/p/16712454.html

相关文章