记得数据结构中有使用栈进行括号匹配的算法,但是忘记了.
昨天在做作业的时候自己设计了一个算法,测试结果是正确的.
基本思想是:
逐字扫描公式字符;并用一个list存贮已经匹配了的"("的索引
遇到")"(其索引为right0)时向前找公式开始到这个")"之间的子公式的最后一个"("的索引index,
若索引index在list中,则right--,如此循环,知道找到一个"(".
只要公式中"("和")"的数量一样多,最终都可以找到匹配的括号.
代码如下:(java实现)
public void bracketMatch(int right) //匹配括号,并找到相应的子公式,right是")"在公式中的索引
{
String tmpstr;
int left;
int tmp=right;
while(true)
{
if(tmp==0)tmp++;
tmpstr=str.substring(0,tmp); //str是公式字符串
left=tmpstr.lastIndexOf('(');
if(!bracketIndex.contains(new Integer(left)))
{
bracketIndex.add(new Integer(left)); //bracketindex是保存"("索引的List
break;
}
else
tmp--;
}
tmpstr=str.substring(left,right+1);//取得括号中的子公式
}
希望大家给出知道意见,以便进一步改进......