Как проверить, сбалансирована ли строка?

Question

Я хочу проверить, сбалансирована ли входная строка. Он будет сбалансирован, если есть соответствующие открывающие и закрывающие скобки, скобки или скобки.

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; 
} 

У меня возникли проблемы с выбором того, что делать. Должен ли я помещать каждую открывающую или закрывающуюся круглую скобку, скобку или скобки в стеке, а затем выталкивать их? Если я их вытащу, как это мне действительно помогает?

Answer 1

1) Для каждого открывающего кронштейна: { [ ( вставьте его в стек.

2) Для каждого закрывающего кронштейна: } ]) выскочить из стека и проверить, соответствует ли тип кронштейна. Если не вернуть false;

т.е. текущий символ в строки является } и если poped из стека все остальное из { затем вернуться false немедленно.

3) Если конец строки и стек не пуст, верните false, в противном случае true.

Answer 2

Да, стек является подходящим выбором для задачи или вы можете использовать рекурсивную функцию. Если вы используете стек, то идея заключается в том, что вы нажимаете каждую открывающую скобку в стеке, когда вы сталкиваетесь с закрывающей скобкой, вы проверяете, соответствует ли ей вершина стека. Если он совпадает, вытащите его, если это не ошибка. По завершении стек должен быть пустым.

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"); 
     } 
    } 
} 

Answer 3

Ну, грубо говоря, если оно сбалансировано, это означает, что ваш стек должен быть пустым.

Для этого вам нужно совать свой стек, когда вы разобрать }

Дополнительного требование, чтобы проверить, что } предшествует { или символ совал является {.

Answer 4

Ниже приведен пример кода Java, чтобы определить, сбалансирована ли строка.

http://introcs.cs.princeton.edu/java/43stack/Parentheses.java.html

Идея заключается в том, что -

• Для каждой открывающей фигурной скобкой ([ {, вставьте его в стек.
• Для закрытия скобки ) ] }, попробуйте поместить подходящую открывающую скобу ([ } из стека. Если вы не можете найти подходящую открывающую скобку, строка не будет сбалансирована.
• Если после обработки полной строки стек пуст, тогда строка сбалансирована. В противном случае строка не сбалансирована.

Answer 5

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"); 
     } 
    } 
} 

Любые отзывы об этом приветствуются. Пожалуйста, критикуйте, если вы обнаружите, что что-то не так или бесполезно. Я просто пытаюсь учиться.

Answer 6

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"); 
    } 
}