* 수식의 표기법 - 전위, 후위, 중위
수식의 표기법은 연산자의 위치에 따라 전위, 후위, 중위 표기법으로 나누어지며,
각각의 표기법은 서로 다른 표기법으로 변환 시킬 수 있다.
컴퓨터 내부에서 수식을 처리하기에 가장 효율적인 방법은 후위 표기법이다.
그래서 컴퓨터 내부에서 효율적인 처리를 위해 스택을 사용하여 입력된 수식을 후위 표기법으로 변환하게 된다.
(1) 전위 표기법 (Prefix Notation) +AB
연산자를 앞에 표기하고 그 다음에 피연산자를 표기하는 방법
(2) 중위 표기법 (Infix Notation) A+B
연산자를 피연산자의 가운데에 표기하는 방법
(3) 후위 표기법 (Postfix Notation) AB+
연산자를 피연산자 뒤에 표기하는 방법
[중위 표기법의 전위 표기법 변환]
|
1. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 2. 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킨다. 3. 괄호를 제거한다. |
[중위 표기법의 후위 표기법 변환]
|
1. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 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 |
formula.java
public void toPostfix(String infix){
char testCh;
exp = infix;
int expSize = exp.length();
LinkedStack stack = new LinkedStack();
for(int i=0; i<expSize; i++){
testCh = exp.charAt(i);
switch(testCh){
case '0' :
case '1' :
case '2' :
case '3' :
case '4' :
case '5' :
case '6' :
case '7' :
case '8' :
case '9' :
System.out.print(testCh);
break;
case '+' :
case '-' :
case '/' :
case '*' :
stack.push(testCh);
break;
case ')' :
System.out.print(stack.pop());
break;
default:
}
}
while(!stack.isEmpty()){
System.out.print(stack.pop());
}
} |
이전에 스택을 이용한 수식 검사에서 구현했던 formula.java에 toPostfix() 메서드를 추가해줬다.
중위 표기법을 후위 표기법으로 변환하는데 필요한 구현 소스 코드들을 아래에 첨부했습니다.
중위 표기법의 후위 표기법 변환.zip
[후위 표기 수식의 연산]
컴퓨터 내부에서 후위 표기법의 수식을 연산할 때에도 스택을 사용할 수 있다.
(1) 피연산자를 만나면 스택에 삽입한다.
(2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop 하여 연산하고, 연산 결과를 다시 스택에 삽입한다.
(3) 수식이 끝나면, 마지막으로 스택을 pop 하여 출력한다.
|
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 |
Test.java
public class Test {
public static void main(String[] args) {
String postfix = "35*62/-";
evalPostfix(postfix);
}
public static void evalPostfix(String postfix){
char testCh = ' ';
int expSize = postfix.length();
int num1=0, num2=0;
LinkedStack stack = new LinkedStack();
for(int i=0; i<expSize; i++){
testCh = postfix.charAt(i);
if(testCh=='+' || testCh=='-' || testCh=='*' || testCh=='/'){
num2 = stack.pop();
num1 = stack.pop();
switch(testCh){
case '+' :
stack.push(num1+num2);
break;
case '-' :
stack.push(num1-num2);
break;
case '*' :
stack.push(num1*num2);
break;
case '/' :
stack.push(num1/num2);
break;
}
}else{
stack.push(testCh-'0');
}
}
System.out.println("결과값 : " + stack.pop());
}
} |
수식의 계산을 위해 이전에 링크드리스트로 구현했던 스택 노드의 데이터 타입을 char 에서 int로 바꾸어서 사용하였다.
후위 표기 수식의 연산을 구현하는데 필요한 소스 코드들을 아래에 첨부했습니다.
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 큐 (Queue) - 연결큐 연결 자료구조 방식 구현 (0) | 2015.11.04 |
|---|---|
| [자료구조/java] 큐 (Queue) - 선형큐, 원형큐 순차 자료구조 방식 구현 (0) | 2015.11.03 |
| [자료구조/java] 스택의 응용 - 수식의 괄호 검사 (java) (0) | 2015.10.31 |
| [자료구조/java] 스택의 응용 - 역순 문자열 만들기 (0) | 2015.10.31 |
| [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 (0) | 2015.10.31 |
