Stack栈（数学表达式求值）
2021-08-17 16:47:58 0 举报AI智能生成
Stack
作者其他创作
大纲/内容
栈，是限定仅在表尾进行插入或删除操作的线性表。
后进先出
表尾端有其特殊含义，称为栈顶（top）
表头端称为栈底（bottom）
不含任何元素的空表称为空栈
栈使用
boolean empty()
测试堆栈是否为空
Object peek( )
查看堆栈顶部的对象，但不从堆栈中移除它
Object pop( )
移除堆栈顶部的对象，并作为此函数的值返回该对象
Object push(Object element)
把项压入堆栈顶部
int search(Object element)
返回对象在堆栈中的位置，以 1 为基数
应用
数学表达式求值
前置知识点
数学表达式的三种形式：前缀表达式，中缀表达式，后缀表达式。
中缀表达式（Infix Expression）
就是我们平时常用的书写方式，带有括号
前缀表达式（Prefix Expression）
要求运算符出现在运算数字的前面
后缀表达式（Postfix Expression）
要求运算符出现在运算数字的后面
思路
步骤一： 中缀表达式转化为后缀表达式
遍历中缀表达式
遇到左括号（ -> 压入栈中
遇到数字 -> 追加到后缀表达式
遇到运算符
栈中无运算符 -> 压入栈中
栈中有运算符 -> 比较栈顶运算符
栈顶运算符 >= 当前运算符
当前运算符压入栈中
栈顶运算符 < 当前运算符
栈顶运算符弹出，追加到后缀表达式
当前运算符压入栈中
当前运算符压入栈中
遇到右扩符） -> 栈顶运算符弹出，追加到后缀表达式
删除栈中左扩符
删除栈中左扩符
步骤二： 后缀表达式求值
遍历表达式
遇到数字 -> 压进栈中
遇到运算符 -> 弹出2个数字，进行运算 -> 结果压进栈中
遍历结束 -> 返回栈顶元素
0 条评论
下一页
