글이나 수학식을 표현하기위해 괄호 (ex. { , [, ( ) 등을 많이 사용한다.
보통 열린 괄호가 ( 가 있으면 순서에 맞게 닫힌 괄호가 있어야 하는데 이것을 우리는 균형잡힌 괄호(balanced parentheses )라고 얘기한다.
즉 [()]{}{[()()]()} 표현식은 열린, 닫힌 괄호들이 균형잡힌 형태로 표현된것이고
[(]) 는 두번째 ( 다음에 닫힌 괄호 ) 가 없기 때문에 균형잡힌 형태라고 볼 수 없다.
Examples of balanced expression
- (())
- {(([]))}
- {{}}[]
- [](){}
- {{}}{}()[]
Examples of unbalanced expression
- {()
- [][])
- }}}}
- ((()
- [{](){}
그럼 표현식 E 가 주어지고 그 표현식이 균형이 잡혀 있는지 어떻게 확인할수 있을까?
표현식의 유효성을 체크하기위한 방법으로 스택을 사용하면 된다.
알고리즘을 자세히 살펴보기 전에 먼저 열린 괄호와 닫힌 괄호들의 종류를 다음과 같이 정의하겠다.
Opening Brackets:
- {
- (
- [
Closing Brackets:
- }
- )
- ]
그리고 검사할 표현식은 그림 1과 같다.
열린 괄호 ( ex. (, { . [ ) 가 나오면 무조건 스택에 push 해준다. 예제에서 처음 문자는 ( 이므로 현재 스택에 ( 가 들어가 있다.
마찬가지로 2, 3번째도 모두 열린 괄호 { { 이기 때문에 스택에 넣는다. 스택사이즈는 3이 된다.
이제 4번째 부터 닫힌 괄호 } 가 나오는데 닫힌 괄호들이 나오면 스택의 맨 상단에 있는게 닫힌 괄호와 매칭 ( (), {}, [] )이 되는것인지 확인하고 매칭이 된다면 스택에서 pop 을 해준다. 만약 이때 서로 매칭이 안된다면 균형 잡힌(정상적인 or 유요한) 괄호 표현식이라고 볼수 없게 되는것이다.
스택상단에 열린 괄호 { 게 있으니 닫힌 괄호 } 와 매칭이 되기 때문에 스택에서 pop 하면 된는 것이다.
마찬가지로 5번째도 닫힌 괄호 } 이고 스택상단에 열린 괄호 { 와 매칭되므로 스택에서 pop 한다.
6번째도 닫힌 괄로 ) 이고 현재 스택 상단에 열린괄호 ( 와 매칭되므로 스택에서 pop 한다. 그럼 지금까지 스택은 빈상태로 남는다.
이런식으로 나머지도 쭉 비교하다가 매칭되지 않으면 invalid 한 것이고 균형잡힌 괄호 표현식이라면 최종적으로 스택은 빈상태(empty)가 되어야 한다.
다음은 위 알고리즘을 코드로 구현한 것이다.
단, () 괄호에 대해서만 작성하였다.
|
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
|
/**
* 문자열이 올바른 괄호 문자열인지 체크한다.
*
* */
public static boolean checkValidBrackets(String p) {
Stack<Character> s = new Stack<>();
int length = p.length();
for(int i = 0 ; i < length ; i++) {
char c = p.charAt(i);
if(c == '(') {
s.push(c);
}
else if( c == ')'){
if(s.empty())
return false;
else if(s.peek() == '(') {
s.pop();
}
else
return false;
}
}
return s.empty();
}
Colored by Color Scripter
|
레퍼런스
- Balanced Brackets Problem - Application of Stack
- HackerRank - Stacks : Balanced Brackets
- Check for balanced parentheses in an expression