检查表达式中的平衡括号-O(1)空间-C中的O（N ^ 2）时间复杂度
概念
对于给定的包含字符串'（'，'）'，'{'，'}'，'['和']'的字符串str，任务是查找方括号是否平衡。
括号表示为平衡，如果-
我们关闭的开放式括号必须用相同类型的括号封闭。
再次，我们按照正确的顺序关闭方括号。
输入−str=“（()）{}”
输出-是
输入−str=“））（（[[][”
输出-否
方法
分配两个变量a和b来跟踪要比较的两个括号。
应该保持一个计数，其值在遇到左括号时增加，而在遇到右括号时减少。
遇到开括号时，指定b=a，a=a+1和count=count+1。
在遇到右方括号时，递减计数并比较i和j处的括号，
如果已经看到a和b的括号是匹配的，则在字符串th和b的位置用字符串“#”代替。a递增，b递减，直到遇到非“#”值或b≥0。
如果已经看到a和b的括号不匹配，则返回false。
如果count！=0，则返回false。
示例
// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
count1--;
if (j1 > -1 && s1[j1] == tocom1) {
s1[i1] = '#';
s1[j1] = '#';
while (j1 >= 0 && s1[j1] == '#')
j1--;
i1++;
return 1;
}
else
return 0;
}
bool isValid(string s1){
if (s1.length() == 0)
return true;
else {
int i1 = 0;
int count1 = 0;
int j1 = -1;
bool result1;
while (i1 < s1.length()) {
switch (s1[i1]) {
case '}':
result1 = helperFunc(count1, s1, i1, j1, '{');
if (result1 == 0) {
return false;
}
break;
case ')':
result1 = helperFunc(count1, s1, i1, j1, '(');
if (result1 == 0) {
return false;
}
break;
case ']':
result1 = helperFunc(count1, s1, i1, j1, '[');
if (result1 == 0) {
return false;
}
break;
default:
j1 = i1;
i1++;
count1++;
}
}
if (count1 != 0)
return false;
return true;
}
}
//驱动程式码
int main(){
string str1 = "[[]][]()";
if (isValid(str1))
cout << "Yes";
else
cout << "No";
return 0;
}输出结果
Yes