Comment vérifier si une chaîne est équilibrée?

Question

Je veux tester si une chaîne d'entrée est équilibrée. Il serait équilibré s'il y avait une parenthèse ouvrante et fermante, une parenthèse ou une accolade.

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

J'ai des problèmes pour choisir quoi faire. Devrais-je mettre chaque parenthèse, parenthèse ou accolade d'ouverture ou de fermeture dans une pile, puis les sortir? Si je les montre, comment cela m'aide vraiment?

Answer 1

1) Pour chaque parenthèse ouvrante: { [ ( poussez-la dans la pile.

2) Pour chaque crochet de fermeture: } ]) sauter de la pile et vérifier si le type de support correspond. Si ce n'est pas le cas, retournez false;

dire symbole en cours dans la chaîne est } et si poped de la pile est autre chose de { puis revenez immédiatement false.

3) Si la fin de ligne et la pile ne sont pas vides, renvoyer false, sinon true.

Answer 2

Oui, une pile est un choix approprié pour la tâche ou vous pouvez utiliser une fonction récursive. Si vous utilisez une pile, l'idée est que vous poussez chaque parenthèse ouvrante sur la pile, quand vous rencontrez une parenthèse fermante, vous vérifiez que le haut de la pile correspond. Si cela correspond, faites-le disparaître, sinon c'est une erreur. Une fois terminée, la pile devrait être vide.

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

Eh bien, en gros, si c'est équilibré, cela signifie que votre pile devrait être vide.

Pour cela, vous devez faire apparaître votre pile lorsque vous analysez un }

exigence supplémentaire est de vérifier que } est précédée par { ou le caractère est un { sauté.

Answer 4

Voici un exemple de code Java pour détecter si une chaîne est équilibrée.

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

L'idée est que -

• Pour chaque accolade ouvrante ([ {, appuyez sur la pile.
• Pour la fermeture de l'accolade ) ] }, essayez d'ouvrir une accolade d'ouverture correspondante ([ } à partir de la pile. Si vous ne trouvez pas d'accolade d'ouverture correspondante, la chaîne n'est pas équilibrée.
• Si après avoir traité la chaîne complète, la pile est vide alors la chaîne est équilibrée. Sinon, la chaîne n'est pas équilibrée.

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

Tout commentaire à ce sujet est le bienvenu. Veuillez critiquer si vous trouvez que quelque chose ne va pas ou est inutile. J'essaie juste d'apprendre.

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