Дужкі/Кранштэйны Matching з выкарыстаннем алгарытму Stack

Напрыклад, калі дужка/кранштэйны спалучаныя ў наступным:

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

і гэтак далей, але калі круглыя ​​дужкі/квадратныя дужкі, не адпавядае яна павінна вяртаць хлусня, напрыклад:

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

і гэтак далей. Ці можаце вы праверыць гэты код? Загадзя дзякую.

public static boolean isParenthesisMatch(String str) {
    Stack stack = new Stack();

    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)); 
}
23
Вы кажаце, «круглыя ​​дужкі», але вы таксама, здаецца, хочуць, каб праверыць дужкі ...
дададзена аўтар fge, крыніца
Фокус у тым, каб падтрымліваць стэк, дзе кожны ўзровень адпавядае брекет і захоўвае тып кранштэйна.
дададзена аўтар Yves Daoust, крыніца
што такое асаблівы Java тут?
дададзена аўтар SMA, крыніца
Выдаліць тэг Java, як гэта не мае нічога агульнага з Java. У Вас няма устаўленага кода, кажучы я stucked тут і г.д.
дададзена аўтар SMA, крыніца
Пытанне. Ці з'яўляецца [{]} сапраўднае адпаведнасць?
дададзена аўтар Kevin, крыніца
@yvesdaoust en.wikipedia.org/wiki/Bracket_%28mathematics%29 даказвае мой пункт дакладна - у залежнасці ад таго, якія сітуацыі дужкі выкарыстоўваюцца, яны, магчыма, павінны быць разабраны як розныя тыпы, або разам, або без адпаведнай планкі
дададзена аўтар Aify, крыніца
Ці вы маглі б напісаць рэальны аналізатар замест злоўжываючы рэгулярныя выразы.
дададзена аўтар cpburnz, крыніца
Без спецыфікацыі мовы (гэта значыць дакладны адказ на пытанне «згодна з якім правілы выразы, якія вы хочаце, каб разабраць фарміруецца»), мы не можам адказаць на гэтае пытанне. Ці з'яўляюцца яны кантэкстна свабодны мову? Яны, безумоўна, не з'яўляюцца рэгулярнымі з-за адны дужкі. Ці з'яўляюцца яны кантэкстна-залежная? Т'юрынг-поўны? Нягледзячы на ​​ўсё, што гэтае пытанне павінен быць на CS.SE
дададзена аўтар G. Bach, крыніца
Мова праграмавання не мае значэння, мова разбірайцеся ёсць. Адпаведнае пытанне «што ўяўляе сабой матэматычнае выраз?»
дададзена аўтар G. Bach, крыніца
@aify няма нічога па тэме тут, можа быць, за выключэннем вашых каментароў. Такое пытанне цалкам адносіцца да катэгорыі алгарытму. Ваш матэрыял аб інтэрвалах гэта тое, што не па тэме, пад гэтым пытаннем, як гэта ясна кажа аб матэматычным выразе.
дададзена аўтар shasan, крыніца
Проста цікавы тэст сцэнар: "(((()) {))}" Шоўду вяртаюць ілжывыя
дададзена аўтар Vitor Braga, крыніца
@Aify Мой кантэкст адпаведнасці (), {} і [] і нічога на самай справе не мае значэння. Калі закрыццё тыпу варта пасля адкрыцця аднаго і таго ж тыпу, то яго добра! Гэта ўсё, што мне трэба.
дададзена аўтар user4275686, крыніца
@Kevin Не ... памылка ў 3
дададзена аўтар user4275686, крыніца
Я раблю гэта ў Java, так што я падумаў, што можа быць нейкі канкрэтны савет (ы).
дададзена аўтар user4275686, крыніца
@Aify любых спасылак на шырокі «пытанне» вы згадалі?
дададзена аўтар user4275686, крыніца
@Aify Гэта алгарытмічная ідэя, якую я круціўся вакол с. Што тэгаў вы маглі б прапанаваць тады?
дададзена аўтар user4275686, крыніца
@ G.Bach трохбаковы матэматычнага выразы: чысла, зменныя, аператары (+ - * /) і хай круглыя ​​дужкі, каб змяніць старшынствы ацэнкі.
дададзена аўтар user4275686, крыніца
@G. Бах Сінтаксічны мова будзе Java, разабрана мовай з'яўляецца матэматычным выразам.
дададзена аўтар user4275686, крыніца
Таксама гэта неабходна для рэалізацыі яго стэк? што ідэя рабіць гэта проста з масівамі?
дададзена аўтар user4275686, крыніца
@Aify Не, мне трэба ведаць, што я які ахоплівае ўсе выпадкі. Ці можа быць якой-небудзь іншы выпадак (ы)?
дададзена аўтар user4275686, крыніца

21 адказы

Ваш код мае некаторую блытаніну ў яго звароце з «{» і «}» знакаў. Яна павінна быць цалкам паралельна, як вы спраўляецеся «(» і «)».

Гэты код, злёгку зменены ад вашага, здаецца, працуе правільна:

public static boolean isParenthesisMatch(String str) {
    if (str.charAt(0) == '{')
        return false;

    Stack stack = new Stack();

    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();
}
44
дададзена
Затым дадайце гэтую праверку перад цыклам. Я буду рэдагаваць яго.
дададзена аўтар Don Roby, крыніца
дзякуй, вельмі ясны алгарытм :)
дададзена аўтар butterywombat, крыніца
Ці будзе гэта працаваць на ўвесь файл або толькі для аднаго радка? Хай ( ў 1-й лініі, але ) знаходзіцца ў 2-м радку файла. Ці можна праверыць у гэтым выпадку?
дададзена аўтар Sigur, крыніца
дзякуй, але праблема заключаецца {{} або нават {()}, {}() павінна вяртаць хлусня. Іншымі словамі, першы з == {павінна быць ілжывым.
дададзена аўтар Shuvo0o, крыніца
Ідэальна падыходзіць. Дзякуй!
дададзена аўтар Shuvo0o, крыніца

Гэты код лягчэй зразумець:

public static boolean CheckParentesis(String str)
{
    if (str.isEmpty())
        return true;

    Stack stack = new Stack();
    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();
}
33
дададзена
дзякуй. досыць лёгка
дададзена аўтар Abhijit Gaikwad, крыніца
І гэта працуе. Дзякуючы.
дададзена аўтар james.garriss, крыніца
Вялікі код, хоць гэта можа быць трохі палепшана шляхам даданняў працягваюць заяву пасля націску бягучага сімвала ў стэк.
дададзена аўтар JSextonn, крыніца
Дзякуючы я ператварыў код C ++
дададзена аўтар Aminos, крыніца

алгарытм:

  1. сканаваць радок, штурхаючы ў стэк для кожнага «(» знойдзена ў радку
  2. <�Літый>, калі сімвал «)» адсканаваныя, поп-адзін «(» з стэка </літый>

Цяпер, круглыя ​​дужкі збалансаваны для двух умоў:

  • «(» можа быць з стэка для кожнага «)» знойдзена ў радку, і
  • <�Літый> стэк пусты ў канцы (калі ўся радок апрацоўваецца)
6
дададзена
Нават калі дадаць ўмовы «{» і «}» для гэтага алгарытму, ён не адносіцца да - {(}) . Мы павінны праверыць, калі пасля кожнага LAST кранштэйне/дужкай, якая адкрываецца, у SAME неабходна закрыць.
дададзена аўтар Swanidhi, крыніца
public static boolean isValidExpression(String expression) {
    Map openClosePair = new HashMap();
    openClosePair.put(')', '(');
    openClosePair.put('}', '{');
    openClosePair.put(']', '[');        
    Stack stack = new Stack();
    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();
}
4
дададзена
<�Код> openClosePair.values ​​(). Змяшчае (ч) быць заменены openClosePair.containsValue (ч)
дададзена аўтар Tim, крыніца
Чаму OP павінны выкарыстоўваць код? Не маглі б вы пашырыць свой адказ з тлумачэннем?
дададзена аўтар Zippy, крыніца
ваша апошняя пара ў адваротным кірунку зменіцца ( «]», «[»)
дададзена аўтар JesseBoyd, крыніца
і вы павінны праверыць, калі стэк пусты, калі (stack.empty() || stack.pop() = openClosedPair.get (ч)!) {вярнуцца ілжывым; }
дададзена аўтар JesseBoyd, крыніца
Яна вяртае вынік адразу пасля таго, як знайшоў незаконнае закрыццё. Выкарыстоўвае карту, якая стажор выкарыстоўвае метад хэшавання і хутчэй. Колькасць ліній менш і лёгка зразумець.
дададзена аўтар ganesan dharmalingam, крыніца
дзякуючы @JesseBoyd ў цяперашні час змянілася
дададзена аўтар ganesan dharmalingam, крыніца

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

  1. ітэрацыі па зададзенай паслядоўнасці. Пачніце з пустым стэкам.

  2. Калі бягучы сімвал з'яўляецца якая адкрывае дужкай, проста ўстаўце яго ў стэк.

  3. <�Літый> <�р> Калі гэта якая зачыняе дужка, пераканайцеся, што стэк не пуста, і верхні элемент кроку з'яўляецца прыдатнай якая адкрывае дужкай (гэта значыць, адпавядае гэтаму адзін). Калі няма, паведаміць пра памылку. У адваротным выпадку, поп верхні элемент з стэка. </Р>
  4. У рэшце рэшт, паслядоўнасць з'яўляецца правільным тады і толькі тады стэк пусты.

Чаму гэта правільна? Вось схема доказы: калі гэты алгарытм паведаміў, што паслядоўнасць выпраўляюцца, ён знайшоў прыдатную пару усіх дужак. Такім чынам, паслядоўнасць сапраўды дакладна па азначэнні. Калі ён паведаміў пра памылку:

  1. Калі стэк ня пусты, у рэшце рэшт, баланс адкрыцця і закрыцця дужкі не роўная нулю. Такім чынам, гэта не правільная паслядоўнасць.

  2. Калі стэк быў пусты, калі мы павінны былі выскачыць элемент, баланс зноў.

  3. Калі быў няправільны элемент на вяршыні стэка, пару «няправільных» дужкі павінны адпавядаць адзін аднаму. Гэта азначае, што паслядоўнасць не з'яўляецца правільным.

Я паказаў, што:

  • Калі алгарытм паведаміў, што паслядоўнасць з'яўляецца правільным, гэта правільна.

  • Калі алгарытм паведамілі, што паслядоўнасць не з'яўляецца правільнай, гэта няправільна (звярніце ўвагу, што я не выкарыстоўваю той факт, што няма ніякіх іншых выпадкаў, акрамя тых, якія пазначаны ў вашым пытанні). </Р>

Гэтыя дзве кропкі азначаюць, што гэты алгарытм працуе для ўсіх магчымых уваходаў.

3
дададзена
Heads-Up: Ваш адказ быў аб'яднаны тут з stackoverflow.com/questions/29396477/… - калі ласка, карэктаваць па меры неабходнасці.
дададзена аўтар Shog9, крыніца
Праблема не ў тым, правільна ўкладзенасці дужак у адзіночку.
дададзена аўтар G. Bach, крыніца
дададзена аўтар Sanket, крыніца
public static boolean isBalanced(String s) {
    Map openClosePair = new HashMap();
    openClosePair.put('(', ')');
    openClosePair.put('{', '}');
    openClosePair.put('[', ']'); 

    Stack stack = new Stack();
    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();
}
2
дададзена

Algorithm is:

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

<�Моцны> Выснова:

--Bracket checker--

радок збалансаваны

1
дададзена

Адказ Ганесан ў вышэй не з'яўляецца правільным і StackOverflow не даючы мне каментары ці змяніць свой пост. Так ніжэй правільны адказ. Ganesan мае няправільную абліцоўванне «[» і прапускае праверку стэка IsEmpty ().

Ніжэй код вяртае ісціну, калі брекеты правільна адпаведнасць.

public static boolean isValidExpression(String expression) {
    Map openClosePair = new HashMap();
    openClosePair.put(')', '(');
    openClosePair.put('}', '{');
    openClosePair.put(']', '[');

    Stack stack = new Stack();
    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
дададзена
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 stk =  new Stack();
            for(int i=0;i
1
дададзена
import java.util.*;

class StackDemo {

    public static void main(String[] argh) {
        boolean flag = true;
        String str = "(()){}()";
        int l = str.length();
        flag = true;
        Stack st = new Stack();
        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");
    }
}
1
дададзена
У той час як гэты фрагмент кода можа вырашыць пытанне, уключаючы тлумачэнне сапраўды дапамагае палепшыць якасць вашага паста. Памятаеце, што вы адказваеце на пытанне, для чытачоў у будучыні, і гэтыя людзі могуць не ведаць прычыны вашага кода прапановы.
дададзена аўтар Tony Babarino, крыніца
import java.util.*;

public class MatchBrackets {

    public static void main(String[] argh) {
        String input = "[]{[]()}";
        System.out.println  (input);

        char [] openChars =  {'[','{','('};
        char [] closeChars = {']','}',')'};

        Stack stack = new Stack();

        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");
    }
}
1
дададзена
public static bool IsBalanced(string input)
    {
        Dictionary bracketPairs = new Dictionary() {
        { '(', ')' },
        { '{', '}' },
        { '[', ']' },
        { '<', '>' }
    };

        Stack brackets = new Stack();

        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
дададзена

Калі вы хочаце зірнуць на мой код. Проста для даведкі

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 exprStack = new Stack();

        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);
        }
    }
}
0
дададзена

Я бачыў адказы тут і амаль ўсё зрабілі добра. Тым не менш, я напісаў сваю ўласную версію, якая выкарыстоўвае слоўнік для кіравання парай дужак і стэк кантраляваць парадак выяўленых дужак. Я таксама напісаў блог паведамленне для гэтага.

Вось мой клас

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();
        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 BuildBracketMap()
    {
        return new Dictionary()
        {
            {'[', ']'},
            {'(', ')'},
            {'{', '}'}
        };
    }
}
0
дададзена

Я паспрабаваў гэта з дапамогай 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)}`));
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."))
0
дададзена
//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);
        }
    }
}
0
дададзена
Гэта цалкам адрозніваецца ад кода, размешчаным ОП. Было б вельмі карысна для іншых, калі вы маглі б растлумачыць гэта крыху, каб мы маглі ўбачыць, што ваш ход думкі.
дададзена аўтар Wai Ha Lee, крыніца
Акрамя таго, гэта занадта доўга. Вы таксама павінны ўстрымлівацца як мага больш друкаваць знутры метадаў.
дададзена аўтар Amos Bordowitz, крыніца
import java.util.Stack;

class Demo
{

    char c;

    public  boolean checkParan(String word)
    {
        Stack sta = new Stack();
        for(int i=0;i

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





    }

}
0
дададзена
public String checkString(String value) {
    Stack 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";
}
0
дададзена

Было прапанавана рэалізаваць гэты алгарытм ў прамым кадаванні інтэрв'ю, вось мой рэфактарынгу рашэнне ў C #:

Git Tests

0
дададзена
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 buffer = new Stack();
            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;
}

}
0
дададзена