Java String S = & ldquo; {({)}} & rdquo; [Дубликат]

Я видел ответы здесь, и почти все хорошо. Тем не менее, я написал свою собственную версию, которая использует словарь для управления парными скобками и стекю для контроля порядка обнаруженных фигурных скобок. Я также написал для этого блог 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>()
        {
            {'[', ']'},
            {'(', ')'},
            {'{', '}'}
        };
    }
}

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

Просили реализовать этот алгоритм в интервью с живым кодированием, вот мое реорганизованное решение в C #:

Git Тесты

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

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





    }

}

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



    }

}

Ответ 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();
}

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

1. Итерации по данной последовательности. Начните с пустого стека.
2. Если текущий символ является открывающей скобкой, просто нажмите его в стек.
3. Если это закрывающая скобка, убедитесь, что стек не пуст и верхним элементом шага является подходящая открывающая скобка (она соответствует этому). Если это не так, сообщите об ошибке. В противном случае вытащите верхний элемент из стека.
4. В конце концов последовательность правильная, если стек пуст.

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

1. Если в конце стека не было пустым, баланс открытия и закрытия скобок не равен нулю. Таким образом, это не правильная последовательность.
2. Если стек был пуст, когда нам нужно было поместить элемент, баланс снова выключился.
3. Если на верхнем месте был неправильный элемент пачки «неправильных» скобок должны соответствовать друг другу. Это означает, что последовательность неверна.

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

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

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

Алгоритм:

1. сканирует строку, нажав на стек для каждого '(' найден в строке
2. , если char ')' scanned, pop one ' ('из стека

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

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

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

Алгоритм:

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

Выход:

- Контроллер брекетинга -

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

Этот код легче понять:

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

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

Вот решение в 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."))

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

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

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

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

Я попробовал это, используя приведенный ниже 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)}`));