후위식
더 많은 작업
- Postfix
- 스택(Stack)을 이용하여 연산자가 뒤에 위치하도록 한 수식
- 사람 입장에선 이해하기 어려우나 컴퓨터 입장에선 계산하기 수월하다
- ex) 3 4 * 5 6 * ＋
- 3
- 3 4
- 3 4 *
- 12
- 12 5
- 12 5 6
- 12 5 6 *
- 12 30
- 12 30 +
- 42
| 표기법 | 연산자 위치 | A + B
|
(A + B) * C
|
|---|---|---|---|
| 전위(Prefix, 폴란드 표기법) | 피연산자 앞 | +AB
|
*+ABC
|
| 중위(Infix) | 피연산자 사이 | A+B
|
(A+B)*C
|
| 후위(Postfix) | 피연산자 뒤 | AB+
|
AB+C*
|
사람이 읽기 좋은 것은 중위지만, 괄호가 필요하고 우선순위를 알아야 한다. 전위·후위는 괄호 없이도 해석이 유일하다.
중위 표기법(Infix)은 연산자를 두 피연산자 사이에 쓰는 방식이다. 사람이 손으로 쓰는 수식과 같아 대부분의 프로그래밍 언어가 쓰는 가장 일반적인 표현이고, 산술·논리·비교 연산식에 두루 쓰인다. 피연산자 둘 사이에 연산자 하나를 두는 꼴이라 이항 연산자에 알맞다(단항 연산자는 앞이나 뒤에 따로 붙인다). 연산자를 피연산자 다음(뒤)에 쓰는 것은 후위 표기법이고, 앞에 쓰는 것은 전위 표기법이다.
- 연산자 우선순위에 따라 수식 전체를 괄호로 완전히 묶는다.
- 각 괄호 안의 연산자를 그 괄호의 닫는 괄호 자리로 옮긴다.
- 괄호를 지운다.
예: (A + B) * C + (D + E)
1) 완전 괄호화 : ( ( (A+B) * C ) + (D+E) ) 2) 연산자 이동 : ( ( (A B +) C * ) (D E +) + ) 3) 괄호 제거 : A B + C * D E + +
따라서 답은 AB+C*DE++ 다.
조차장 알고리즘(Shunting-yard algorithm)이라 한다. 스택 하나로 처리한다.
- 피연산자는 바로 출력한다.
- 연산자는 스택에 넣되, 스택 꼭대기에 우선순위가 같거나 높은 연산자가 있으면 먼저 꺼내 출력한 뒤 넣는다.
- 여는 괄호는 그냥 넣고, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 꺼내 출력한다.
- 수식이 끝나면 스택에 남은 연산자를 모두 꺼내 출력한다.
후위 변환과 같은 방법에서 연산자를 여는 괄호 자리로 옮기면 된다.
- 연산자 우선순위에 따라 수식 전체를 괄호로 완전히 묶는다. 대입 연산자 = 는 우선순위가 가장 낮다
- 각 괄호 안의 연산자를 그 괄호의 여는 괄호 자리로 옮긴다
- 괄호를 지운다
예: X = A + C / D
1) 완전 괄호화 : ( X = ( A + ( C / D ) ) ) 2) 연산자 이동 : = ( X + ( A / ( C D ) ) ) 3) 괄호 제거 : = X + A / C D
따라서 전위식은 =X+A/CD, 같은 식의 후위식은 XACD/+= 다.
전위식은 연산자가 피연산자 앞에 오므로, 연산자 하나와 바로 뒤의 피연산자 둘을 안쪽부터 묶어 가며 연산자를 뒤로 옮긴다.
예: - / * A + B C D E
1) + B C → (B C +) 2) * A (B C +) → (A B C + *) 3) / (A B C + *) D → (A B C + * D /) 4) - (A B C + * D /) E → A B C + * D / E -
따라서 후위식은 A B C + * D / E - 이고, 중위식으로 쓰면 ((A * (B + C)) / D) - E 이다. 피연산자 A, B, C, D, E 의 순서는 세 표기법 모두 같고 연산자의 위치만 달라진다.
스택으로 할 때는 전위식을 오른쪽부터 읽는다. 피연산자는 스택에 넣고, 연산자를 만나면 두 개를 꺼내(먼저 꺼낸 것이 왼쪽 피연산자) "왼쪽 오른쪽 연산자" 로 이어 붙인 문자열을 다시 넣는다. 끝까지 읽으면 스택에 남은 하나가 후위식이다.
역시 스택으로 한다.
- 피연산자를 만나면 스택에 넣는다.
- 연산자를 만나면 스택에서 두 개를 꺼내 연산하고 결과를 다시 넣는다. 이때 먼저 꺼낸 것이 오른쪽 피연산자다.
- 마지막에 스택에 남은 하나가 결과다.
수식 : 3 4 + 5 * 3 → [3] 4 → [3, 4] + → 3+4=7 → [7] 5 → [7, 5] * → 7*5=35 → [35] 결과 35
- 후위 표기 수식을 수식 트리의 후위 순회 결과로 볼 수 있다. 전위 표기는 전위 순회, 중위 표기는 중위 순회에 대응한다.
- 후위 → 중위 변환은 위 과정을 거꾸로 하면 된다.