Java求解添加最少括号数问题 括号序列由()、{}、[]组成,例如“(([{}]))()”是合法的,而“(}{)”“(}(}”和“({)}”都是不合法的。如果一个序列不合法,编写一个实验程序求添加的最少括号数,使这个序列变成合法的。例如,“(}(}”最少要添加4个括号变成合法的,即变为“(){}(){}”的具体代码
时间: 2023-06-11 08:06:08 浏览: 42
以下 Java 实现,采用栈来实现括号匹配,如果栈顶元素与当前遍历到的括号匹配,则栈顶元素出栈,否则当前括号入栈。最后,需要将栈中剩余的括号全部出栈,并计算需要添加的最少括号数。
```
import java.util.*;
public class Solution {
public static int minAddBracket(String s) {
Stack<Character> stack = new Stack<Character>();
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
count++;
} else {
char top = stack.peek();
if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {
stack.pop();
} else {
stack.push(c);
}
}
}
}
count += stack.size();
return count;
}
public static void main(String[] args) {
String s1 = "({[}])";
String s2 = "({[}]";
String s3 = "((}}";
System.out.println(minAddBracket(s1)); // output: 2
System.out.println(minAddBracket(s2)); // output: 2
System.out.println(minAddBracket(s3)); // output: 3
}
}
```