3.2栈的应用举例-数制转换 3.2栈的应用举例-行编辑程序 行铺舞程序(P49) ■数制转换 。处理规则：造#通一格：漫@退一行 。算法（算法3.1P48) 算法题想：引入校，保存终增输入的一行字符（理行处理）： 出一次 void conversion(int N,int d) 透©逼一行清法 InitStack(S); while(N){Push(S,N%/od);N=N/d; 化5 while(!StackEmpty(S)){ 3)ch!=EOF Pop(S,e); 3.1)ch!=EOF &ch!='\n' 3.1.1)ch为#，Pop5,c.轴3.1.4) printf(e); 3.1.2)dh为@'， C1ear5ac(S,转3.1.4) 3.1.3)dh为其恤：Push(s,h),被3.1.4) 3.1.4)再读入享符h,雕读3.1) 3。实小，) 3.2)处理完 13/50 囵 14/50 回图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ,表达式求值(P52) ,问题描述 。表达式的表示 ·只包含+，*，/四个双目运算符，且算符本身 不具有二义性： ,中缀表达式(a+b)*c-d*(e-a) 。三个算术四则运算的规则 ,前级表达式*+abc*d-ea (波兰式) 先乘雕，后加减 ,后缀表达式ab士c*deae*。 (逆波兰式) ·从左算到右 。先括号内，后括号外 →算符间的优先关系（算符的优先级和结合性）（表3.1） 分支站点是算特 。#:表达式的开始符和结束符 ·只有(==)，'#==#， 叶子结点是操作数 ,假设输入的是一个合法的表达式。 15/50 回 16/50 图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ·算法思短 ·输入：前缀表达式串（被兰式） 输入：中氧表达式率 输出：表达式值 输出：表达式值 ,入OPTR和OPWD两个线 例：-*+abc*d-ea 钓始OPTR有一元膏”，OPND为空 ,通到算蒋时，由于远算对象还来读到，放前存 入一半将 um(GetTop(OPND)) 是算特，Push(OPND,C) 爱老整清音茶法入的竹逃系对 (OPTR),比款率c的优壳关事 管存的算将个最不国定，需要引入款播结构保存 ·针对上例：在进行算一个运算前，需智存， Pop(OPTR,x) ·敢据结构的操作塘点：后进先出→机 t>cr Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); 。管存的运算对象个数不国定，需要引入最端结构保存 x=Operate(a,theta,b); 。针对上例：在迹行第一个+运算前，馨智存a,b,c Push(OPND,x); 。敷霜辅构的操作将点：后进光出→投 。整能害入亭特处夏。 17/50 图 ·不衡共比模料特种儿点来蜡合出，只要幕林的选界对白 整齐全，即可计算！18/503 13/50 3.2 栈的应用举例-数制转换 „ 数制转换 „ 算法(算法3.1 P48) void conversion(int N, int d){ InitStack(S); while(N) { Push(S, N%d); N=N/d; } while(!StackEmpty(S)) { Pop(S, e); printf(e); } } 14/50 3.2 栈的应用举例-行编辑程序 „ 行编辑程序(P49) „ 处理规则：遇‘#’退一格；遇‘@’退一行 „ 算法思想：引入栈，保存终端输入的一行字符（逐行处理）； 遇‘#’退一格——出栈一次 遇‘@’退一行——清栈 „ 步骤： 1）初始化栈S 2）读入字符ch 3）ch!=EOF 3.1) ch!=EOF && ch!=’\n’ 3.1.1）ch为‘#’：Pop(S, c), 转3.1.4) 3.1.2）ch为‘@’： ClearStack (S) , 转3.1.4) 3.1.3）ch为其他： Push (S, ch) , 转3.1.4) 3.1.4）再读入字符ch，继续3.1) 3.2) 处理完一行，清空栈 3.3) 如ch!=EOF，读入字符ch，继续3) 15/50 3.2 栈的应用举例-表达式求值 „ 表达式求值(P52) „ 表达式的表示 „ 中缀表达式 (a+b)*c-d*(e-a) „ 前缀表达式 -*+abc*d-ea (波兰式) „ 后缀表达式 ab+c*dea-*- (逆波兰式) - * * + a b c d - e a 分支结点是算符 叶子结点是操作数 16/50 3.2 栈的应用举例-表达式求值 „ 问题描述 „ 只包含+, -, *, / 四个双目运算符，且算符本身 不具有二义性； „ 三个算术四则运算的规则 „ 先乘除,后加减 „ 从左算到右 „ 先括号内,后括号外 Î算符间的优先关系（算符的优先级和结合性）(表3.1) „ #: 表达式的开始符和结束符 „ 只有 '('==')'，'#'=='#'； „ 假设输入的是一个合法的表达式。 17/50 3.2 栈的应用举例-表达式求值 „ 算法思想 输入：中缀表达式串 输出：表达式值 „ 引入OPTR和OPND两个栈 „ 初始OPTR有一元素‘#’，OPND为空 „ 读入一字符c c==‘#’：return(GetTop(OPND)) c是非运算符：Push(OPND,c) c是运算符：t=GetTop(OPTR)，比较t和c的优先关系 t<c： Push(OPTR,c) t==c： Pop(OPTR, x) t>c： Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x); „ 继续读入字符处理。 18/50 3.2 栈的应用举例-表达式求值 „ 输入：前缀表达式串(波兰式) 输出：表达式值 例： -*+abc*d-ea „ 遇到算符时，由于运算对象还未读到，故暂存 „ 遇到运算对象时，需要判断当前最近读入的算符的运算对象 是否齐全，若齐全则计算否则暂存 „ 暂存的算符个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个运算前，需暂存-,* „ 数据结构的操作特点：后进先出-Æ栈 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个+运算前，需暂存a,b,c „ 数据结构的操作特点：后进先出-Æ栈 „ 不需要比较算符的优先级和结合性，只要算符的运算对象已 经齐全，即可计算！