# 有效的括號字符串

“（）”

“ *）”

“（*））”

## 有效括號字符串的幼稚方法

*'可以採用三個可能的值，嘗試所有這些值，如果有任何有效的平衡字符串，則當前字符串有效。

1. 遍歷給定的字符串。
2. 遞歸替換'*與“('，')'和空字符串。
3. 如果任何組合是平衡字符串，則給定的字符串是平衡的。

### 有效括號字符串的JAVA代碼

```public class ValidParanthesisString {
private static boolean ans;

private static boolean isValid(String str) {
// Initialise ans as false
ans = false;
// Recur and try all the combinations possible for the string
recurStr(new StringBuilder(str), 0);
return ans;
}

private static void recurStr(StringBuilder str, int i) {
if (i == str.length()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str.charAt(i) == '*') {
// Replace * with (
str.setCharAt(i, '(');
recurStr(str, i + 1);
// Replace * with )
str.setCharAt(i, ')');
recurStr(str, i + 1);
// replace * with empty string
str.setCharAt(i, ' ');
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}

// Function to check if given string is balanced or not
private static boolean checkValidity(StringBuilder str) {
int bal = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
bal++;
} else if (str.charAt(i) == ')') {
bal--;
}
if (bal < 0) {
break;
}
}

return bal == 0;
}

public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));

// Example 2
str = "(*)";
System.out.println(isValid(str));

// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}```

### 有效括號字符串的C ++代碼

```#include <iostream>
using namespace std;

bool ans;

// Function to check if given string is balanced or not
bool checkValidity(string str) {
int bal = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
bal++;
} else if (str[i] == ')') {
bal--;
}
if (bal < 0)
break;
}
return (bal == 0);
}

void recurStr(string str, int i) {
if (i == str.size()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str[i] == '*') {
// Replace * with (
str[i] = '(';
recurStr(str, i + 1);
// Replace * with )
str[i] = ')';
recurStr(str, i + 1);
// replace * with empty string
str[i] = ' ';
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}

bool isValid(string str) {
// Initialise ans as false
ans = false;

// Recur and try all the combinations possible for the string
recurStr(str, 0);

return ans;
}

int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}```
```true
true
true```

## 有效括號字符串的最佳方法

1. 開括號將最小值和最大值加1。
2. 尖括號將最小值和最大值減小1，最小值不能為負。
3. 星號（*）將最小值減少1，並將最大值增加1。
4. 如果最大值在任何時候變為負值，則字符串不平衡。

### 例

• '（'：將最小值和最大值增加1 {索引0}（最小值= 1，最大值= 1）
• '*'：將最小值減小1，將最大值減小1 {索引1、2和3}（最小值= 0，最大值= 4）
• '）：將最小值和最大值減小1 {索引4}（最小值= 0且最大值= 3）

### JAVA代碼

```public class ValidParanthesisString {
private static boolean isValid(String str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str.charAt(i) == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = Math.max(minimum, 0);
}

// If minimum is 0, then string is balanced
return minimum == 0;
}

public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));

// Example 2
str = "(*)";
System.out.println(isValid(str));

// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}```

### C ++代碼

```#include <iostream>
using namespace std;

bool isValid(string str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str[i] == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = std::max(minimum, 0);
}
// If minimum is 0, then string is balanced
return (minimum == 0);
}

int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}```
```true
true
true```