教育部—微软精品课程 void conversion (& InitStack(S) scanf(%od,N) while(ni Push(s,n%0 8) N=N/8; while( Stack Empty(S)& Pop(s, e); printf(%od,e) }∥ conversion 扇京航航天大学数握常题组版
void conversion () { InitStack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } } // conversion
教育部—微软精品课程建设项目 例二、括号匹配的检验 假设在表达式中 ([]())或[([][])] 等为正确的格式, [(])或([())或(()]) 均为不正确的格式。 则检验括号是否匹配的方法可用 胡待的急迫程度”这个概念来描述 南京航空航天大学数据结构课题组版权所有
例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述
教育部—微软精品课程建设项目 例如:考虑下列括号序列 12345678 分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待” 来的是“不速之客”; 直到结束,也没有到来所“期待 的括弧。 南京航空航天大学数据结构课题组版权所有
分析可能出现的不匹配的情况: • 到来的右括弧并非是所“期待” 的； 例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 • 到来的是“不速之客”； • 直到结束，也没有到来所“期待” 的括弧
教育 算法的设计思想 1)凡出现左括弧,则进栈 2)凡出现右括孤,首先检查栈是否空 若栈空,则表明该“右括弧”多余, 否则和栈顶元素比较, 若相匹配,则“左括弧出栈 否则表明不匹配。 3)表达式检验结束时 若栈空,则表明表达式中匹配正确 否则表明“左括弧”有余。 南京航空航天大学数据结构课题组版权所有
算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余
Status matching(string& exp)( int state= 1 while(i<=length(exp)&& state) switch of exp[]( case左括弧{Push(S,expi);i++; break} case if(NOT Stack Empty(s)&&Get Top(S)=( {Pop(S,e),i++;} else istate=0; 1 break if(StackEmpty(s)&&state)return OK 京航空航天大学数据结构课题组版词
Status matching(string& exp) { int state = 1; while (i<=Length(exp) && state) { switch of exp[i] { case 左括弧:{Push(S,exp[i]); i++; break;} case”)”: { if(NOT StackEmpty(S)&&GetTop(S)=“(“ {Pop(S,e); i++;} else {state = 0;} break; } … … } if (StackEmpty(S)&&state) return OK; …