某司面试题 关于括号匹配有关问题，求指导

某司面试题 关于括号匹配问题，求指导

[解决办法]
的确是考察栈的使用，遇到左括号就压栈，遇到匹配的右括号就出栈，当遇到不匹配的括号或者最后栈内还有没有弹出的左括号那就是返回1吧
[解决办法]
我用的是STL的栈

int CheakMatch(char *str)
{
stack<char> staCheak;

while(*str != '\0')
{
switch(*str)
{
case '(':
case '[':
{
staCheak.push(*str++);
break;
}
case ')':
case ']':
{
if(!staCheak.empty())
{
char top;
top = staCheak.top();
staCheak.pop();

if((*str == ')' && top != '(') 
[解决办法]
 (*str == ']' && top != '['))
return 1;//不匹配，返回1
else
{
str++;
break;
}
}
else//没有左括号，不匹配
return 1;
}
default:
{
str++;
break;
}
}
}

if(staCheak.empty())//栈空，匹配
return 0;
else
return 1;
}

[解决办法]
最好是用栈吧 不用栈的话可能很难解决

#include <stdio.h>
#include <stdlib.h>

#define  MAX_LEN   256

int  main(void)
{
    char*  str = (char*)malloc(MAX_LEN);
char*  brackets = (char*)malloc(MAX_LEN);

printf("input a string: ");

fgets(str, MAX_LEN, stdin);

str[strlen(str) - 1] = '\0';

int i;
int numbers = 0; 
char now;

for (i = 0; i < MAX_LEN; ++i)
{
    if (str[i] == '(')
{
    brackets[numbers++] = '(';
}
else if (str[i] == '[')
{
    brackets[numbers++] = '[';
}
else if (str[i] == ')')
{
    if (numbers >= 1 && brackets[numbers - 1] == '(')   /*之所以测试numbers>=1 是防止因为右括号多余左括号而引起越界*/
    {
--numbers;
            }
            else
            {
                break;
            }
}
else if (str[i] == ']')
{
    if (numbers >= 1 && brackets[numbers - 1] == '[')
    {
--numbers;
            }
            else
            {
                break;
            }
}
}

brackets[numbers] = '\0';

if (i < strlen(str) 
[解决办法]
 strlen(brackets) > 0)
{
        printf("false\n");
    }
    else
    {
        printf("true\n");
    }
    
    system("pause");
return 0;
}

我写的一个简单的程序
------解决方案--------------------

//这是一份非栈式的解决方案，但是我没写完整；所以应该不是很好阅读，各位小伙伴们慎看哈~~~
int fun (char** srcString )
{
//Emp: srcString = "his name is Jack(a well known person in [Pirates of the Caribbean]) "

int length = strlen(srcString);
char* pVecNaxc = new char[length];
memset(pVecNaxc, 0, length);


pVecNaxc[0] = checkType(srcString[0]);    //这个函数自己猜去吧，哈哈哈~~~
for (int i = 1; i < length; i++)
{
   int val = checkType(srcString[i]);

   pVecNaxc[i] = srcString[i-1] + val;

   if (val < 0) {
      if (pVecNaxc[i] != pVecNaxc[i-2])  //此处写的不严谨，但是若你看懂了这个解决方案，相信你就能完善了
return 1;
   }
}

if ((pVecNaxc[length-1] != 0){
   return 1;
}

return 0;
}
[解决办法]

引用:

我用的是STL的栈

int CheakMatch(char *str)
{
stack<char> staCheak;

while(*str != '\0')
{
switch(*str)
{
case '(':
case '[':
{
staCheak.push(*str++);
break;
}
case ')':
case ']':
{
if(!staCheak.empty())
{
char top;
top = staCheak.top();
staCheak.pop();

if((*str == ')' && top != '(') 
[解决办法]
 (*str == ']' && top != '['))
return 1;//不匹配，返回1
else
{
str++;
break;
}
}
else//没有左括号，不匹配
return 1;
}
default:
{
str++;
break;
}
}
}

if(staCheak.empty())//栈空，匹配
return 0;
else
return 1;
}

我的思路基本和你一致，可惜今天才看到这个帖子，大致方法就是使用栈，循环遍历整个字符串，如果是正括号就压栈，如果是反括号就从栈中弹出第一个作比较，成对的话继续继续做比较后面的字符，不成对直接返回不匹配。

查看更多 下一篇