후위표기식이란?
: 일반적으로 피연산자 사이에 연산자를 두고 식을 풀어가는 방법을 중위표기식이라고 한다.
후위표기식은 피연산자 뒤에 연산자를 표기하는 방식이다.
예제 1)
1 + 2 → 3 (중위표기식)
12+ → 3 (후위표기식)
후위 표기식으로 표현된 식은 다음과 같이 계산하면 된다.
1. 앞에서부터 읽으며 피연산자는 스택(Stack)에 쌓는다.
2. 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 다시 스택에 쌓는다.
3. 1~2번을 반복한다.
위 방식대로 다음 식을 계산해보자.
Stack | 연산 |
[3, 5, 7, 6] | 먼저 3, 5, 7, 6이 차례대로 스택에 쌓인다. |
[3, 5] | 덧셈 연산자를 만나면 스택에서 피연산자 2개를 꺼내 계산한다. |
[3, 5, 13] | 결과를 다시 스택에 쌓는다. (13) |
[3] | 곱셈 연산자를 만나면 스택에서 피연산자 2개를 꺼내 계산한다. |
[3, 65] | 결과를 스택에 쌓는다. (65) |
[] | 뺄셈 연산자를 만나면 스택에서 피연산자 2개를 꺼내 계산한다. |
[-62] | 결과를 스택에 쌓는다. (-62) |
위 과정을 통해 최종 결과값은 -62임을 알 수 있다.
본문 출처: