对于给定的包含字符串'(',')','{','}','['和']'的字符串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