如何建设一个公众号电影网站,免费建设在线商城的网站,wordpress写接口,上海做网站企业目录 3.3.1栈在括号匹配中的应用流程图算法代码 3.3.2栈在表达式求值中的应用1. 中缀表达式 (需要界限符)2. 后缀表达式 (逆波兰表达式)中缀表达式转后缀表达式-手算重点#xff1a;中缀表达式转后缀表达式-机算重点#xff1a;后缀表达式的计算—机算 3.前缀表达式 (波兰表达… 目录 3.3.1栈在括号匹配中的应用流程图算法代码 3.3.2栈在表达式求值中的应用1. 中缀表达式 (需要界限符)2. 后缀表达式 (逆波兰表达式)中缀表达式转后缀表达式-手算重点中缀表达式转后缀表达式-机算重点后缀表达式的计算—机算 3.前缀表达式 (波兰表达式)4.中缀表达式的计算(用栈实现)5. 知识回顾 3.3.3栈在递归中的应用调用过程 3.3.4 队列的应用 3.3.1栈在括号匹配中的应用
用栈实现括号匹配 ((())) 最后出现的左括号最先被匹配 (栈的特性—LIFO); 遇到左括号就入栈; 遇到右括号就“消耗”一个左括号 (出栈);
匹配失败情况 扫描到右括号且栈空则该右括号单身; 扫描完所有括号后栈非空则该左括号单身; 左右括号不匹配;
流程图 算法代码
#define MaxSize 10 typedef struct{char data[MaxSize];int top;
} SqStack;//初始化栈
InitStack(SqStack S)//判断栈是否为空
bool StackEmpty(SqStack S)//新元素入栈
bool Push(SqStack S, char x)//栈顶元素出栈用x返回
bool Pop(SqStack S, char x)bool bracketCheck(char str[], int length){SqStack S; //声明InitStack(S); //初始化栈for(int i0; ilength; i){if(str[i] ( || str[i] [ || str[i] {){Push(S, str[i]); //扫描到左括号入栈}else{if(StackEmpty(S)) //扫描到右括号且当前栈空return false; //匹配失败char topElem; //存储栈顶元素Pop(S, topElem); //栈顶元素出栈if(str[i] ) topElem ! ( )return false;if(str[i] ] topElem ! [ )return false;if(str[i] } topElem ! { )return false; }}StackEmpty(S); //栈空说明匹配成功
}
3.3.2栈在表达式求值中的应用
1. 中缀表达式 (需要界限符)
运算符在两个操作数中间:
① a b
② a b - c
③ a b - c*d
④ ((15 ÷ (7-(11)))×3)-(2(11))
⑤ A B × (C - D) - E ÷ F
2. 后缀表达式 (逆波兰表达式)
运算符在两个操作数后面:
① a b
② ab c - / a bc-
③ ab cd* -
④ 15 7 1 1 - ÷ 3 × 2 1 1 -
⑤ A B C D - × E F ÷ - (机算结果)A B C D - × E F ÷ - (不选择)中缀表达式转后缀表达式-手算 步骤1 确定中缀表达式中各个运算符的运算顺序 步骤2 选择下一个运算符按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数 步骤3 如果还有运算符没被处理继续步骤2
“左优先”原则: 只要左边的运算符能先计算就优先算左边的 (保证运算顺序唯一)
中缀A B - C * D / E F① ④ ② ③ ⑤
后缀A B C D * E / - F
重点中缀表达式转后缀表达式-机算
初始化一个栈用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素直到末尾。可能遇到三种情况:
遇到操作数: 直接加入后缀表达式。遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式直到弹出 ‘(’ 为止。注意: ‘(’ 不加入后缀表达式。遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后将栈中剩余运算符依次弹出并加入后缀表达式。
重点后缀表达式的计算—机算
先出栈的是“右操作数”
3.前缀表达式 (波兰表达式)
运算符在两个操作数前面:
① a b
② - ab c
③ - ab *cd
中缀表达式转前缀表达式—手算 步骤1 确定中缀表达式中各个运算符的运算顺序 步骤2 选择下一个运算符按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数 步骤3 如果还有运算符没被处理就继续执行步骤2
“右优先”原则: 只要右边的运算符能先计算就优先算右边的;
中缀A B * (C - D) - E / F⑤ ③ ② ④ ①
前缀 A - * B - C D / E F
注意: 先出栈的是“左操作数”
4.中缀表达式的计算(用栈实现)
两个算法的结合 中缀转后缀 后缀表达式的求值
初始化两个栈操作数栈 和运算符栈
若扫描到操作数压人操作数栈
若扫描到运算符或界限符则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符每当弹出一个运算符时就需要再弹出两个操作数栈的栈项元素并执行相应运算运算结果再压回操作数栈)
5. 知识回顾 3.3.3栈在递归中的应用
迷宫求解也用到栈
函数调用的特点最后被调用的函数最先执行结束(LIFO)
函数调用时需要用一个栈存储
调用返回地址下一条指令的地址实参传递的局部变量自己的
递归调用时函数调用栈称为 “递归工作栈”:
每进入一层递归就将递归调用所需信息压入栈顶 每退出一层递归就从栈顶弹出相应信息
缺点太多层递归可能回导致栈溢出空间复杂度升高也可能含有很多重复计算过程
适合用“递归”算法解决可以把原始问题转换为属性相同但规模较小的问题
调用过程 3.3.4 队列的应用
树的层次遍历、图的广度优先遍历、操作系统FCFS先来先服务
