堆栈的应用-括号匹配.doc

堆栈的应用： 应用例子1编译器中的应用 堆栈的一个应用是在程序中匹配分隔符。这是一个重要实例，因为分隔符的匹配是任意编译器的一部分：如果分隔符不匹配，程序就不可能正确。程序中通常有如下分隔符：圆括号“（”和“）”，方括号“”和“”，大括号“”和“”以及注释分隔符“/*”和“*/”。分隔符匹配的例子：a = b + ( c - d ) * ( e f ) ;g 10 = h i9 + ( j + k ) * l ;while ( m ( n8 + o ) p = 7 ; /* initialize p */ r = 6 ;分隔符不匹配的例子：a = b + ( c - d) * ( e f ) ) ;g10 = h i9 + ( j + k ) * l ;while ( m ( n8 + o ) p = 7 ; /* initialize p */ r = 6 ;从file 中读入字符ch1 .Nch1 “n”Y不是分隔符ch1 “n” 文件没结束“(” 或“”或“” “/” “*” “)” 或“”或“”看下一个字符是否是“/”，如果是，判断字符“*”“/”与栈顶及次栈顶字符是否匹配，如果不匹配，出错；如果匹配，将栈顶及次栈顶字符弹出看与栈顶字符是否匹配，如果不匹配，出错；如果匹配，将栈顶字符弹出。看下一个字符是否是“*”，如果是，压栈push(ch1)从file 中读入下一个字符ch1 .栈是否为空？ 为空，结束 不空，出错。算法 delimitermatching(file. flag)CREATS（S）.从file中读入字符ch1. /设“n”表示文件结束while ch1 “n” do (if (ch1=“(”) OR (ch1=“” ) OR (ch1=“” ) /第一种情况then push(ch1).else if ch1 = “/” /第二种情况 注意顺序then（ 读入下一个字符ch2 . if ch2=“*” then ( push(ch1). push(ch2). ) ） else if (ch1=“)”) OR (ch1=“”) OR (ch1 = “”) then ( /第三种情况 ch2 peek(). if NOT ( (ch1=“)” AND ch2=“(”) OR (ch1=“” AND ch2=“”) OR (ch1=“” AND ch2=“”) ) then ( flag fail. return .)/匹配失败 else pop(). /匹配成功 )else if ch1=“*” /第四种情况 then ( 读入下一个字符ch2 . if ch2=“/” then (ch3peek(). ch4stop-1./取次栈顶元素 if NOT ( ch1=ch3 AND ch2 = ch4 )then ( flag fail. return .) else ( pop(). pop(). ) /else 忽略其他字符从file 中读入下一个字符