例二、括号匹配的检验 假设在表达式中 ([]())或[([][])] 等为正确的格式, [(])或([())或(()]) 均为不正确的格式。 则检验括号是否匹配的方法可用 期待的急迫程度”这个概念来描述
例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述
例如:考虑下列括号序列 12345678 分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待 塑 来的是“不速之客”; 直到结束,也没有到来所“期待 的括弧
分析可能出现的不匹配的情况: • 到来的右括弧并非是所“期待” 的； 例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 • 到来的是“不速之客”； • 直到结束，也没有到来所“期待” 的括弧
算法的设计思想: 1)凡出现左括弧,则进栈 2)凡出现右括孤,首先检查栈是否空 若栈空,则表明该“右括弧”多余, 否则和栈顶元素比较 若相匹配,则“左括弧出栈” 否则表明不匹配。 3)表达式检验结束时 若栈空,则表明表达式中匹配正确 否则表明“左括弧”有余
算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余
Status matching(string exp)i int state= 1 while(i<=length(exp)&& state)& switch of expi case左括弧:{Push(S,expi]);i++; break;} case if(NOT Stack Empty(S)&&Get Top(S=( ( Pop(s,e);11++ else istate=0; 1 break if(StackEmpty(s)&i&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); ii++;} else {state = 0;} break; } … … } if (StackEmpty(S)&&state) return OK; …
例三、行编辑程序问题 如何实现? “每接受一个字符即存入存储器 并不恰当
例三、行编辑程序问题 如何实现？ “每接受一个字符即存入存储器” ? 并不恰当！