堆栈的应用-括号匹配

《堆栈的应用-括号匹配》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、堆栈的应用：应用例子1——编译器中的应用堆栈的一个应用是在程序中匹配分隔符。这是一个重要实例，因为分隔符的匹配是任意编译器的一部分：如果分隔符不匹配，程序就不可能正确。程序中通常有如下分隔符：圆括号“（”和“）”，方括号“[”和“]”，大括号“{”和“}”以及注释分隔符“/*”和“*/”。分隔符匹配的例子：a=b+(c-d)*(e–f);g[10]=h[i[9]]+(j+k)*l;while(m<(n[8]+o)){p=7;/*initializep*/r=6;}分隔符不匹配的例子：a=b+(c-d)*(e–f));g[10]=h[i[9

2、]+(j+k)*l;while(m<(n[8]+o]){p=7;/*initializep*/r=6;}从file中读入字符ch1.Nch1¹“”Y不是分隔符ch1¹“”文件没结束“(”或“[”或“{”“/”“*”“)”或“]”或“}”看下一个字符是否是“/”，如果是，判断字符“*”“/”与栈顶及次栈顶字符是否匹配，如果不匹配，出错；如果匹配，将栈顶及次栈顶字符弹出看与栈顶字符是否匹配，如果不匹配，出错；如果匹配，将栈顶字符弹出。看下一个字符是否是“*”，如果是，压栈push(ch1)从file中读入下一个字符ch1.栈是否为空？

3、为空，结束不空，出错。算法delimitermatching(file.flag)CREATS（S）.从file中读入字符ch1.//设“”表示文件结束whilech1¹“”do(if(ch1=“(”)OR(ch1=“[”)OR(ch1=“{”)//第一种情况thenpush(ch1).elseifch1=“/”//第二种情况注意顺序then（读入下一个字符ch2.ifch2=“*”then(push(ch1).push(ch2).)）elseif(ch1=“)”)OR(ch1=“]”)OR(ch1=“}”)then(//第三种情

4、况ch2¬peek().ifNOT((ch1=“)”ANDch2=“(”)OR(ch1=“]”ANDch2=“[”)OR(ch1=“}”ANDch2=“{”))then(flag¬fail.return.)//匹配失败elsepop().//匹配成功)elseifch1=“*”//第四种情况then(读入下一个字符ch2.ifch2=“/”then(ch3¬peek().ch4¬s[top-1].//取次栈顶元素ifNOT(ch1=ch3ANDch2=ch4)then(flag¬fail.return.)else(pop().pop().

5、))//else忽略其他字符从file中读入下一个字符ch1.)endwhileifNOTstackisempty()then(flag¬fail.return.)▐