NOI题库2.2括号匹配分析与题解ppt课件.ppt

NOI题库
2.2-括号匹配问题描述输出Sampleinput问题分析问题分析问题分析这样就写出了代码： elseif(S[i]==')')//找到")"
{
if(left[j]>=0)//有匹配的左括号，下标不为-1
{
S[left[j]]=S[i]='';//设空
j--;//找上一个左括号
}
else
S[i]='?';//未匹配
}
else
S[i]='';//其他字符设空
}
cout<<S<<endl;//输出（已修改后的S）
}

如果“(”下标从left[0]开始存储，当第一个“(”匹配完后，j=-1，就会出现下标越界！！！本算法时间复杂度O(n)