Подтвердить что ты не робот

Скобки для скобок/скобки с использованием алгоритма Stack

Например, если скобки/скобки соответствуют следующему:

({})
(()){}()
()

и т.д., но если скобки/скобки не совпадают, он должен возвращать значение false, например:

{}
({}(
){})
(()

и т.д. Вы можете проверить этот код? Спасибо заранее.

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)); 
}
4b9b3361

ОТВЕТЫ

Ответ 1

В вашем коде есть некоторая путаница в обработке символов '{' и '}'. Он должен быть полностью параллелен тому, как вы обрабатываете '(' и ')'.

Этот код, слегка измененный от вашего, кажется, работает правильно:

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

Ответ 2

Этот код проще понять:

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

Ответ 3

Алгоритм:

  • сканировать строку, нажав на стек для каждого '(' найдено в строке
  • if char ')' отсканированный, поп один '(' из стека

Теперь скобки сбалансированы для двух условий:

  • '(' можно вытащить из стека для каждого ')', найденного в строке, и
  • стек пуст в конце (когда обрабатывается вся строка)

Ответ 4

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

Ответ 5

Собственно, нет необходимости проверять случаи "вручную". Вы можете просто запустить следующий алгоритм:

  • Итерации по данной последовательности. Начните с пустого стека.

  • Если текущий char является открывающей скобкой, просто вставьте его в стек.

  • Если это закрывающая скобка, убедитесь, что стек не пуст, а верхний элемент этого шага - подходящая открывающая скобка (она соответствует этому). Если это не так, сообщите об ошибке. В противном случае вытащите верхний элемент из стека.

  • В конце концов, последовательность правильная, если стек пуст.

Почему это правильно? Вот эскиз доказательства: если этот алгоритм сообщил, что последовательность исправлена, она обнаружила совпадающую пару всех скобок. Таким образом, последовательность действительно правильна по определению. Если он сообщил об ошибке:

  • Если стек не был пуст в конце, баланс открывающих и закрывающих скобок не равен нулю. Таким образом, это не правильная последовательность.

  • Если стек был пуст, когда нам нужно было поместить элемент, баланс снова выключается.

  • Если на вершине стека был неправильный элемент, пара "неправильных" скобок должна соответствовать друг другу. Это означает, что последовательность неверна.

Я показал, что:

  • Если алгоритм сообщил, что последовательность верна, это правильно.

  • Если алгоритм сообщил, что последовательность неверна, это неверно (обратите внимание, что я не использую тот факт, что нет других случаев, кроме тех, которые указаны в вашем вопросе).

Эти две точки означают, что этот алгоритм работает для всех возможных входов.

Ответ 6

Алгоритм:

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.

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

Вывод:

- Проверка брекетинга -

Строка сбалансирована

Ответ 7

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

Ответ 8

Ответ Ganesan выше неверен, и StackOverflow не позволяет мне комментировать или редактировать его сообщение. Итак, ниже приведен правильный ответ. Ganesan имеет неправильную обратную сторону "[" и отсутствует проверка стека isEmpty().

Приведенный ниже код вернет true, если скобки правильно совпадают.

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

Ответ 9

Оптимизированная реализация с использованием операторов Stacks и Switch:

public class JavaStack {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

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

    while (sc.hasNext()) {
        String input = sc.next();

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            switch (c) {

                case '(':
                    s.push(c); break;
                case '[':
                    s.push(c); break;
                case '{':
                    s.push(c); break;
                case ')':
                    if (!s.isEmpty() && s.peek().equals('(')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;
                case ']':
                    if (!s.isEmpty() && s.peek().equals('[')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;
                case '}':
                    if (!s.isEmpty() && s.peek().equals('{')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;

                default:
                    s.push('x'); break;

            }

        }
        if (s.empty()) {
            System.out.println("true");
        } else {
            System.out.println("false");
            s.clear();
        }
    }
} }

Ура!

Ответ 10

Вы делаете некоторые дополнительные проверки, которые не нужны. Не вносит изменений в функциональность, но более чистый способ написания вашего кода:

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 == '(' || c == '{')
            stack.push(c);
        else if (stack.empty())
            return false;
        else if (c == ')') {
            if (stack.pop() != '(')
                return false;
        } else if (c == '}') {
            if (stack.pop() != '{')
                return false;
        }
    }
    return stack.empty();
}

Нет причин заглядывать в парантез, прежде чем удалять его из стека. Я также рассмотрел бы оборачивание блоков инструкций в паратезы для улучшения читабельности.

Ответ 11

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

Ответ 12

Я видел ответы здесь, и почти все хорошо. Тем не менее, я написал свою собственную версию, которая использует словарь для управления парными скобками и стекю для контроля порядка обнаруженных фигурных скобок. Я также написал блог post для этого.

Вот мой класс

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>()
        {
            {'[', ']'},
            {'(', ')'},
            {'{', '}'}
        };
    }
}

Ответ 13

Я думаю, что это лучший ответ:

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

Ответ 14

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

Ответ 15

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





    }

}

Ответ 16

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



    }

}

Ответ 17

Я попробовал это, используя javascript ниже, это результат.

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

Ответ 18

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

Ответ 19

Если вы хотите посмотреть мой код. Только для справки

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

Ответ 20

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

Ответ 21

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

Ответ 22

Здесь решение в 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."))

Ответ 23

Меня попросили реализовать этот алгоритм на собеседовании по программированию, вот мое реорганизованное решение в С#:

Git Tests

Ответ 24

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

}

Ответ 25

в Java вы не хотите сравнивать строку или символ по знакам ==. Вы бы использовали метод равных. equalsIgnoreCase или что-то в этом роде. если вы используете ==, он должен указывать на ту же область памяти. В методе ниже я попытался использовать целые, чтобы обойти это. здесь используются целые числа из индекса строки, поскольку каждая открывающая скобка имеет закрывающую скобку. Я хотел использовать сопоставление местоположения вместо сопоставления сопоставления. Но я думаю, что с этим вы должны быть преднамеренным в том, где вы размещаете символы строки. Также давайте посмотрим, что Да = верно и Нет = ложно для простоты. В этом ответе предполагается, что вы передали массив строк для проверки, и вам необходим массив, если да (они совпадают) или Нет (нет)

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

Ответ 26

  Check balanced parenthesis or brackets with stack-- 
  var excp = "{{()}[{a+b+b}][{(c+d){}}][]}";
   var stk = [];   
   function bracket_balance(){
      for(var i=0;i<excp.length;i++){
          if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
             stk.push(excp[i]);
          }else if(excp[i]== ']' && stk.pop() != '['){
             return false;
          }else if(excp[i]== '}' && stk.pop() != '{'){

            return false;
          }else if(excp[i]== ')' && stk.pop() != '('){

            return false;
          }
      }

      return true;
   }

  console.log(bracket_balance());
  //Parenthesis are balance then return true else false

Ответ 27

Программа согласования скобок без использования стека

Здесь я использовал строку для замены реализаций стека, таких как операции push и pop.

'пакет java_prac; импорт java.util. *; открытый класс BracketsChecker {

    public static void main(String[] args) {
        System.out.println("- - - Brackets Checker [ without stack ] - - -\n\n");
        Scanner scan=new Scanner(System.in);
        System.out.print("Input : " );
        String s = scan.nextLine();
        scan.close();
        System.out.println("\n...working...\n");
        String o="([{";
        String c=")]}";
        String x=" ";
        int check =0;
        for (int i = 0; i < s.length(); i++) {
            if(o.contains(String.valueOf(s.charAt(i)))){
                x+=s.charAt(i);     
                 //System.out.println("In : "+x); // stack in
            }else if(c.contains(String.valueOf(s.charAt(i)))) { 
                char temp = s.charAt(i);
                if(temp==')') temp = '(';
                if(temp=='}') temp = '{';
                if(temp==']') temp = '[';
                if(x.charAt(x.length()-1)==temp) {
                    x=" "+x.substring(1,x.length()-1);
                    //System.out.println("Out : "+x);   // stack out
            }else {
            check=1;    
            }
            }
    }   
        if(x.length()==1 && check==0 ) {
            System.out.println("\n\nCompilation Success \n\n© github.com/sharanstark 2k19");
        }else {
            System.out.println("\n\nCompilation Error \n\n© github.com/sharanstark 2k19" );
        }
    }
}'