Правильная скобочная последовательность

@GG_one123 · Регистрация: 15.03.2020

Студворк — интернет-сервис помощи студентам

Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.

Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

Входные данные
В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

Выходные данные
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Пример

Входные данные
()[]

Выходные данные
yes

@Catstail · 16.03.2020, 19:34

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Stack;
import java.util.Scanner;
 
public class JavaApplication6 {
 
    public static void main(String[] args) {
      Stack<Integer> st = new Stack<>();
      Scanner inp = new Scanner(System.in);
      System.out.print("cmd=");
      String cmd = inp.nextLine();
      char a;
      int i,k;
      boolean flag=true;
      for (i=0; i<cmd.length(); i++)
      {
          a=cmd.charAt(i);
          switch (a)
          {
              case '(':
                st.push(1);
                break;
              case '[':
                st.push(2);
                break;
              case '{':
                st.push(3);
                break;
              case ')':
                if (st.empty())
                {
                   flag=false;
                   break;
                }
                k=st.peek();
                st.pop();
                if (k!=1) flag=false;
                break;
              case ']':
                if (st.empty())
                {
                   flag=false;
                   break;
                }
                k=st.peek();
                st.pop();
                if (k!=2) flag=false;
                break;
              case '}':
                if (st.empty())
                {
                   flag=false;
                   break;
                }
                k=st.peek();
                st.pop();
                if (k!=3) flag=false;
                break;
              default:  
          }
          if (! flag) break;
      }
      
      if (flag && st.empty())
          System.out.println("OK");
      else
          System.out.println("Error");
    }
}

@korvin_ · 16.03.2020, 22:44

Catstail, что-то ты перемудрил.

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

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.LinkedList;
 
final class Brackets {
 
    static boolean areBalanced(String s) {
        final var stack = new LinkedList<Character>();
        final var n = s.length();
        for (var i = 0; i < n; i++) {
            final var ch = s.charAt(i);
            switch (ch) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                case ')':
                case ']':
                case '}':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    final char top = stack.pop();
                    if (top != ch) {
                        return false;
                    }
            }
        }
        return stack.isEmpty();
    }
}

@Catstail · 17.03.2020, 11:22

korvin_, а так:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main
{
    public static boolean check(String cmd)
    {
        int len_p,len_c;
        String tmp=cmd.replaceAll("[^()\\[\\]{}]","");
        while(true)
        {
            len_p=tmp.length();
            tmp=tmp.replaceAll("\\(\\)","");
            tmp=tmp.replaceAll("\\[\\]","");
            tmp=tmp.replaceAll("\\{\\}","");
            len_c=tmp.length();
            if (len_p==len_c) break;
        }
        return (len_c==0);
    }   
    public static void main (String[] args) 
    {
        System.out.println(check("(a[b]){a(a)a}"));
    }
}

@korvin_ · 17.03.2020, 12:20

Сообщение от Catstail

а так

не эффективно.

Добавлено через 23 минуты
Catstail, вот крайне примитивный бенч:

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

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.LinkedList;
 
final class Brackets {
 
    public static boolean check(String cmd) {
        int len_p, len_c;
        String tmp = cmd.replaceAll("[^()\\[\\]{}]", "");
        do {
            len_p = tmp.length();
            tmp = tmp.replaceAll("\\(\\)", "");
            tmp = tmp.replaceAll("\\[\\]", "");
            tmp = tmp.replaceAll("\\{\\}", "");
            len_c = tmp.length();
        } while (len_p != len_c);
        return (len_c == 0);
    }
 
    static boolean areBalanced(String s) {
        final var stack = new LinkedList<Character>();
        final var n = s.length();
        for (var i = 0; i < n; i++) {
            final var ch = s.charAt(i);
            switch (ch) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                case ')':
                case ']':
                case '}':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    final char top = stack.pop();
                    if (top != ch) {
                        return false;
                    }
            }
        }
        return stack.isEmpty();
    }
 
    private static final String BRACKETS = "()[]{}";
 
    private static long REGEX_MILLIS = 0L;
    private static long RAW_MILLIS = 0L;
 
    private static void generateCheck(int n) {
        REGEX_MILLIS = 0L;
        RAW_MILLIS = 0L;
        generateCheck("", n);
        System.out.printf("RAW:   %6.3fs%nREGEX: %6.3fs%n", RAW_MILLIS / 1000.0, REGEX_MILLIS / 1000.0);
    }
 
    private static void generateCheck(String s, int n) {
        if (n <= 0) {
            var start = System.currentTimeMillis();
            final var expected = areBalanced(s);
            var end = System.currentTimeMillis();
            RAW_MILLIS += end - start;
            start = System.currentTimeMillis();
            final var result = check(s);
            end = System.currentTimeMillis();
            REGEX_MILLIS += end - start;
            if (expected != result) {
                System.out.printf("FAIL: %s , expected = %s , result = %s%n", s, expected, result);
            }
        } else {
            for (var i = 0; i < BRACKETS.length(); i++) {
                generateCheck(s + BRACKETS.charAt(i), n - 1);
            }
        }
    }
 
    public static void main(String[] args) {
        for (var i = 6; i < 10; i++) {
            System.out.printf("FOR i = %d:%n", i);
            generateCheck(i);
            System.out.println();
        }
    }
}

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FOR i = 6:
RAW:    0.008s
REGEX:  0.184s
 
FOR i = 7:
RAW:    0.010s
REGEX:  0.443s
 
FOR i = 8:
RAW:    0.074s
REGEX:  2.221s
 
FOR i = 9:
RAW:    0.399s
REGEX: 13.948s

@Aviz__ · 17.03.2020, 14:04

GG_one123, без конкретизации вида скобок))

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Deque;
import java.util.LinkedList;
 
public class Helper {
 
    public static void main(String[] args) {
        System.out.println(isRightParenthSeq("<>{)"));
        System.out.println(isRightParenthSeq("<(>)"));
        System.out.println(isRightParenthSeq("<()>[]"));
        System.out.println(isRightParenthSeq("[]"));
    }
 
    private static boolean isRightParenthSeq(String strSrc) {
        Deque<Character> charDeque = new LinkedList<>();
        for (char tmpChar : strSrc.toCharArray()) {
            if (Character.isMirrored(tmpChar))
                if (Character.isMirrored(tmpChar + 2)) // значит левая
                    charDeque.addFirst(tmpChar);
                else charDeque.addLast(tmpChar);
        }
        if (charDeque.size() % 2 != 0) return false;
        for (int i = 0; i < charDeque.size() / 2; i++) {
            if ((charDeque.removeLast() - charDeque.removeFirst()) != 2) return false;
        }
        return true;
    }
}

резулт:
false
false
true
true

@Catstail · 17.03.2020, 15:40

korvin_, зато коротко.

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@GG_one123 -2 / 0 / 0 Регистрация: 15.03.2020 Сообщений: 5

	Правильная скобочная последовательность 15.03.2020, 13:45. Показов 11583. Ответов 6 Метки нет (Все метки) Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной. Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная. Входные данные В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок. Выходные данные Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no. Пример Входные данные ()[] Выходные данные yes 0

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,733 Записей в блоге: 14
	17.03.2020, 15:40
	korvin_, зато коротко. 0