Balancing parentheses, how to check if they are in the correct position?

Asked

Viewed 89 times

1

I’m making a program that takes a string and checks if open parentheses are closed. I have the following code:

int abertos = 0, fechados = 0; //conta os parenteses
    parens = parens.replaceAll("[^()]", "");//fiz essa linha considerando que a entrada contenha caracteres que não sejam parenteses
    for (int i = 0; i < parens.length(); i++){
        if (parens.charAt(i) == '(')
            abertos++;
        if (parens.charAt(i) == ')')
            fechados++;
        return abertos == fechados ? true : false;
    }

If the input is " () " or " )("it returns true, but everyone agrees that " )( " are not closed parentheses, so I need a script to resolve this situation. But, what? I spent a couple of hours cracking my head and I did not find the answer, I ask the help of readers!

java
  • 2

    You can use a stack, and each time you close a parentheses it will take out one of this stack, if what you take out does not match, it means it closed wrong

  • 1

    Thank you very much Natan, I am beginner and still did not know the Stack class, helped me a lot!

2 answers

2

As indicated in comments you can use a stack to test the balancing of parentheses of a sentence.

The mechanism is simple, take a string as input and iterate by its characters every time:

  • find an opening parenthesis, (, Pop him.
  • find a closing parenthesis, ), check out:
    • if the battery is empty it is because the input is unbalanced.
    • if the top of the stack contains an opening parenthesis, (, blow him out.
  • find a character deferent to an opening parenthesis, (, or a closing bracket, ) ignore him.

After iterating by input characters:

  • if the stack is empty it is because the input is balanced.
  • if remaining elements in the stack is because the input is unbalanced.

Example:

import java.lang.*;
import java.io.*; 
import java.util.*;

class Main {  
  
  static Stack<Character> pilha = new Stack<Character>();
  
  public static void main(String args[]) {         
    String s = System.console().readLine(">>>");     //Lê uma linha.
    //Itera por cada caractere da sentença s...
    for (int i = 0; i < s.length(); i++){
      char c = s.charAt(i);     
      //...verifica se o caractere é (...
      if (c == '(') {
        pilha.push(c);                              //...empilhe o caractere.
      //...verifica se o caractere é )...
      } else if (c == ')') {
        //...verifica se a pilha estiver vazia...
        if (pilha.empty()){
          System.out.println("Desbalanceado");      //...expressão desbalanceada.
          return;                                   //...encerra a função.
        }
        pilha.pop();                                //...remove o que estiver no topo da pilha.
      }
    }
    //Verifica se após a iteração a pilha não estiver vazia...
    if (!pilha.empty()){
      System.out.println("Desbalanceado");          //...expressão desbalanceada.
      return;                                       //...encerra a função.
    }    
    System.out.println("Balanceado");               //a expressão está balanceada.
  } 
}

0

A script possibility for your scenario

    int abertos = 0; 
    parens = parens.replaceAll("[^()]", "");
    if(parens.length() % 2 != 0) return false; //Caso não seja um valor par também será falso e não precisa entra no loop
    
    for (int i = 0; i < parens.length(); i++){
            if (abertos == 0 && parens.charAt(i) == ')') return false; //caso não tenha nenhum parentes aberto e seja um fechado já retorna false
            if (parens.charAt(i) == '(') abertos++;
            if (parens.charAt(i) == ')') abertos--;
        }
    return abertos == 0; //Caso a quantidade parentes não seja igual a zero, então também está errado

Browser other questions tagged java

You are not signed in. Login or sign up in order to post.