자바로 배우는 쉬운 자료구조 - 수식의 후위 표기법 변환

연산자와 피연산자로 구성된 수식을 표기하는 방법은 연산자의 위치에 따라 다음의 세 가지 표기법이 있다.

(1) 전위 표기법(Prefix Notation)

    : 연산자를 앞에 표기하고 그다음에 피연산자를 표기하는 방법(+AB)

(2) 중위 표기법(Infix Notaion)

    : 연산자를 피연산자의 가운데에 표기하는 방법(A+B)

(3) 후위 표기법(Postfix Notaion)

    : 연산자를 피연산자 뒤에 표기하는 방법(AB+)

다음 수식을 전위 표기법으로 변환해보자

A*B-C/D

(1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

     -> ((A*B)-(C/D))

(2) 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킨다.

-> -(*(AB)/(CD))

(3) 괄호를 제거한다.

-> -*AB/CD

같은 수식을 후위 표기법 으로 변환해보자

(1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

-> ((A*B)-(C/D))

(2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

-> ((AB)*(CD)/)-

(3) 괄호를 제거한다.

-> AB*CD/-