检查表达式中括号是否平衡 - O(1) 空间 - O(N^2) 时间复杂度（C++）

概念

给定一个包含字符 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’ 的字符串 str，任务是判断括号是否平衡。

括号被认为是平衡的，如果：

  • 打开的括号必须由相同类型的括号关闭。

  • 并且打开的括号必须按照正确的顺序关闭。

输入 − str = “(()){}”

输出 − 是

输入 − str = “))(([][”

输出 − 否

方法

  • 分配两个变量 a 和 b 来跟踪要比较的两个括号。

  • 需要维护一个计数器，当遇到开括号时其值递增，当遇到闭括号时其值递减。

  • 当遇到开括号时，将 b = a，a = a + 1 以及 count=count+1。

  • 当遇到闭括号时，递减 count 并比较 i 和 j 处的括号，

    • 如果发现 a 和 b 处的括号匹配，则将字符串中 a 和 b 位置的字符替换为 ‘#’。a 自增，b 自减，直到遇到非 ‘#’ 值或 b ≥ 0。

    • 如果发现 a 和 b 处的括号不匹配，则返回 false。

  • 如果 count != 0，则返回 false。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

 实时演示

// 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;
   }
}
// Driver code
int main(){
   string str1 = "[[]][]()";
   if (isValid(str1))
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

输出

Yes

更新于: 2020年7月23日

311 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告