-
Notifications
You must be signed in to change notification settings - Fork 14
/
BracketsExpressionValidator.java
58 lines (52 loc) · 2.11 KB
/
BracketsExpressionValidator.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
package by.andd3dfx.common;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
import java.util.Set;
/**
* <pre>
* <a href="https://leetcode.com/problems/valid-parentheses/description/">Task description</a>
*
* Есть скобочное выражение с разными видами скобок: {}, (), [], <>.
* Проверить, что оно правильное.
* Других символов, кроме скобок, быть не может.
*
* ([{}]) -> true
* ([)] -> false
* </pre>
*
* @see <a href="https://youtu.be/4kimh-Gsuxs">Video solution</a>
*/
public class BracketsExpressionValidator {
private static final Set<Character> CLOSING_BRACKETS = Set.of('}', ')', ']', '>');
private static final Map<Character, Character> CLOSING_2_OPENING_BRACKET_MAP = Map.of(
')', '(',
'}', '{',
']', '[',
'>', '<'
);
/**
* Проходим по массиву символов, складываем их в стек.
* Когда находим закрывающую скобку - проверяем, есть ли вверху стека парная к ней открывающая.
* Если нет - выражение ошибочно. Если есть - продолжаем обход.
* После обхода, если стек пустой - валидация прошла успешно.
*/
public static boolean validate(String expression) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : expression.toCharArray()) {
if (CLOSING_BRACKETS.contains(ch)) {
if (stack.isEmpty()) {
return false;
}
var expectedOpeningBracket = CLOSING_2_OPENING_BRACKET_MAP.get(ch);
if (stack.peek() != expectedOpeningBracket) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}