一：
如果通过插入“ +”和“ 1”可以从中得到格式正确的数学表达式，则将带括号的序列称为正确的。
例如，序列 "(())()"，"()"和 "(()(()))"是正确的，而")("，"(()))("和"(()" 不是。
定义重新排序操作：选择括号序列的任意连续子段（子字符串），然后以任意方式对其中的所有字符进行重新排序。当重新排序的子段的长度为t时，重新排序操作需要耗时t秒。
例如，对于“))((”，他可以选择子字符串“)(”并重新排序“)()(”（此操作将花费2秒）。
不难看出，重新排序操作不会改变左括号和右括号的数量。
现在，LD想花费最少的时间，通过任意次数（可能为零）执行重新排序操作来使括号序列变成正确的。
输入格式:
1.第一行包含一个整数n（1≤n≤1e6），表示序列的长度；
2.第二行包含一个长度为n的字符串，仅由字符‘(’和‘)’组成。
输出格式:
输出一个整数，表示使括号序列正确的最小秒数；如果不可能实现，则输出-1。
输入样例:
8
))((())(
输出样例:
6
二：
给出一串包含 ( 、 ) 、[ 和 ] 的字符串，字符串在以下三种情况下为合法的：
1 字符串为空；
2 如果A和B都是合法的，那么AB也是合法的；
3 如果A是合法的，那么(A)和[A]也是合法的。
试判断输入的字符串是否合法。
输入格式:
输入包括一串由若干个 ( 、 ) 、 [ 或 ] 组成的字符串，字符串长度不超过100。
输出格式:
如果该字符串合法，输出“Yes”；否则输出“No”。
输入样例:
([])
输出样例:
Yes
第一个问题
#include <stdio.h>
#include <string.h>
int main()
{
int n = 0;
int result = 1;
char s[100];
scanf("%s", s);
for (int i = 0; i < strlen(s); i++)
{
if (s[i] == '(') n++;
if (s[i] == ')') n--;
if (n < 0) { result = 0; break; }
}
if (n!=0) result = 0;
if (result) printf("YES"); else printf("NO");
return 0;
}
第二个问题
#include <stdio.h>
#include <string.h>
char conv(char c)
{
if (c == ')') return '(';
if (c == '}') return '{';
if (c == ']') return '[';
return 0;
}
int main()
{
char arr[100];
int n = 0;
int result = 1;
char s[100];
scanf("%s", s);
for (int i = 0; i < strlen(s); i++)
{
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
arr[n++] = s[i];
else if (s[i] == ')' || s[i] == ']' || s[i] == '}')
{
if (arr[n - 1] != conv(s[i])) { result = 0; break; }
n--;
}
}
if (n != 0) result = 0;
if (result) printf("YES"); else printf("NO");
return 0;
}
堆栈
1.
#include <bits/stdc++.h>
#define unless(a) if(!a)
using namespace std;
int main()
{
string a;
stack <char> s;
getline(cin, s);
int len = a.size();
for(int i = 0; i < len; ++i)
{
if(a[i] == '(') s.push(a[i]);
else if(a[i] == ')')
{
unless(s.empty())
s.pop();
else
{
cout << "NO\n";
return 0;
}
}
}
if(s.empty()) cout << "YES";
else cout << "NO";
return 0;
}
2.
#include <bits/stdc++.h>
#define unless(a) if(!a)
using namespace std;
int main()
{
string a;
stack <char> s;
getline(cin, s);
int len = a.size();
for(int i = 0; i < len; ++i)
{
if(a[i] == '(') s.push(a[i]);
else if(a[i] == ')')
{
unless(s.empty())
s.pop();
else
{
cout << "NO\n";
return 0;
}
}
}
unless(s.empty()) cout << "NO\n";
for(int i = 0; i < len; ++i)
{
if(a[i] == '[') s.push(a[i]);
else if(a[i] == ']')
{
unless(s.empty())
s.pop();
else
{
cout << "NO\n";
return 0;
}
}
}
if(s.empty()) cout << "YES\n";
else cout << "NO\n";
return 0;
}