Come verificare se una stringa è bilanciata?

Question

Voglio testare se una stringa di input è bilanciata. Sarebbe bilanciato se vi fosse una parentesi chiusa, parentesi o parentesi aperta e chiusa.

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

Ho problemi a scegliere cosa fare. Devo inserire tutte le parentesi, parentesi o parentesi di apertura o chiusura in una pila e poi farle scoppiare? Se li faccio fuori, come mi aiuta davvero?

Answer 1

1) Per ogni staffa di apertura: { [ ( spingerlo in pila.

2) Per ogni staffa di chiusura: } ]) pop dalla pila e verificare se il tipo di parentesi corrisponde. Se non si restituisce false;

cioè attuale symbol in Stringa è } e se poped da stack è altro da { poi tornare false immediatamente.

3) Se la fine della riga e lo stack non sono vuoti, restituire false, altrimenti true.

Answer 2

Sì, una pila è una scelta adatta per l'attività oppure è possibile utilizzare una funzione ricorsiva. Se usi uno stack, allora l'idea è che spinga ciascuna staffa di apertura in pila, quando incontri una parentesi di chiusura, controlli che la cima della pila corrisponda. Se corrisponde, spegnilo, se non è un errore. Al termine, lo stack dovrebbe essere vuoto.

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

Beh, in parole povere, se è bilanciato, significa che lo stack dovrebbe essere vuoto.

Per questo, è necessario pop tuo stack quando si analizza un }

requisito aggiuntivo è quello di verificare che } è preceduta da { o il personaggio spuntato è un {.

Answer 4

Di seguito è riportato un esempio di codice Java per rilevare se una stringa è bilanciata.

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

L'idea è che -

• Per ciascun controvento apertura ([ {, spingerlo in pila.
• Per la parentesi di chiusura ) ] }, provare a inserire una coppia di rinforzi di apertura ([ } dallo stack. Se non riesci a trovare una parentesi graffa aperta, la stringa non è bilanciata.
• Se dopo l'elaborazione della stringa completa, lo stack è vuoto, la stringa viene bilanciata. Altrimenti la stringa non è bilanciata.

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

Qualsiasi commento su questo è il benvenuto. Per favore, critica se trovi qualcosa che è sbagliato o inutile. Sto solo cercando di imparare.

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