首页 > 代码库 > 括号匹配（字符串）

括号匹配（字符串）

2024-07-09 23:45:30   224人阅读

问题描述：
检查字符串表达式中的括号是否匹配；
左括号数目同有括号数目不相等即为不匹配；
去除多余的左括号或者右括号，优先保留先出现的括号；
匹配后去除无效的括号：如：((表达式)) 应为(表达式)；
只考虑小括号，不考虑先出现右括号的情况；
要求实现函数： (字符串最长长度为60；表达式正确性不需要考虑)
void Bracket(char* src, char* dst);
如果匹配则通过dst 输出原串；
如果不匹配则根据要求去处多于括号后通过dst 输出匹配后的串
示例
输入：12+(345*25-34) 输出：12+(345*25-34)
输入：12+(345*(25-34) 输出： 12+(345*25-34)
输入：(12+345)*25)-34 输出： (12+345)*25-34
输入：(543+(256-43)*203))+24
输出：(543+(256-43)*203)+24
输入：((1+2)*((34-2))+((2*8-1)
输出：((1+2)*(34-2)+2*8-1)

#include<iostream>#include<vector>#include<string>#include<algorithm>using namespace std;void leftRight(string s,vector<int> &leftBracket,vector<int> &rightBracket){    unsigned len = s.size();    leftBracket.clear();    rightBracket.clear();    for(unsigned i=0;i<len;i++)    {        if(s[i]==‘(‘)            leftBracket.push_back(i);        else if(s[i]==‘)‘)            rightBracket.push_back(i);    }}void Bracket(char* src, char* dst){      vector<int> leftBracket,rightBracket;//存放左右括号的下标   unsigned len = strlen(src);   string s(src,src+len);   leftRight(s,leftBracket,rightBracket);   unsigned len1 = leftBracket.size(),len2=rightBracket.size();      while(len1>len2)   {     s.erase(leftBracket[len1-1],1);     leftRight(s,leftBracket,rightBracket);     len1--;   }   while(len1<len2)   {     s.erase(rightBracket[len2-1],1);     leftRight(s,leftBracket,rightBracket);     len2--;   }      unsigned k1 ,k2 ;   vector<int> era;//要删除的元素的下标   for(k1 = len1-1;k1>0;k1--)//删除不需要的括号对   {               if(leftBracket[k1]-leftBracket[k1-1]!=1)       {           for(k2 = 0;k2<len2;k2++)           {             if(leftBracket[k1]<rightBracket[k2])             {                                  rightBracket[k2]=0;                 break;             }           }//end for       }//end if       else       {         for(k2 = 0;k2<len2-1;k2++)           {             if(leftBracket[k1]<rightBracket[k2] && leftBracket[k1-1]<rightBracket[k2+1] && rightBracket[k2+1]-rightBracket[k2]==1)             {                 era.push_back(leftBracket[k1]);                 era.push_back(rightBracket[k2]);                 rightBracket[k2]=0;                                  break;             }           }//end for              }//end else   } //end forif(era.size()!=0)//有大下标到小下标依次删除多余的括弧{    sort(era.begin(),era.end());    for(int i=era.size()-1;i>=0;i--)    {        s.erase(era[i],1);    }}strncpy(dst,&s[0],s.size());dst[s.size()]=‘\0‘;}void main(){        char* src = http://www.mamicode.com/"((1+2)*((34-2))+((2*8-1)";     char* dst = new char[100];    Bracket(src, dst);        puts(dst);}

注意事项：

如果用string的erase函数，一用此函数，string的大小和以前的下标与字符串对应关系就改变了，这一点编程时要特别注意！


联系
我们