오늘은 스택을 사용하여 수식을 후위 표기법으로 변환하여 보겠습니다.

방식

우선 연산자와 피연산자로 구성된 수식을 표기하는 방법에 3가지가 있다는 것을 짚고 넘어가자면,

• 전위 표기법

• 중위 표기법

• 후위 표기법

이렇게 세가지의 종류가 있습니다.

전위 표기법은 연산자를 앞에 표기하고 그 다음에 피연산자를 나열하는 방법이며, 중위 표기법은 일반적인 수식 표기법이자 연산자를 피연산자의 가운데에 표기하는 방법입니다. 마지막으로 이번에 다룰 후위 표기법은 연산자를 피연산자 뒤에 표기하는 방법입니다.

전위 표기법 변환

간단하게 중위 표기법을 전위 표기법으로 바꾸려는 예시를 들자면,

1. 수식의 연산자를 우선 순위에 따라서 괄호로 묶습니다.

2. 각 연산자에 대응되는 왼쪽 괄호의 앞으로 이동합니다.

3. 괄호를 제거합니다.

예시를 들자면 아래와 같습니다.

1. a*b-c/d

2. ((a*b) - (c/d))

3. -(*(a b) / (c d))

4. -* a b / c d

후위 표기법 변환

전위 표기법을 예시로 나타낸 것처럼 후위 표기법으로도 바꾸어 보겠습니다.

1. 우선 수식의 각 연산자를 우선 순위에 맞게 괄호를 사용하여 다시 표기합니다.

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

3. 괄호를 제거합니다.

직접 예시를 들면,

1. a*b-c/d

2. ((a*b) - (c/d))

3. ((a b) * (c d)/)-

4. a b * c d / -

왜 후위 표기법을 쓰는가

우리가 계산을 하는 과정과 다르게 컴퓨터는 수식을 처리할 때 후위 표기법이 가장 효율적이라고 합니다.

후위 표기법은 괄호나 연산자를 왼쪽에서 오른쪽 순서대로 처리할 수 있기 때문입니다.

그래서 스택을 이용하여 중위 연산식을 후위 연산식으로 변환하게 되는 것입니다.

위에는 사람이 후위 연산으로 변환하는 과정을 설명했다면, 아래는 컴퓨터가 변환하는 방식을 서술해보겠습니다.

컴퓨터의 후위식 변환

1. 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽습니다.

2. 피연산자를 만나면 따로 뺍니다.

3. 연산자를 만나면 스택에 넣습니다.

4. 오른쪽 괄호를 만나면 스택에서 꺼냅니다.

5. 수식이 끝나면 스택이 공백이 될 때까지 꺼냅니다.

알고리즘

func()
    while(true) do{
        tmp <- get(exp);
        case {
            tmp = operand :
                print();
            tmp = operator : 
                push();
            tmp = ")":
                print(pop());
            tmp = null:
                while(isempty()) do
                    print(pop());
        }
    }
end()