중위 표기법과 후위 표기법

중위 표기법 (infix notation)

(A + B) * (C + D)

• 연산자가 피연산자들의 사이에 위치

후위 표기법 (postfix notation)

A B + C D + *

• 연산자가 피연산자들의 뒤에 위치

후위 표기식의 계산

앞의 두 개가 피연산자이고, 그 뒤에 나타나는 연산자를 두 피연산자에 적용한다.

즉, 피연산자를 만나면 스택에 넣고, 연산자를 만나면 두 개의 피연산자를 빼내서 연산을 한다.

발생한 연산 결과는 다시 스택에 넣어서 다음 연산에 영향을 받도록 한다.

스택 연산으로 아래의 후위 표기식의 계산을 표현한다면

A B + C D + *

push(A) —> push(B) —> pop(A), pop(B), push(A + B) —> push(C) —> push(D) —> pop(D), pop(C), push(C + D) —> pop(A + B), pop(C + D), push((A + B) * (C + D)) —> pop(…) —> return

괄호의 처리

[중위] (A + B) * C