수식을 표현하는 방법에는 3가지가 있습니다.
Infix방법은 우리가 일반적으로 사용하는 방법입니다. 즉 연산자(operrator)가 중앙(in)에 들어가는 것이죠.
a+b, (a+b)*c, (a+b)*(c-d) 는 모두 infix 방식입니다.즉 연산자는 좌우에 있는 값을 가지고 연산을 하는 것이죠.
그러나 컴퓨터상에서 컴파일이나 인터프리터를 만들 때에는 이 방식이 불편합니다. 실제로 a/(b-c+d)*(e-a)*c와 같은 string을 읽어 들여 계산하는 프로로그램을 한번 만들어 보세요.
그래서 컴퓨터 엔지니어들이 만든 방식이 prefix와 postfix입니다.
postfix는 연산자를 뒤에 놓는 방법입니다.
즉, a+b를 postfix방식으로 나타내면 ab+가 됩니다.
즉 연산자 앞의 두값(a와 b)을 가지고 연산을 하면 됩니다.
(a+b)*c는 (ab+)c*가 됩니다. 즉 (ab+)와 c를 곱하기(*)하라는 이야기되지요.
prefix나 postfix에는 ()를 사용하지 않으므로 (ab+)c*는 ab+c*가 됩니다.
그러면, 왜 컴퓨터에서는 이 방식으로 표현하는 것이 계산하기 편한지 살펴봅시다.
수식 ab+c*에서
1. 첫번째 숫자 a를 읽어 stack에 넣읍니다. (그러면 stack에는 a가 있습니다.)
2. 두번째 숫자 b를 읽어 stack에 넣읍니다. (그러면 stack에는 a, b가 있습니다.)
3. 세번째 +(연산자)를 만나면 stack에서 가장 최근 값2개를 꺼내서 연산(+)합니다.
연산된 결과는 다시 stack에 넣읍니다 (그러면 stack에는 K가 있습니다. K=a+b)
4. 네번째 숫자 c를 만나면 stack에 넣읍니다. (그러면 stack에는 K, c가 있습니다.)
5. 다섯번째 *(연산자)를 만나면 stack에서 가장 최근 값2개를 꺼내서 연산(*)합니다.
연산된 결과는 다시 stack에 넣읍니다 (그러면 stack에는 X가 있습니다. X = K*c)
6. 수식에 더 이상 없으면 stack에서 숫자를 꺼냅니다. 이 것이 답입니다.
====> 요약하면, 앞에서 부터 차례대로 읽어 가면서, 숫자를 만나면 stack에 넣고,
연산자를 만나면 stcack에 넣은 가장 최근 값 2개를 연산하여 다시 stack에 넣으면 됩니다.
a/(b+c)를 postfix로 표기하면, a(bc+)*가 되고 괄호를 없애면 abc+*가 됩니다.
첫번째 값을 읽어보면 a가 되고...(한번 차례대로 해보세요.)
a/(b-c+d)*(e-a)*c를 postfix방식으로 바꾸어 봅시다.
(1) 식을 모두 괄호로 묶는다.
수식 모두에 계산하는 순서대로 괄호를 넣으면 ((a/((b-c)+d))*(e-a))*c)됩니다. 즉 가장 안에 있는 괄호부터 하나씩 계산하면 되도록 괄호를 모두 넣은 후,
(2) 이항 연산자들은 모두 그들 오른쪽에 있는 괄호와 대체시킨다
((a/((b-c)+d))*(e-a)) * c )
차례대로 대체하면 다음과 같이 됩니다. ((a((bc)-d)+)/(ea)-)*)c*
(3) 모든 괄호를 삭제한다.
모든 괄호를 삭제하면, abc-d+/ea-*c*가 됩니다.
이렇게 만들어진 수식의 위와 같은 밥법으로 계산하면 쉽게 계산을 할 수 있습니다.
Infix방법은 우리가 일반적으로 사용하는 방법입니다. 즉 연산자(operrator)가 중앙(in)에 들어가는 것이죠.
a+b, (a+b)*c, (a+b)*(c-d) 는 모두 infix 방식입니다.즉 연산자는 좌우에 있는 값을 가지고 연산을 하는 것이죠.
그러나 컴퓨터상에서 컴파일이나 인터프리터를 만들 때에는 이 방식이 불편합니다. 실제로 a/(b-c+d)*(e-a)*c와 같은 string을 읽어 들여 계산하는 프로로그램을 한번 만들어 보세요.
그래서 컴퓨터 엔지니어들이 만든 방식이 prefix와 postfix입니다.
postfix는 연산자를 뒤에 놓는 방법입니다.
즉, a+b를 postfix방식으로 나타내면 ab+가 됩니다.
즉 연산자 앞의 두값(a와 b)을 가지고 연산을 하면 됩니다.
(a+b)*c는 (ab+)c*가 됩니다. 즉 (ab+)와 c를 곱하기(*)하라는 이야기되지요.
prefix나 postfix에는 ()를 사용하지 않으므로 (ab+)c*는 ab+c*가 됩니다.
그러면, 왜 컴퓨터에서는 이 방식으로 표현하는 것이 계산하기 편한지 살펴봅시다.
수식 ab+c*에서
1. 첫번째 숫자 a를 읽어 stack에 넣읍니다. (그러면 stack에는 a가 있습니다.)
2. 두번째 숫자 b를 읽어 stack에 넣읍니다. (그러면 stack에는 a, b가 있습니다.)
3. 세번째 +(연산자)를 만나면 stack에서 가장 최근 값2개를 꺼내서 연산(+)합니다.
연산된 결과는 다시 stack에 넣읍니다 (그러면 stack에는 K가 있습니다. K=a+b)
4. 네번째 숫자 c를 만나면 stack에 넣읍니다. (그러면 stack에는 K, c가 있습니다.)
5. 다섯번째 *(연산자)를 만나면 stack에서 가장 최근 값2개를 꺼내서 연산(*)합니다.
연산된 결과는 다시 stack에 넣읍니다 (그러면 stack에는 X가 있습니다. X = K*c)
6. 수식에 더 이상 없으면 stack에서 숫자를 꺼냅니다. 이 것이 답입니다.
====> 요약하면, 앞에서 부터 차례대로 읽어 가면서, 숫자를 만나면 stack에 넣고,
연산자를 만나면 stcack에 넣은 가장 최근 값 2개를 연산하여 다시 stack에 넣으면 됩니다.
a/(b+c)를 postfix로 표기하면, a(bc+)*가 되고 괄호를 없애면 abc+*가 됩니다.
첫번째 값을 읽어보면 a가 되고...(한번 차례대로 해보세요.)
a/(b-c+d)*(e-a)*c를 postfix방식으로 바꾸어 봅시다.
(1) 식을 모두 괄호로 묶는다.
수식 모두에 계산하는 순서대로 괄호를 넣으면 ((a/((b-c)+d))*(e-a))*c)됩니다. 즉 가장 안에 있는 괄호부터 하나씩 계산하면 되도록 괄호를 모두 넣은 후,
(2) 이항 연산자들은 모두 그들 오른쪽에 있는 괄호와 대체시킨다
((a/((b-c)+d))*(e-a)) * c )
차례대로 대체하면 다음과 같이 됩니다. ((a((bc)-d)+)/(ea)-)*)c*
(3) 모든 괄호를 삭제한다.
모든 괄호를 삭제하면, abc-d+/ea-*c*가 됩니다.
이렇게 만들어진 수식의 위와 같은 밥법으로 계산하면 쉽게 계산을 할 수 있습니다.
'DS/ALGORITHUM' 카테고리의 다른 글
| Heap Sort (0) | 2008.06.20 |
|---|
