Las expresiones equilibradas de Java comprueban {}

Estoy intentando crear un progtwig que toma una cadena como argumento en su constructor. Necesito un método que compruebe si la cadena es una expresión equilibrada entre paréntesis. Necesita manejar ({[]}) cada necesidad abierta para equilibrar con su correspondiente corchete de cierre. Por ejemplo, un usuario podría ingresar [({})] que estaría equilibrado y} {estaría desequilibrado. Esto no necesita manejar letras o números. Necesito usar una stack para hacer esto.

Me dieron este pseudocódigo pero no sé cómo implementarlo en Java. Cualquier consejo sería asombroso. pseudocódigo

Actualización: lo siento, olvidé de publicar lo que tenía hasta ahora. Todo está desordenado porque al principio estaba tratando de usar char y luego probé una matriz … no estoy exactamente seguro de a dónde ir.

import java.util.*; public class Expression { Scanner in = new Scanner(System.in); Stack stack = new Stack(); public boolean check() { System.out.println("Please enter your expression."); String newExp = in.next(); String[] exp = new String[newExp]; for (int i = 0; i < size; i++) { char ch = exp.charAt(i); if (ch == '(' || ch == '[' || ch == '{') stack.push(i); else if (ch == ')'|| ch == ']' || ch == '}') { //nothing to match with if(stack.isEmpty()) { return false; } else if(stack.pop() != ch) { return false; } } } if (stack.isEmpty()) { return true; } else { return false; } } } 

Espero que este código pueda ayudar:

 import java.util.Stack; public class BalancedParenthensies { public static void main(String args[]) { System.out.println(balancedParenthensies("{(a,b)}")); System.out.println(balancedParenthensies("{(a},b)")); System.out.println(balancedParenthensies("{)(a,b}")); } public static boolean balancedParenthensies(String s) { Stack stack = new Stack(); for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(c == '[' || c == '(' || c == '{' ) { stack.push(c); } else if(c == ']') { if(stack.isEmpty() || stack.pop() != '[') { return false; } } else if(c == ')') { if(stack.isEmpty() || stack.pop() != '(') { return false; } } else if(c == '}') { if(stack.isEmpty() || stack.pop() != '{') { return false; } } } return stack.isEmpty(); } } 
 public static boolean isBalanced(String expression) { if ((expression.length() % 2) == 1) return false; else { Stack s = new Stack<>(); for (char bracket : expression.toCharArray()) switch (bracket) { case '{': s.push('}'); break; case '(': s.push(')'); break; case '[': s.push(']'); break; default : if (s.isEmpty() || bracket != s.peek()) { return false;} s.pop(); } return s.isEmpty(); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); String expression = in.nextLine(); boolean answer = isBalanced(expression); if (answer) { System.out.println("YES");} else { System.out.println("NO");} } 

La implementación java del pseudo código equivalente del algoritmo es java es la siguiente.

 import java.util.HashMap; import java.util.Map; import java.util.Stack; /** * @author Yogen Rai */ public class BalancedBracket { public static void main(String[] args) { String braces = "{{}("; if(isBalanced(braces)){ System.out.println("YES"); }else{ System.out.println("NO"); } } public static boolean isBalanced(String brackets) { // set matching pairs Map braces = new HashMap<>(); braces.put('(', ')'); braces.put('[',']'); braces.put('{','}'); // if length of string is odd, then it is not balanced if (brackets.length() % 2 != 0) { return false; } // travel half until openings are found and compare with // remaining if the closings matches Stack halfBraces = new Stack(); for(char ch: brackets.toCharArray()) { if (braces.containsKey(ch)) { halfBraces.push(braces.get(ch)); } // if stack is empty or if closing bracket is not equal to top of stack, // then braces are not balanced else if(halfBraces.isEmpty() || ch != halfBraces.pop()) { return false; } } return halfBraces.isEmpty(); } } 

Es importante usar una stack para empujar los símbolos de apertura, luego, cuando se encuentra con una abrazadera de cierre, saca el elemento de la parte superior de la stack y luego lo verifica para ver si coincide con el tipo de abrazadera de cierre. Aquí hay una implementación de Java.

 import java.util.Stack; public class Balanced { public static void main (String [] args) { String test_good = "()(){}{}{()}"; String test_bad = "((({}{}))()"; System.out.println(checkBalanced(test_good)); System.out.println(checkBalanced(test_bad)); } public static boolean checkBalanced(String check) { Stack S = new Stack(); for(int a = 0; a < check.length(); a++) { char let = check.charAt(a); if(let == '[' || let == '{' || let == '(') S.push(let); else if(let == ']' || let == '}' || let == ')') { if(S.empty()) return false; switch(let) { // Opening square brace case ']': if (S.pop() != '[') return false; break; // Opening curly brace case '}': if (S.pop() != '{') return false; break; // Opening paren brace case ')': if (S.pop() != '(') return false; break; default: break; } } } if(S.empty()) return true; return false; } } 

¿Te importa si agrego mi solución de estilo extraño basada en JavaScript ?

Es un material ad-hoc, no para producción, sino para las entrevistas o algo así. O simplemente por diversión.

El código :

 function reduceStr (str) { const newStr = str.replace('()', '').replace('{}', '').replace('[]', '') if (newStr !== str) return reduceStr(newStr) return newStr } function verifyNesting (str) { return reduceStr(str).length === 0 } 

Controles :

 console.log(verifyNesting('[{{[(){}]}}[]{}{{(())}}]')) //correct console.log(verifyNesting('[{{[(){}]}}[]{}{({())}}]')) //incorrect 

Explicación

Se eliminarán recursivamente los pares de cierres “()”, “[]” y “{}”:

 '[{{[(){}]}}[]{}{{(())}}]' '[{{}}[]{}{{(())}}]' '[{}{}{{()}}]' '[{}{{}}]' '[{{}}]' '[{}]' '' 

Si al final la longitud de la cadena estará vacía, es true , si no, es false .

PS pocas respuestas

  • ¿Por qué no para la producción?

Porque es lento y no le importa la posibilidad de que haya otros personajes entre pares.

  • ¿Por qué JS? Nos encanta java

Porque soy un desarrollador frontend pero cumplí la misma tarea, por lo que tal vez pueda ser útil para alguien. Y JS también es JVM lang =)

  • Pero por qué…

Porque todos los desarrolladores de JS están locos, por eso.

Estás presionando i – el índice – en la stack, y comparando contra ch . Usted debe empujar y hacer estallar ch .

Por favor, intente esto.

  import java.util.Stack; public class PatternMatcher { static String[] patterns = { "{([])}", "{}[]()", "(}{}]]", "{()", "{}" }; static String openItems = "{(["; boolean isOpen(String sy) { return openItems.contains(sy); } String getOpenSymbol(String byCloseSymbol) { switch (byCloseSymbol) { case "}": return "{"; case "]": return "["; case ")": return "("; default: return null; } } boolean isValid(String pattern) { if(pattern == null) { return false; } Stack stack = new Stack(); char[] symbols = pattern.toCharArray(); if (symbols.length == 0 || symbols.length % 2 != 0) { return false; } for (char c : symbols) { String symbol = Character.toString(c); if (isOpen(symbol)) { stack.push(symbol); } else { String openSymbol = getOpenSymbol(symbol); if (stack.isEmpty() || openSymbol == null || !openSymbol.equals(stack.pop())) { return false; } } } return stack.isEmpty(); } public static void main(String[] args) { PatternMatcher patternMatcher = new PatternMatcher(); for (String pattern : patterns) { boolean valid = patternMatcher.isValid(pattern); System.out.println(pattern + "\t" + valid); } } } 

Esta es mi implementación para esta pregunta. Este progtwig permite números, alfabetos y caracteres especiales con cadena de entrada, pero simplemente ignórelos al procesar la cadena.

CÓDIGO:

 import java.util.Scanner; import java.util.Stack; public class StringCheck { public static void main(String[] args) { boolean flag =false; Stack input = new Stack(); System.out.println("Enter your String to check:"); Scanner scanner = new Scanner(System.in); String sinput = scanner.nextLine(); char[] c = new char[15]; c = sinput.toCharArray(); for (int i = 0; i < c.length; i++) { if (c[i] == '{' || c[i] == '(' || c[i] == '[') input.push(c[i]); else if (c[i] == ']') { if (input.pop() == '[') { flag = true; continue; } else { flag = false; break; } } else if (c[i] == ')') { if (input.pop() == '(') { flag = true; continue; } else { flag = false; break; } } else if (c[i] == '}') { if (input.pop() == '{') { flag = true; continue; } else { flag = false; break; } } } if (flag == true) System.out.println("Valid String"); else System.out.println("Invalid String"); scanner.close(); } } 

Esta es mi propia implementación. Intenté hacerlo lo más corto y lo más claro posible:

 public static boolean isBraceBalanced(String braces) { Stack stack = new Stack(); for(char c : braces.toCharArray()) { if(c == '(' || c == '[' || c == '{') { stack.push(c); } else if((c == ')' && (stack.isEmpty() || stack.pop() != '(')) || (c == ']' && (stack.isEmpty() || stack.pop() != '[')) || (c == '}' && (stack.isEmpty() || stack.pop() != '{'))) { return false; } } return stack.isEmpty(); } 

Similar a uno de los códigos anteriores en JAVA, pero necesita una statement más agregada para evitar la comparación de la stack con otros caracteres que no sean llaves:

else if(bracketPair.containsValue(strExpression.charAt(i)))

 public boolean isBalanced(String strExpression){ Map bracketPair = new HashMap(); bracketPair.put('(', ')'); bracketPair.put('[', ']'); bracketPair.put('{', '}'); Stack stk = new Stack(); for(int i =0;i 

Este código funciona para todos los casos incluyen otros caracteres no solo paréntesis ex:
Por favor ingrese la entrada

{ibrahim[k]}
cierto

()[]{}[][]
verdadero saddsd] falso

 public class Solution { private static Map parenthesesMapLeft = new HashMap<>(); private static Map parenthesesMapRight = new HashMap<>(); static { parenthesesMapLeft.put('(', '('); parenthesesMapRight.put(')', '('); parenthesesMapLeft.put('[', '['); parenthesesMapRight.put(']', '['); parenthesesMapLeft.put('{', '{'); parenthesesMapRight.put('}', '{'); } public static void main(String[] args) { System.out.println("Please enter input"); Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); System.out.println(isBalanced(str)); } public static boolean isBalanced(String str) { boolean result = false; if (str.length() < 2) return false; Stack stack = new Stack<>(); for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (!parenthesesMapRight.containsKey(ch) && !parenthesesMapLeft.containsKey(ch)) { continue; } if (parenthesesMapLeft.containsKey(ch)) { stack.push(ch); } else { if (!stack.isEmpty() && stack.pop() == parenthesesMapRight.get(ch).charValue()) { result = true; } else { return false; } } } if (!stack.isEmpty()) return result = false; return result; } } 
  import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class BalancedParenthesisWithStack { /*This is purely Java Stack based solutions without using additonal data structure like array/Map */ public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); /*Take list of String inputs (parenthesis expressions both valid and invalid from console*/ List inputs=new ArrayList<>(); while (sc.hasNext()) { String input=sc.next(); inputs.add(input); } //For every input in above list display whether it is valid or //invalid parenthesis expression for(String input:inputs){ System.out.println("\nisBalancedParenthesis:"+isBalancedParenthesis (input)); } } //This method identifies whether expression is valid parenthesis or not public static boolean isBalancedParenthesis(String expression){ //sequence of opening parenthesis according to its precedence //ie '[' has higher precedence than '{' or '(' String openingParenthesis="[{("; //sequence of closing parenthesis according to its precedence String closingParenthesis=")}]"; //Stack will be pushed on opening parenthesis and popped on closing. Stack parenthesisStack=new Stack<>(); /*For expression to be valid : CHECK : 1. it must start with opening parenthesis [()... 2. precedence of parenthesis should be proper (eg. "{[" invalid "[{(" valid ) 3. matching pair if( '(' => ')') ie [{()}(())] ->valid [{)]not */ if(closingParenthesis.contains (((Character)expression.charAt(0)).toString())){ return false; }else{ for(int i=0;i 
 import java.util.Stack; public class StackParenthesisImplementation { public static void main(String[] args) { String Parenthesis = "[({})]"; char[] charParenthesis = Parenthesis.toCharArray(); boolean evalParanthesisValue = evalParanthesis(charParenthesis); if(evalParanthesisValue == true) System.out.println("Brackets are good"); else System.out.println("Brackets are not good"); } static boolean evalParanthesis(char[] brackets) { boolean IsBracesOk = false; boolean PairCount = false; Stack stack = new Stack(); for(char brace : brackets) { if(brace == '(' || brace == '{' || brace == '['){ stack.push(brace); PairCount = false; } else if(!stack.isEmpty()) { if(brace == ')' || brace == '}' || brace == ']') { char CharPop = stack.pop(); if((brace == ')' && CharPop == '(')) { IsBracesOk = true; PairCount = true; } else if((brace == '}') && (CharPop == '{')) { IsBracesOk = true; PairCount = true; } else if((brace == ']') && (CharPop == '[')) { IsBracesOk = true; PairCount = true; } else { IsBracesOk = false; PairCount = false; break; } } } } if(PairCount == false) return IsBracesOk = false; else return IsBracesOk = true; } } 
 public static void main(String[] args) { System.out.println("is balanced : "+isBalanced("(){}[]<>")); System.out.println("is balanced : "+isBalanced("({})[]<>")); System.out.println("is balanced : "+isBalanced("({[]})<>")); System.out.println("is balanced : "+isBalanced("({[<>]})")); System.out.println("is balanced : "+isBalanced("({})[<>]")); System.out.println("is balanced : "+isBalanced("({[}])[<>]")); System.out.println("is balanced : "+isBalanced("([{})]")); System.out.println("is balanced : "+isBalanced("[({}])")); System.out.println("is balanced : "+isBalanced("[(<{>})]")); System.out.println("is balanced : "+isBalanced("[")); System.out.println("is balanced : "+isBalanced("]")); System.out.println("is balanced : "+isBalanced("asdlsa")); } private static boolean isBalanced(String brackets){ char[] bracketsArray = brackets.toCharArray(); Stack stack = new Stack(); Map openingClosingMap = initOpeningClosingMap(); for (char bracket : bracketsArray) { if(openingClosingMap.keySet().contains(bracket)){ stack.push(bracket); }else if(openingClosingMap.values().contains(bracket)){ if(stack.isEmpty() || openingClosingMap.get(stack.pop())!=bracket){ return false; } }else{ System.out.println("Only < > ( ) { } [ ] brackets are allowed ."); return false; } } return stack.isEmpty(); } private static Map initOpeningClosingMap() { Map openingClosingMap = new HashMap(); openingClosingMap.put(Character.valueOf('('), Character.valueOf(')')); openingClosingMap.put(Character.valueOf('{'), Character.valueOf('}')); openingClosingMap.put(Character.valueOf('['), Character.valueOf(']')); openingClosingMap.put(Character.valueOf('<'), Character.valueOf('>')); return openingClosingMap; } 

Simplificando y haciendo legible. Uso de One Map solo y condiciones mínimas para obtener el resultado deseado.

¿Qué tal este, utiliza tanto el concepto de stack como el contador de cheques?

 import java.util.*; class Solution{ public static void main(String []argh) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String input=sc.next(); Stack stk = new Stack(); char[] chr = input.toCharArray(); int ctrl = 0, ctrr = 0; if(input.length()==0){ System.out.println("true"); } for(int i=0; i 

Esto puede ser usado. Pasa todas las pruebas.

 static String isBalanced(String s) { if(null == s){ return ""; } Stack bracketStack = new Stack<>(); int length = s.length(); if(length < 2 || length > 1000){ return "NO"; } for(int i = 0; i < length; i++){ Character c= s.charAt(i); if(c == '(' || c == '{' || c == '[' ){ bracketStack.push(c); } else { if(!bracketStack.isEmpty()){ char cPop = bracketStack.pop(); if(c == ']' && cPop!= '['){ return "NO"; } if(c == ')' && cPop!= '('){ return "NO"; } if(c == '}' && cPop!= '{'){ return "NO"; } } else{ return "NO"; } } } if(bracketStack.isEmpty()){ return "YES"; } else { return "NO"; } } 

Por favor, inténtalo. Lo revisé. Funciona correctamente

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.Stack; public class CloseBrackets { private static Map leftChar = new HashMap<>(); private static Map rightChar = new HashMap<>(); static { leftChar.put('(', '('); rightChar.put(')', '('); leftChar.put('[', '['); rightChar.put(']', '['); leftChar.put('{', '{'); rightChar.put('}', '{'); } public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String st = bf.readLine(); System.out.println(isBalanced(st)); } public static boolean isBalanced(String str) { boolean result = false; if (str.length() < 2) return false; Stack stack = new Stack<>(); /* For Example I gave input * str = "{()[]}" */ for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (!rightChar.containsKey(ch) && !leftChar.containsKey(ch)) { continue; } // Left bracket only add to stack. Other wise it will goes to else case // For both above input how value added in stack // "{(" after close bracket go to else case if (leftChar.containsKey(ch)) { stack.push(ch); } else { if (!stack.isEmpty()) { // For both input how it performs // 3rd character is close bracket so it will pop . pop value is "(" and map value for ")" key will "(" . So both are same . // it will return true. // now stack will contain only "{" , and travers to next up to end. if (stack.pop() == rightChar.get(ch).charValue() || stack.isEmpty()) { result = true; } else { return false; } } else { return false; } } } if (!stack.isEmpty()) return result = false; return result; } } 

Aquí está el Código. He probado todos los casos de prueba posibles en Hacker Rank.

static String isBalanced (Entrada de cadena) {

  Stack stack = new Stack(); for (int i = 0; i < input.length(); i++) { Character ch = input.charAt(i); if (input.charAt(i) == '{' || input.charAt(i) == '[' || input.charAt(i) == '(') { stack.push(input.charAt(i)); } else { if (stack.isEmpty() || (stack.peek() == '[' && ch != ']') || (stack.peek() == '{' && ch != '}') || (stack.peek() == '(' && ch != ')')) { return "NO"; } else { stack.pop(); } } } if (stack.empty()) return "YES"; return "NO"; } 

Usando referencia de nodo podemos verificar fácilmente

 import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class CloseBracketsBalance { private static final Map closeBracket= new HashMap<>(); private static final List allBrac = new ArrayList<>(); static { allBrac.add("["); allBrac.add("]"); allBrac.add("{"); allBrac.add("}"); allBrac.add("("); allBrac.add(")"); closeBracket.put("]", "["); closeBracket.put("}", "{"); closeBracket.put(")", "("); } public static void main(String[] args) { System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd)})]")); // return true System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd}))]")); // return false } public static boolean checkSheetIsbalance(String c) { char[] charArr = c.toCharArray(); Node node = null; for(int i=0,j=charArr.length;i 

El método mejorado, de @Smartoop.

 public boolean balancedParenthensies(String str) { List leftKeys = Arrays.asList('{', '(', '<', '['); List rightKeys = Arrays.asList('}', ')', '>', ']'); Stack stack = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (leftKeys.contains(c)) { stack.push(c); } else if (rightKeys.contains(c)) { int index = rightKeys.indexOf(c); if (stack.isEmpty() || stack.pop() != leftKeys.get(index)) { return false; } } } return stack.isEmpty(); } 
 package com.me.hr; import java.util.HashMap; import java.util.Scanner; import java.util.Stack; public class Paranthesis { public static void main(String[] argh) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String input = sc.next(); Paranthesis obj = new Paranthesis(); System.out.println(obj.isEven(input)); } // Complete the code } sc.close(); } boolean isEven(String token) { HashMap paranthesisMap = new HashMap(); paranthesisMap.put('{', '}'); paranthesisMap.put('[', ']'); paranthesisMap.put('(', ')'); // List closingThesis = Arrays.asList('}',']',')'); char[] chars = token.toCharArray(); Stack stack = new Stack(); for (char ch : chars) { boolean push = true; // Not Allow closing prthese first if (stack.isEmpty() && paranthesisMap.values().contains(ch)) return false; // Pop Out Matching closing prthese if (!stack.isEmpty() && paranthesisMap.values().contains(ch)) { char peek = stack.peek(); if (paranthesisMap.get(peek).equals(ch)) { stack.pop(); push = false; } else { // Otherwise not matching return false; } } if (push) stack.push(ch); } if (stack.isEmpty()) return true; return false; } } 
 **// balanced parentheses problem (By fabboys)** #include  #include  using namespace std; class Stack{ char *arr; int size; int top; public: Stack(int s) { size = s; arr = new char[size]; top = -1; } bool isEmpty() { if(top == -1) return true; else return false; } bool isFull() { if(top == size-1) return true; else return false; } void push(char n) { if(isFull() == false) { top++; arr[top] = n; } } char pop() { if(isEmpty() == false) { char x = arr[top]; top--; return x; } else return -1; } char Top() { if(isEmpty() == false) { return arr[top]; } else return -1; } Stack{ delete []arr; } }; int main() { int size=0; string LineCode; cout<<"Enter a String : "; cin >> LineCode; size = LineCode.length(); Stack s1(size); char compare; for(int i=0;i<=size;i++) { if(LineCode[i]=='(' || LineCode[i] == '{' || LineCode[i] =='[') s1.push(LineCode[i]); else if(LineCode[i]==']') { if(s1.isEmpty()==false){ compare = s1.pop(); if(compare == 91){} else { cout<<" Error Founded"; return 0;} } else { cout<<" Error Founded"; return 0; } } else if(LineCode[i] == ')') { if(s1.isEmpty() == false) { compare = s1.pop(); if(compare == 40){} else{ cout<<" Error Founded"; return 0; } }else { cout<<"Error Founded"; return 0; } }else if(LineCode[i] == '}') { if(s1.isEmpty() == false) { compare = s1.pop(); if(compare == 123){} else{ cout<<" Error Founded"; return 0; } }else { cout<<" Error Founded"; return 0; } } } if(s1.isEmpty()==true) { cout<<"No Error in Program:\n"; } else { cout<<" Error Founded"; } return 0; }