这题是学校OJ的一题,弄了很久都没过就一直放那,现在学了栈就顺手把它解决了,期间也是历经坎坷啊。本来感觉OK了,结果还是有毛病,最后学长给了一个测试数据改了之后就解决了。。。

括号的匹配 1000(ms) 65535(kb) 362 / 1985

题意描述: 在算术表达式中,除了加、减、乘、除等运算外,往往还有括号。包括有大括号{},中括号[],小括号(),尖括号<>等。 对于每一对括号,必须先左边括号,然后右边括号;如果有多个括号,则每种类型的左括号和右括号的个数必须相等;对于多重括号的情形,按运算规则,从外到内的括号嵌套顺序为:大括号->中括号->小括号->尖括号。例如,{[()]},{()},{{}}为一个合法的表达式,而([{}]),{([])},[{<>}]都是非法的。

输入
文件的第一行为一个整数n(1≤n≤100),接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。
输出
在输出文件中有N行,其中第I行对应第I个表达式的合法性,合法输出YES,非法输出NO。
样例输入
5
{[(<>)]}
[()]

<>()[]{} [{}] {()} 样例输出 YES YES YES NO YES
#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
int isMax(char a, char b)
{
  if (a == '{' && (b == '{' || b == '[' || b == '(' || b == '<'))
  {
    return 1;
  }
  else if (a == '[' && (b == '[' || b == '(' || b == '<'))
  {
    return 1;
  }
  else if (a == '(' && (b == '<' || b == '('))
  {
    return 1;
  }
  else if(a == '<' && b =='<')
  {
    return 1;
  }
  else if (b == '}' && (a == '}' || a == ']' || a == ')' || a == '>'))
  {
    return 1;
  }
  else if (b == ']' && (a == ']' || a == ')' || a == '>'))
  {
    return 1;
  }
  else if (b == ')' && (a == '>' || a == ')'))
  {
    return 1;
  }
  else if (b == '>' && a == '>')
  {
    return 1;
  }
  else
  {
    return 0;
  }
}
int isKh(char a,char b)
{
  if ((a == '{' || a == '[' || a == '<' || a == '(') && (b == '{' || b == '[' || b == '<' || b == '('))
    return 1;
  else if ((a == '}' || a == ']' || a == '>' || a == ')') && (b == '}' || b == ']' || b == '>' || b == ')'))
    return 1;
  else
    return 0;
}
int main()
{

  int n;
  cin >> n;

  while (n--)
  {
    string str;
    stack <char> s;
    cin >> str;

    int len = str.length();
    if (len % 2 != 0)
    {
      cout << "NO" << endl;
      continue;
    }
    int flag = 0;
    for (int i = 0; i < len-1; i++)   //判断是否有等级不合适的
    {
      if (isKh(str[i], str[i + 1]))
      {
        if (!isMax(str[i], str[i + 1]))
        {
          cout << "NO" << endl;
          flag = 1;
          break;
        }
      }
    }
    if (flag)
    {
      continue;
    }

    for (int i = 0; i < len ; i++)
    {
      if (str[i] == '}' && !s.empty())
      {
        if (s.top() == '{')
        {
          s.pop();
          continue;
        }
      }
      if (str[i] == ']' && !s.empty())
      {
        if (s.top() == '[')
        {
          s.pop();
          continue;
        }
      }
      if (str[i] == ')' && !s.empty())
      {
        if (s.top() == '(')
        {
          s.pop();
          continue;
        }
      }
      if (str[i] == '>' && !s.empty())
      {
        if (s.top() == '<')
        {
          s.pop();
          continue;
        }
      }
      s.push(str[i]);
    }
    if (!s.empty())
    {
      cout << "NO" << endl;
    }
    else
    {
      cout << "YES" << endl;
    }
  }
  system("pause");
  return 0;
}
最后修改:2022 年 04 月 01 日
如果觉得我的文章对你有用,请随意赞赏