parentesis - pilas en java codigo
Emparejamiento de paréntesis/corchetes utilizando el algoritmo de pila (22)
Por ejemplo, si los paréntesis / corchetes coinciden en lo siguiente:
({})
(()){}()
()
y así sucesivamente, pero si el paréntesis / corchetes no coincide, debería devolver falso, por ejemplo:
{}
({}(
){})
(()
y así. ¿Puedes por favor revisar este código? Gracias por adelantado.
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == ''{'')
return false;
if(c == ''('')
stack.push(c);
if(c == ''{'') {
stack.push(c);
if(c == ''}'')
if(stack.empty())
return false;
else if(stack.peek() == ''{'')
stack.pop();
}
else if(c == '')'')
if(stack.empty())
return false;
else if(stack.peek() == ''('')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String[] args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
Aquí hay una solución en Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack = []
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {([])} if brackets have match."))
El algoritmo:
- escanee la cadena, empujando a una pila para cada ''('' encontrado en la cadena
- si se ha escaneado char '')'', saca uno ''('' de la pila
Ahora, los paréntesis están equilibrados para dos condiciones:
- ''('' puede sacarse de la pila para cada '')'' que se encuentra en la cadena, y
- la pila está vacía al final (cuando se procesa toda la cadena)
En realidad, no hay necesidad de verificar ningún caso "manualmente". Solo puedes ejecutar el siguiente algoritmo:
Iterar sobre la secuencia dada. Comience con una pila vacía.
Si el char actual es un soporte de apertura, simplemente empújelo hacia la pila.
Si se trata de un soporte de cierre, compruebe que la pila no esté vacía y que el elemento superior del paso sea un soporte de apertura adecuado (es decir, coincida con este). Si no es así, informar un error. De lo contrario, saque el elemento superior de la pila.
Al final, la secuencia es correcta si la pila está vacía.
¿Por qué es correcto? Aquí hay un bosquejo de una prueba: si este algoritmo informó que la secuencia se corrigió, se encontró un par coincidente de todos los paréntesis. Por lo tanto, la secuencia es de hecho correcta por definición. Si ha reportado un error:
Si la pila no estaba vacía al final, el saldo de los corchetes de apertura y cierre no es cero. Por lo tanto, no es una secuencia correcta.
Si la pila estaba vacía cuando tuvimos que hacer estallar un elemento, el saldo vuelve a estar apagado.
Si había un elemento incorrecto en la parte superior de la pila, un par de corchetes "incorrectos" deberían coincidir entre sí. Significa que la secuencia no es correcta.
He demostrado que:
Si el algoritmo ha informado que la secuencia es correcta, es correcta.
Si el algoritmo ha informado que la secuencia no es correcta, es incorrecta (tenga en cuenta que no utilizo el hecho de que no hay otros casos excepto los que se mencionan en su pregunta).
Estos dos puntos implican que este algoritmo funciona para todas las entradas posibles.
Este código es más fácil de entender:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == ''{'' || current == ''('' || current == ''['')
{
stack.push(current);
}
if (current == ''}'' || current == '')'' || current == '']'')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == ''}'' && last == ''{'' || current == '')'' && last == ''('' || current == '']'' && last == ''['')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
He intentado esto usando javascript a continuación es el resultado.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = [''{'', ''['', ''(''];
var closingBraces = [''}'', '']'', '')''];
var stack = [];
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'''',
''test'',
''{{[][]()()}()}[]()'',
''{test{[test]}}'',
''{test{[test]}'',
''{test{(yo)[test]}}'',
''test{[test]}}'',
''te()s[]t{[test]}'',
''te()s[]t{[test''
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
He visto respuestas aquí y casi todos lo hicieron bien. Sin embargo, he escrito mi propia versión que utiliza un Diccionario para administrar los pares de corchetes y una pila para monitorear el orden de las llaves detectadas. También he escrito una entrada de blog para esto.
Aqui esta mi clase
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "()[]{}" is balanced.
// "{([])}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{''['', '']''},
{''('', '')''},
{''{'', ''}''}
};
}
}
La respuesta anterior de Ganesan no es correcta y no me permite comentar ni editar su publicación. Así que abajo está la respuesta correcta. Ganesan tiene una orientación incorrecta "[" y falta la comprobación de la pila IsEmpty ().
El siguiente código devolverá verdadero si las llaves coinciden correctamente.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('')'', ''('');
openClosePair.put(''}'', ''{'');
openClosePair.put('']'', ''['');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
Si quieres echar un vistazo a mi código. Solo para referencia
public class Default {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp==''['' || tmp==''{'' || tmp==''(''){
exprStack.push(tmp);
}else if(tmp=='']'' || tmp==''}'' || tmp=='')''){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp=='']'' && peekElement!=''[''){
stringBalanced="NO";
}else if(tmp==''}'' && peekElement!=''{''){
stringBalanced="NO";
}else if(tmp=='')'' && peekElement!=''(''){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
Su código tiene cierta confusión en el manejo de los caracteres ''{'' y ''}''. Debe ser completamente paralelo a la forma en que manejas ''('' y '')''.
Este código, modificado ligeramente con respecto al tuyo, parece funcionar correctamente:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == ''{'')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == ''('')
stack.push(c);
else if(c == ''{'')
stack.push(c);
else if(c == '')'')
if(stack.empty())
return false;
else if(stack.peek() == ''('')
stack.pop();
else
return false;
else if(c == ''}'')
if(stack.empty())
return false;
else if(stack.peek() == ''{'')
stack.pop();
else
return false;
}
return stack.empty();
}
en java no quieres comparar la cadena o el carácter por == signos. Usted usaría el método de iguales. equalsIgnoreCase o algo por el estilo. Si usa == debe apuntar a la misma ubicación de memoria. En el método a continuación, intenté usar intenciones para solucionar esto. usando ints aquí desde el índice de cadena ya que cada llave de apertura tiene una llave de cierre. Quería usar la coincidencia de ubicación en lugar de una comparación de comparación. Pero creo que con esto tienes que ser intencional en donde colocas los caracteres de la cadena. También consideremos que Sí = verdadero y No = falso para simplificar. Esta respuesta asume que usted pasó una matriz de cadenas para inspeccionar y requirió una matriz de si sí (coincidieron) o No (no lo hicieron)
import java.util.Stack;
public static void main(String[] args) {
//String[] arrayOfBraces = new String[]{"{[]}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "()[]{}" is balanced.
// "{([])}" is balanced
// "{([)]}" is _not_ balanced
String[] arrayOfBraces = new String[]{"{[]}","([{}])","{}{()}","()[]{}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String[] answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
El algoritmo es:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
En código Java :
public class StackDemo {
public static void main(String[] args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char[] array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ''['' || arr[i] == ''{'' || arr[i] == ''('')
push(arr[i]);
else if (arr[i] == ''}'' && peek() == ''{'')
pop();
else if (arr[i] == '']'' && peek() == ''['')
pop();
else if (arr[i] == '')'' && peek() == ''('')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Salida:
--Bracket checker--
La cuerda esta balanceada
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}[][]{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next [], next [], next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String[] args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a==''{''||a==''[''||a==''('')
{
open = open+1;
continue;
}
if(a==''}''||a=='']''||a=='')''){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace(''{'', ''}'');
stringfirst = stringfirst.replace(''('', '')'');
stringfirst = stringfirst.replace(''['', '']'');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
import java.util.*;
class StackDemo {
public static void main(String[] argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
import java.util.*;
public class MatchBrackets {
public static void main(String[] argh) {
String input = "[]{[]()}";
System.out.println (input);
char [] openChars = {''['',''{'',''(''};
char [] closeChars = {'']'',''}'','')''};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c[]=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]==''('' || c[i]==''['' || c[i]==''{'')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc=='')'' && stk.peek()==''('' )
{
stk.pop();
}
else if(cc=='']'' && stk.peek()==''['' )
{
stk.pop();
}
else if(cc==''}'' && stk.peek()==''{'' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c==''('')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==''{'')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='')'')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()==''('')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()==''('' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c==''}'')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()==''{'')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c==''('')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String[] args) {
String[] values = { "()]", "[()]" };
String[] rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String[] match(String[] values) {
String[] returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == ''{'')
return endmatch == ''}'';
if (start == ''('')
return endmatch == '')'';
if (start == ''['')
return endmatch == '']'';
return false;
}
}
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == ''['' && stack.peek() == '']'') ||
(topStackChar == ''{'' && stack.peek() == ''}'') ||
(topStackChar == ''('' && stack.peek() == '')'')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ ''('', '')'' },
{ ''{'', ''}'' },
{ ''['', '']'' },
{ ''<'', ''>'' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the ''opening'' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the ''closing'' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the ''latest'' ''opening'' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(''('', '')'');
openClosePair.put(''{'', ''}'');
openClosePair.put(''['', '']'');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('')'', ''('');
openClosePair.put(''}'', ''{'');
openClosePair.put('']'', ''['');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}