* 수식의 괄호 검사 (괄호 쌍 검사)
- 수식은 일반적으로 연산자(operator)와 피연산자(operand)로 구성되어 있고, 왼쪽에서 오른쪽 순서로 처리한다.
- 수식에 사용한 연산자의 우선순위에 따라 높은 우선순위를 가진 연산자를 먼저 처리한다.
- 우선순위는 괄호를 사용하여 표시하기도 한다 -> 일반괄호((,)), 중괄호({,}), 대괄호([,])
- 여러개의 괄호가 중첩된 경우 가장 안쪽의 괄호를 먼저 처리한다.
※ 지금 여기에서 해보려는 것은 수식의 괄호의 쌍을 확인하여, 수식이 올바르게 이루어져 있는가를 확인하려는 것이다.
글의 제목과 같이 '스택(Stack)' 을 활용하여 '스택(Stack)' 을 읽으면서
(1) 왼쪽 괄호를 만나면 스택에 push
(2) 오른쪽 괄호를 만나면 스택을 pop
if 현재 검사중인 괄호와 pop한 괄호의 종류가 같다면 OK!
else 현재 검사중인 괄호와 pop한 괄호의 종류가 다르다면 NO~
(3) 일이 모두 끝났을 때 스택이 공백 스택이 되면 모든 괄호가 올바르게 쌍으로 이루고 있는 것으로 수식은 올바르다고 말할 수 있다.
|
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 |
Formula.java
package Formula;
public class Formula {
private String exp;
private int expSize;
private char testCh, openPair;
public boolean testPair(String exp){
this.exp = exp;
LinkedStack stack = new LinkedStack();
expSize = this.exp.length();
for(int i=0; i<expSize; i++){
testCh = exp.charAt(i);
switch(testCh){
case '(' :
case '[' :
case '{' :
stack.push(testCh);
break;
case ')' :
case ']' :
case '}' :
if(stack.isEmpty()){
return false;
}else{
openPair = stack.pop();
if((openPair==')') && (testCh!='(') ||
(openPair==']') && (testCh!='[') ||
(openPair=='}') && (testCh!='{')){
return false;
}else{
break;
}
}
}
}
if(stack.isEmpty()){
return true;
}else{
return false;
}
}
} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
Test.java
package Formula;
public class Test {
public static void main(String[] args) {
Formula op = new Formula();
String exp = "{(A+B)-3}*5+[{cos(x+y)+7}-1]*4";
char postfix[];
int value;
System.out.println(exp);
if(op.testPair(exp)){
System.out.println("수식이 올바름(괄호의 쌍이 일치)");
}else{
System.out.println("수식이 올바르지 않음(괄호의 쌍이 불일치)");
}
}
} |
Stack 인터페이스, LinkedStack, StackNode, Fromula, Test 총 다섯개의 클래스 파일이 필요하다.
Stack 인터페이스, LinkedStack, StackNode 3개는 이전 포스팅 중 스택의 연결리스트 구현 부분에서 이미 설명했기 때문에 재사용하였고,
Formula, Test 두개의 클래스만 작성해보았다.
[첨부파일]
Formula.java'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 큐 (Queue) - 선형큐, 원형큐 순차 자료구조 방식 구현 (0) | 2015.11.03 |
|---|---|
| [자료구조/java] 수식의 표기법 - Stack 사용 (1) | 2015.11.02 |
| [자료구조/java] 스택의 응용 - 역순 문자열 만들기 (0) | 2015.10.31 |
| [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 (0) | 2015.10.31 |
| [자료구조/java] 다항식의 연결 자료구조 표현 (0) | 2015.10.30 |
