我想测试输入字符串是否平衡。如果有匹配的左括号和右括号，括号或大括号，它将是平衡的。
example:
{} balanced
() balanced
[] balanced
If S is balanced so is (S)
If S and T are balanced so is ST
public static boolean isBalanced(String in)
{
Stack st = new Stack();
for(char chr : in.toCharArray())
{
if(chr == '{')
st.push(chr);
}
return false;
}
我在选择做什么时遇到问题。我是否应该将每个左括号或右括号、括号或大括号放在堆栈中，然后将它们弹出？如果我把它们弹出来，这对我有什么帮助？
1）对于每个开口支架：{ [ (将其推入堆栈。
2）对于每个右括号：} ] )从堆栈中弹出并检查括号类型是否匹配。如果不返回false；
即字符串中的当前符号是}，如果从堆栈中弹出是其他任何东西，{则false立即返回。
3）如果行尾和堆栈不为空，则返回false，否则true。
是的，堆栈是该任务的合适选择，或者您可以使用递归函数。如果您使用堆栈，那么想法是您将每个左括号推入堆栈，当您遇到右括号时，您检查堆栈顶部是否匹配它。如果匹配，则将其弹出，如果不匹配，则为错误。完成后，堆栈应该是空的。
import java.util.Stack;
public class Balanced {
public static boolean isBalanced(String in)
{
Stack<Character> st = new Stack<Character>();
for(char chr : in.toCharArray())
{
switch(chr) {
case '{':
case '(':
case '[':
st.push(chr);
break;
case ']':
if(st.isEmpty() || st.pop() != '[')
return false;
break;
case ')':
if(st.isEmpty() || st.pop() != '(')
return false;
break;
case '}':
if(st.isEmpty() || st.pop() != '{')
return false;
break;
}
}
return st.isEmpty();
}
public static void main(String args[]) {
if(args.length != 0) {
if(isBalanced(args[0]))
System.out.println(args[0] + " is balanced");
else
System.out.println(args[0] + " is not balanced");
}
}
}
以下是Java检测字符串是否平衡的代码示例。
http://introcs.cs.princeton.edu/java/43stack/Parentheses.java.html
这个想法是——
( [ {，将其推入堆栈。) ] }，尝试( [ }从堆栈中弹出一个匹配的左大括号。如果找不到匹配的左大括号，则字符串不平衡。好吧，粗略地说，如果它是平衡的，那意味着你的堆栈应该是空的。
为此，您需要在解析时弹出堆栈}
附加要求是检查}前面是{还是弹出的字符是{.
我编写了这段代码来解决这个问题，每个括号类型只使用一个整数（或者可能是一个字节）变量。
public boolean checkWithIntegers(String input) {
int brackets = 0;
for (char c: input.toCharArray()) {
switch (c) {
case '(':
brackets++;
break;
case ')':
if (brackets == 0)
return false;
brackets--;
break;
default:
break;
}
}
return brackets == 0;
}
public static void main(String... args) {
Borrar b = new Borrar();
System.out.println( b.checkWithIntegers("") );
System.out.println( b.checkWithIntegers("(") );
System.out.println( b.checkWithIntegers(")") );
System.out.println( b.checkWithIntegers(")(") );
System.out.println( b.checkWithIntegers("()") );
}
OBS
希望这有帮助。干杯!
import java.util.Stack;
public class SyntaxChecker {
/**
* This enum represents all types of open brackets. If we have a new type then
* just add it to this list with the corresponding closed bracket in the other
* ClosedBracketTypes enum
* @author AnishBivalkar
*
*/
private enum OpenBracketTypes {
LEFT_ROUND_BRACKET('('),
LEFT_SQUARE_BRACKET('['),
LEFT_CURLY_BRACKET('{');
char ch;
// Constructs the given bracket type
OpenBracketTypes(char ch) {
this.ch = ch;
}
// Getter for the type of bracket
public final char getBracket() {
return ch;
}
/**
* This method checks if the current character is of type OpenBrackets
* @param name
* @return True if the current character is of type OpenBrackets, false otherwise
*/
public static boolean contains(final char name) {
for (OpenBracketTypes type : OpenBracketTypes.values()) {
if (type.getBracket() == name) {
return true;
}
}
return false;
}
}
/**
* This enum represents all types of Closed brackets. If we have a new type then
* just add it to this list with the corresponding open bracket in the other
* OpenBracketTypes enum
* @author AnishBivalkar
*
*/
private enum CloseBracketTypes {
RIGHT_ROUND_BRACKET(')'),
RIGHT_SQUARE_BRACKET(']'),
RIGHT_CURLY_BRACKET('}');
char ch;
CloseBracketTypes(char ch) {
this.ch = ch;
}
private char getBracket() {
return ch;
}
/**
* This method checks if a given bracket type is a closing bracket and if it correctly
* completes the opening bracket
* @param bracket
* @param brackets
* @return
*/
public static boolean isBracketMatching(char bracket, Stack<Character> brackets) {
// If the current stack is empty and we encountered a closing bracket then this is
// an incorrect syntax
if (brackets.isEmpty()) {
return false;
} else {
if (bracket == CloseBracketTypes.RIGHT_ROUND_BRACKET.getBracket()) {
if (brackets.peek() == OpenBracketTypes.LEFT_ROUND_BRACKET.getBracket()) {
return true;
}
} else if (bracket == CloseBracketTypes.RIGHT_SQUARE_BRACKET.ch) {
if (brackets.peek() == OpenBracketTypes.LEFT_SQUARE_BRACKET.getBracket()) {
return true;
}
} else if (bracket == CloseBracketTypes.RIGHT_CURLY_BRACKET.ch) {
if (brackets.peek() == OpenBracketTypes.LEFT_CURLY_BRACKET.getBracket()) {
return true;
}
}
return false;
}
}
/**
* This method checks if the current character is of type ClosedBrackets
* @param name
* @return true if the current character is of type ClosedBrackets, false otherwise
*/
public static boolean contains(final char name) {
for (CloseBracketTypes type : CloseBracketTypes.values()) {
if (type.getBracket() == name) {
return true;
}
}
return false;
}
}
/**
* This method check the syntax for brackets. There should always exist a
* corresponding closing bracket for a open bracket of same type.
*
* It runs in O(N) time with O(N) worst case space complexity for the stack
* @param sentence The string whose syntax is to be checked
* @return True if the syntax of the given string is correct, false otherwise
*/
public static boolean matchBrackets(String sentence) {
boolean bracketsMatched = true;
// Check if sentence is null
if (sentence == null) {
throw new IllegalArgumentException("Input cannot be null");
}
// Empty string has correct syntax
if (sentence.isEmpty()) {
return bracketsMatched;
} else {
Stack<Character> brackets = new Stack<Character>();
char[] letters = sentence.toCharArray();
for (char letter : letters) {
// If the letter is a type of open bracket then push it
// in stack else if the letter is a type of closing bracket
// then pop it from the stack
if (OpenBracketTypes.contains(letter)) {
brackets.push(letter);
} else if (CloseBracketTypes.contains(letter)) {
if (!CloseBracketTypes.isBracketMatching(letter, brackets)) {
return false;
} else {
brackets.pop();
}
}
}
// If the stack is not empty then the syntax is incorrect
if (!brackets.isEmpty()) {
bracketsMatched = false;
}
}
return bracketsMatched;
}
/**
* @param args
*/
public static void main(String[] args) {
String words = "[[][][]Anfield[[]([])[]]becons()]";
boolean isSyntaxCorrect = SyntaxChecker.matchBrackets(words);
if (isSyntaxCorrect) {
System.out.println("The syntax is correct");
} else {
System.out.println("Incorrect syntax");
}
}
}
非常欢迎对此提供任何反馈。如果您发现有问题或无用，请批评。我只是想学习。
import java.util.*;
public class Parenthesis
{
public static void main (String ...argd)
{
Scanner sc=new Scanner(System.in);
System.out.println("enetr string");
String s=sc.nextLine();
Stack<Character> st=new Stack<Character>();
for (int i=0;i<s.length();++i)
{
if((s.charAt(i)=='(')||(s.charAt(i)=='{')||(s.charAt(i)=='['))
{
st.push(s.charAt(i));
}
else if(st.isEmpty()==false)
{
switch(s.charAt(i))
{
case']':
if(st.pop()!='[')
{
System.out.println("unbalanced");
System.exit(0);
}
break;
case'}':
if(st.pop()!='{')
{
System.out.println("unbalanced");
System.exit(0);
}
break;
case')':
if(st.pop()!='(')
{
System.out.println("unbalanced");
System.exit(0);
}
break;
}
}
}
if(st.isEmpty())
{
System.out.println("balanced paranthesis");
}
else
System.out.println("not balance");
}
}
对应的 Hackrrank 链接：https ://www.hackerrank.com/challenges/balanced-brackets/problem
import java.util.Stack;
class BalancedParenthesis {
static String isBalanced(String s) {
return isBalanced(s.toCharArray());
}
private static String isBalanced(final char[] chars) {
final Stack<Character> stack = new Stack<>();
for (char eachChar : chars) {
if (eachChar == '{' || eachChar == '[' || eachChar == '(') {
stack.push(eachChar);
} else {
if (stack.isEmpty()) {
return "NO";
}
if (correspondingCloseBracket(stack.peek()) != eachChar) {
return "NO";
}
stack.pop();
}
}
return stack.isEmpty() ? "YES" : "NO";
}
private static char correspondingCloseBracket(final char eachChar) {
if (eachChar == '{') {
return '}';
}
if (eachChar == '[') {
return ']';
}
return ')';
}
}
我假设nullor emptyvalue 是一个平衡的字符串，我使用 aMap来跟踪每个开始/结束括号：
static boolean isBalanced(String value) {
if (value == null || value.isBlank()) {
return true;
}
if (value.length() % 2 != 0) {
return false;
}
Map<Character, Character> bracketMirrors = Map.of('(', ')',
'{', '}',
'[', ']');
Deque<Character> characters = new ArrayDeque<>();
for (char c : value.toCharArray()) {
if (bracketMirrors.containsValue(c)) {
if (characters.isEmpty() || c != bracketMirrors.get(characters.pop())) {
return false;
}
} else {
characters.push(c);
}
}
return characters.isEmpty();
}
def balance (string):
if ((len(string)%2)!=0):
return("Not Balanced")
else:
check_num=[]
def check(num1,num2):
if ((num1=='['and num2==']') or (num1=='{'and num2=='}') or (num1=='('and num2==')')) :
check_num.append('B')
else:
check_num.append('N')
i=0
while i < (len(string)-1):
check(string[i],string[i+1])
i+=2
if 'N' in check_num:
return("Not Balanced")
else:
return("Balanced")
public class IsBalanced {
static Boolean isBalanced(String expStr) {
Boolean balanced = false;
int openedBraces = 0;
int closeddBraces = 0;
for (int i = 0; i < expStr.length(); i++) {
if (expStr.charAt(i) == '{' || expStr.charAt(i) == '(' || expStr.charAt(i) == '[') {
for (int j = i + 1; j < expStr.length(); j++) {
if (expStr.charAt(i) == '{') {
if (expStr.charAt(j) == '}') {
closeddBraces++;
break;
}
} else if (expStr.charAt(i) == '(') {
if (expStr.charAt(j) == ')') {
closeddBraces++;
break;
}
} else if (expStr.charAt(i) == '[') {
if (expStr.charAt(j) == ']') {
closeddBraces++;
break;
}
}
}
openedBraces++;
}
}
System.out.println("openedBraces : " + openedBraces + " , closeddBraces : " + closeddBraces);
if (openedBraces == closeddBraces) {
balanced = true;
}
return balanced;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "{[()]}[[]](";
if (isBalanced(str))
System.out.println("Balanced");
else
System.out.println("NotBalanced");
}
}