检查表达式中的平衡括号-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
猜你喜欢