資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查表示式中括號是否平衡 - 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。
示例
// 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 次瀏覽
廣告