Проверка сбалансированных выражений Java {[()]}

Я пытаюсь создать программу, которая принимает строку в качестве аргумента в свой конструктор. Мне нужен метод, который проверяет, является ли строка сбалансированным выражением в скобках. Он должен обрабатывать ({[]}), каждый открытый должен балансировать с соответствующей закрывающей скобкой. Например, пользователь может ввести [({})], который будет сбалансирован, а} {будет неуравновешенным. Это не нужно обрабатывать буквы или цифры. Для этого мне нужно использовать стек.

Мне был дан этот псевдокод, но я не могу понять, как его реализовать в java. Любые советы были бы замечательными. псевдокод

Обновление - извините, забыл опубликовать то, что у меня было до сих пор. Его все испортилось, потому что сначала я пытался использовать char, а затем я попробовал массив.. im не совсем уверен, куда идти.

import java.util.*;

public class Expression
{
  Scanner in = new Scanner(System.in);
  Stack<Integer> stack = new Stack<Integer>();



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


}

Ответы

Ответ 1

Я надеюсь, что этот код может помочь:

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<Character> stack  = new Stack<Character>();
        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();
    }
}

Ответ 2

public static boolean isBalanced(String expression) {
  if ((expression.length() % 2) == 1) return false;
  else {
    Stack<Character> 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");}

}

Ответ 3

Псевдокод эквивалентной Java-реализации алгоритма заключается в следующем.

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<Character, Character> 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<Character> 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();
    }
}

Ответ 4

Важно использовать стек, чтобы нажимать на него открывающие символы, а затем, когда вы сталкиваетесь с закрывающей скобкой, вы вынимаете элемент из верхней части стека, а затем проверяете его, чтобы увидеть, соответствует ли он типу закрывающей фигурной скобки. Вот реализация 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<Character> S = new Stack<Character>();
        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;
    }
}

Ответ 5

Вы не возражаете, если я добавлю свое причудливое решение на основе JavaScript?

Это рекламный материал, а не для производства, а для интервью или что-то в этом роде. Или просто для удовольствия.

Код:

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
}

Проверка

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

Объяснение

Он будет рекурсивно удалять пары закрытий "()", "[]" и "{}":

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

Если в конце длина строки будет пустой - это true, если нет - это false.

P.S. Несколько ответов

  • Почему не для производства?

Потому что он медленный и не заботится о возможности появления других символов между парами.

  • Почему JS? Мы любим Java

Потому что я сторонний разработчик, но встретил ту же задачу, поэтому, возможно, это может быть полезно для кого-то. И JS также является JVM lang =)

  • Но почему...

Потому что все разработчики JS безумны, поэтому.

Ответ 6

Вы нажимаете i - индекс - на стек и сравниваете с ch. Вы должны нажать и поп ch.

Ответ 7

Пожалуйста, попробуйте это.

    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<String> stack = new Stack<String>();
            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);
            }
        }

    }

Ответ 8

Это моя реализация для этого вопроса. Эта программа позволяет номера, алфавиты и специальные символы со строкой ввода, но просто игнорирует их при обработке строки.

CODE:

import java.util.Scanner;
import java.util.Stack;

public class StringCheck {

    public static void main(String[] args) {
        boolean flag =false;
        Stack<Character> input = new Stack<Character>();
        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();

    }

}

Ответ 9

Этот код работает для всех случаев, включая другие символы, а не только круглые скобки например:
Введите ввод

{ibrahim[k]}
true

()[]{}[][]
правда saddsd] ложь

public class Solution {

    private static Map<Character, Character> parenthesesMapLeft = new HashMap<>();
    private static Map<Character, Character> 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<Character> 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;
    }
}

Ответ 10

Это моя собственная реализация. Я попытался сделать его максимально коротким:

public static boolean isBraceBalanced(String braces) {
    Stack<Character> stack = new Stack<Character>();

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

Ответ 11

    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<String> 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
         //i.e. '[' 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<Character> 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(  '(' => ')')  i.e. [{()}(())] ->valid [{)]not 
          */
         if(closingParenthesis.contains
         (((Character)expression.charAt(0)).toString())){
            return false;
        }else{
        for(int i=0;i<expression.length();i++){

        char ch= (Character)expression.charAt(i);

        //if parenthesis is opening(ie any of '[','{','(') push on stack
        if(openingParenthesis.contains(ch.toString())){
                parenthesisStack.push(ch);
            }else if(closingParenthesis.contains(ch.toString())){
        //if parenthesis is closing (ie any of ']','}',')') pop stack
        //depending upon check-3 
                if(parenthesisStack.peek()=='(' && (ch==')') || 
                    parenthesisStack.peek()=='{' && (ch=='}') ||    
                    parenthesisStack.peek()=='[' && (ch==']')
                        ){
                parenthesisStack.pop();
                }
            }
        }

        return (parenthesisStack.isEmpty())? true : false;
        }
    }

Ответ 12

Подобно одному из приведенных выше кодов в JAVA, но ему требуется еще одно выражение else, чтобы избежать сравнения стека с символами, отличными от фигурных скобок:

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

public boolean isBalanced(String strExpression){
 Map<Character,Character> bracketPair = new HashMap<Character,Character>();
  bracketPair.put('(', ')');
  bracketPair.put('[', ']');
  bracketPair.put('{', '}');
  Stack<Character> stk = new Stack<Character>();
        for(int i =0;i<strExpression.length();i++){
            if(bracketPair.containsKey(strExpression.charAt(i)))
                stk.push(strExpression.charAt(i));
            else if(bracketPair.containsValue(strExpression.charAt(i))) 
                if(stk.isEmpty()||bracketPair.get(stk.pop())!=strExpression.charAt(i))
                return false;
        }

        if(stk.isEmpty())
            return true;
            else
                return false;
        }

Ответ 13

Альтернативой Hashmap и эффективным способом будет использование Deque:

public boolean isValid(String s) 
{
    if(s == null || s.length() == 0)
        return true;

     Deque<Character> stack = new ArrayDeque<Character>();
     for(char c : s.toCharArray()) 
     {
         if(c == '{')
            stack.addFirst('}');

          else if(c == '(')
            stack.addFirst(')');

           else if(c == '[')
              stack .addFirst(']');

            else if(stack.isEmpty() || c != stack.removeFirst())
               return false;
     }
             return stack.isEmpty();
}

Ответ 14

Поздняя почта. 

package com.prac.stack;

public class BalanceBrackets {

public static void main(String[] args) {
    String str = "{()}[]";
    char a[] = str.toCharArray();
    System.out.println(check(a));
}

static boolean check(char[] t) {
    Stackk st = new Stackk();
    for (int i = 0; i < t.length; i++) {
        if (t[i] == '{' || t[i] == '(' || t[i] == '[') {
            st.push(t[i]);
        }
        if (t[i] == '}' || t[i] == ')' || t[i] == ']') {
            if (st.isEmpty()) {
                return false;
            } else if (!isMatching(st.pop(), t[i])) {
                return false;
            }
        }
    }

    if (st.isEmpty()) {
        return true;
    } else {
        return false;
    }
}

static boolean isMatching(char a, char b) {
    if (a == '(' && b == ')') {
        return true;
    } else if (a == '{' && b == '}') {
        return true;
    } else if (a == '[' && b == ']') {
        return true;
    } else {
        return false;
    }
}

}

Ответ 15

Использование switch-case для лучшей читаемости и обработки других сценариев:

import java.util.Scanner;
import java.util.Stack;

public class JavaStack
{
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String input = sc.next();
            System.out.println(isStringBalanced(input));
        }
        scanner.close();

    }

    private static boolean isStringBalanced(String testString)
    {
        Stack<Character> stack = new Stack<Character>();
        for (char c : testString.toCharArray()) {
            switch (c) {
                case '[':
                case '(':
                case '{':
                    stack.push(c);
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        // stack has to be empty, if not, the balance was wrong
        return stack.empty();
    }
}

Ответ 16

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<Character> stack = new Stack<Character>();
                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;
            }
        }

Ответ 17

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<Character> stack = new Stack<Character>();
    Map<Character, Character> 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<Character, Character> initOpeningClosingMap() {
    Map<Character, Character> openingClosingMap = new HashMap<Character, Character>();
    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;
}

Упрощение и чтение. Использование только одной карты и минимальные условия для получения желаемого результата.

Ответ 18

Как об этом, он использует обе концепции стека плюс проверки счетчика:

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<Character> stk = new Stack<Character>();
      char[] chr = input.toCharArray();
      int ctrl = 0, ctrr = 0;
      if(input.length()==0){
          System.out.println("true");
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='{'||chr[i]=='('||chr[i]=='['){
              ctrl++;
              stk.push(chr[i]);
              //System.out.println(stk);
          }
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='}'||chr[i]==')'||chr[i]==']'){
              ctrr++;
              if(!stk.isEmpty())
                  stk.pop();
              //System.out.println(stk);
          }
      }
      //System.out.println(stk);
      if(stk.isEmpty()&&ctrl==ctrr)
        System.out.println("true");
      else
        System.out.println("false");
      }
   }
}

Ответ 19

Это можно использовать. Пропускает все тесты.

static String isBalanced(String s) {

    if(null == s){
        return "";
    }

    Stack<Character> 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";
    }

}

Ответ 20

Пожалуйста, попробуйте это, я проверил его. Он работает правильно

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<Character, Character> leftChar = new HashMap<>();
    private static Map<Character, Character> 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<Character> 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;
    }
}

Ответ 21

Вот кодекс. Я проверил все возможные тестовые примеры на Hacker Rank.

static String isBalanced(String input) {

    Stack<Character> stack = new Stack<Character>();
    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";

}

Ответ 22

Используя ссылку node, мы можем легко проверить

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class CloseBracketsBalance {
    private static final Map<String, String> closeBracket= new HashMap<>();
    private static final List<String> 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<j;i++) {
            String ch = charArr[i]+"";
            if(!allBrac.contains(ch)) {
                continue;
            }

            if(closeBracket.containsKey(ch)) {
                // node close bracket               
                if(node == null) {
                    return false;
                }
                if(!(node.nodeElement).equals(closeBracket.get(ch))) {
                    return false;
                }
                node = node.parent; 
            } else {
                //make node for open bracket                
                 node = new Node(ch, node);
            }
        }       

        if(node != null) {
            return false;
        }

        return true;
    }
}


class Node {
    public String nodeElement;
    public Node parent;
    public Node(String el, Node p) {
        this.nodeElement = el;
        this.parent = p;
    }
}

Ответ 23

Улучшенный метод, от @Smartoop.

public boolean balancedParenthensies(String str) {
    List<Character> leftKeys = Arrays.asList('{', '(', '<', '[');
    List<Character> rightKeys = Arrays.asList('}', ')', '>', ']');

    Stack<Character> 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();
}

Ответ 24

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<Character, Character> paranthesisMap = new HashMap<Character, Character>();
        paranthesisMap.put('{', '}');
        paranthesisMap.put('[', ']');
        paranthesisMap.put('(', ')');

        // List<Character> closingThesis = Arrays.asList('}',']',')');
        char[] chars = token.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        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;
    }

}

Ответ 25

public void validateExpression(){

    if(!str.isEmpty() && str != null){
        if( !str.trim().equals("(") && !str.trim().equals(")")){

            char[] chars = str.toCharArray();

            for(char c: chars){
                if(!Character.isLetterOrDigit(c) && c == '('  || c == ')') {
                    charList.add(c);
                }
            }

            for(Character ele: charList){                   
                if(operatorMap.get(ele) != null && operatorMap.get(ele) != 0){                      
                    operatorMap.put(ele,operatorMap.get(ele)+1);
                }else{
                    operatorMap.put(ele,1);
                }
            }

            for(Map.Entry<Character, Integer> ele: operatorMap.entrySet()){
                System.out.println(String.format("Brace Type \"%s\" and count is \"%d\" ", ele.getKey(),ele.getValue()));                   
            }

            if(operatorMap.get('(') == operatorMap.get(')')){
                System.out.println("**** Valid Expression ****");
            }else{
                System.out.println("**** Invalid Expression ****");
            }

        }else{
            System.out.println("**** Incomplete expression to validate ****");
        }

    }else{
        System.out.println("**** Expression is  empty or null ****");
    }       
}

Ответ 26

Рассматриваемая строка состоит только из '(' ')' '{' '}' '[' ']'. Вот метод кода, который возвращает истину или ложь в зависимости от того, сбалансировано уравнение или нет.

private static boolean checkEquation(String input) {

    List<Character> charList = new ArrayList<Character>();

    for (int i = 0; i < input.length(); i++) {

        if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
            charList.add(input.charAt(i));
        } else if ((input.charAt(i) == ')' && charList.get(charList.size() - 1) == '(')
                || (input.charAt(i) == '}' && charList.get(charList.size() - 1) == '{')
                || (input.charAt(i) == ']' && charList.get(charList.size() - 1) == '[')) {
            charList.remove(charList.size() - 1);
        } else
            return false;

    }

    if(charList.isEmpty())
        return true;
    else
        return false;
}

Ответ 27

///check Parenthesis
public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()){
        if(map.containsKey(c)){
            stack.push(c);
        } else if(!stack.empty() && map.get(stack.peek())==c){
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.empty();
}

Ответ 28

package Stack;

import java.util.Stack;

public class BalancingParenthesis {

    boolean isBalanced(String s) {

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {

                stack.push(s.charAt(i)); // push to the stack

            }

            if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {

                if (stack.isEmpty()) {
                    return false; // return false as there is nothing to match
                }

                Character top = stack.peek(); // to get the top element in the stack

                if (top == '(' && s.charAt(i) == ')' || top == '{' && s.charAt(i) == '}'
                        || top == '[' && s.charAt(i) == ']') {

                    stack.pop();
                }

            }

        }

        if (stack.isEmpty()) {
            return true; // check if every symbol is matched
        }

        return false;
    }

    public static void main(String[] args) {

        BalancingParenthesis obj = new BalancingParenthesis();

        System.out.println(obj.isBalanced("()[]{}[][]"));

    }

}

// Time Complexity : O(n)

Ответ 29

**// balanced parentheses problem (By fabboys)**
#include <iostream>
#include <string.h>

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