[Algorithm] 차량기지 알고리즘, 스택을 사용하여 중위 표기법을 후위 표기법으로 변환

0. 시작

1 + 3.334 / (4.28 * (110 - 7729) = ?
위 식을 계산해 볼까요?
사칙 연산은 초등학교 과정에서 배우므로, 대부분의 사람은 큰 어려움 없이 해낼 수 있습니다. 소수는 언제 배우는지 잊었습니다만..
그러나 컴퓨터는 초등학교를 다니지 않기 때문에, 위 식을 직관적으로 풀 수 없습니다.
이 말은, 컴퓨터에게 더하기, 빼기 등의 연산자를 가르친 후 연산자의 우선순위까지 알려준 다음!
우선순위에 따라 각 항을 계산하는 방법을 알려주어야 한다는 것이죠.

컴퓨터와 친해지기 위해, 정확히는 알고리즘과 친해지기 위해 이를 직접 구현해보는 시간을 갖도록 하겠습니다.

물론, 요즈음의 컴파일러는 이를 잘 해냅니다.
IDE에서 수식 요리조리 입력한 후 빌드 때리면 결과가 짠 하고 나오는 마법의 세상...!
(사칙연산을 할 수 있도록 고안된 컴파일러에게 사칙연산을 구현한 코드를 빌드하는 과정에서 사칙연산을 수행하여 기계어로 만드는...
사칙연산을 사칙연산하여 다시 사칙연산하는 CPU...)

1. 중위 표기법: Infix

1 + 3.334 / (4.28 * (110 - 7729)

중위표기법이란, 흔히 쓰는 수식의 표기법입니다.
맨 처음 보여드렸던 식 처럼연산자가 피연산자 가운데 오도록 식을 표기하는 방법이지요.
그러나 컴퓨터가 이를 직접 계산하기엔 불편합니다.
항을 다 쪼개고, 우선순위에 따라 먼저 계산하는데, 여기에 괄호가 포함되고...이러쿵 저러쿵

계산이 귀찮은 우리는 컴퓨터에게 이를 맡기려고 합니다.
그런데 반복되는 일련의 과정을 수행하는데에 능한 컴퓨터에게, 중위표기법은 너무 어려운 길 입니다.
중위표기법을 계산하는 방법을 알려주는것과 우리가 식을 푸는 것...비슷비슷할 것 같습니다.

만약 사칙연산임에도 불구하고, 앞에서부터 쭉쭉 계산할 수 있도록 할 수는 없을까요?
컴퓨터가 앞에서 쭉쭉 읽고, 연산자의 우선순위 때문에 다시 앞으로 돌아갈 일이 없도록 할 수 있다면 참 좋을텐데요...

그런 당신에게 딱인 물건, 후위 표기법을 가지고 왔습니다!

2. 후위 표기법: Postfix

1 3.334 4.28 110 7729 - * / +

후위표기법은 역폴란드 표기법과 같은 말입니다.
연산자를 피연산자 뒤에 써 수식을 표기합니다. 그런데 이게 계산이 되는 식인지 궁금하지 않으신가요?
그런 당신을 위해 간단한 예시를 들어보겠습니다. 아, 계산을 위해서는 스택이 필요합니다.

단순하고, 아름답지 않나요?
식을 앞에서부터 읽어가며 계산하고, 계산을 위해 다시 앞으로 돌아가는 일이 없습니다!
이미 우선순위가 식에 적용되어 있기 때문이지요.

3. 차량기지 알고리즘: 중위표기법에서 후위표기법으로 변환

그림으로 보는 차량기지 알고리즘, 출처 - 위키피디아

차량기지 알고리즘 이라는 이름이 생소하신 분들이 계실거라고 생각합니다.
'중위표기법에서 후위표기법 변환 알고리즘' 이 알고리즘 이름이 아닐것 같아 조사해보니, 차량기지 알고리즘이라고 합니다.
무려 다익스트라 알고리즘으로 유명하신 컴퓨터 과학자 에드거 다익스트라(에츠허르 데이크스트라) 께서 고안하셨구요!

알고리즘의 동작 과정은 다음과 같습니다.

• 입력이 아직 남아있는 동안
  • 입력에서 토큰을 읽어들인다.
  • 만약 토큰이 숫자 또는 변수일 경우 출력 큐에 넣는다.
  • 만약 토큰이 함수일 경우 연산자 스택에 푸쉬한다.
  • 만약 토큰이 함수 인자의 구분자(예: 쉼표)일 경우
    • 스택에서 여는 괄호 '(' 가 나타날 때까지 팝하여 출력 큐에 넣는다. 만약 여는 괄호가 나타나지 않으면 구분자의 위치가 잘못되었거나 여는 괄호와 닫는 괄호가 맞지 않는 것이므로 오류를 출력한다.
  • 토큰이 연산자 o1이라면, 연산자 스택의 맨 위에 연산자가 없을 때까지 다음을 반복한다
    • 만약 스택에 연산자 o2가 있다면
      o1이 왼쪽 결합 연산자이고, 연산의 우선순위가 o2와 같거나 그보다 낮을 경우,또는 o1이 오른쪽 결합 연산자이고, 우선순위가 o2보다 낮을 경우o2를 팝하여 출력 큐에 넣는다.
    • 만약 스택에 연산자가 없거나 o2가 조건을 만족하지 않으면 o1을 연산자 스택에 푸쉬한다.
  • 만약 토큰이 여는 괄호 '(' 일 경우 연산자 스택에 푸쉬한다.
  • 만약 토큰이 닫는 괄호 ')' 일 경우
    • 연산자 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 넣는다.
    • 연산자 스택에서 여는 괄호가 나타나면 팝하되, 출력 큐에는 넣지 않는다.
    • 스택을 모두 팝할 때까지 여는 괄호를 찾지 못했다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
    • 여는 괄호를 팝한 후 스택 맨 위에 함수 토큰이 남아있다면 출력 큐에 넣는다.
  • 더이상 입력 토큰이 남아있지 않다면
    • 연산자 스택이 빌 때까지 토큰을 팝한다.
    • 만약 스택에 여는 괄호나 닫는 괄호가 남아있다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
    • 그 외의 연산자는 출력 큐에 넣는다.
• 입력과 연산자 스택이 모두 비었다면 알고리즘을 종료한다.

매우 길군요. 이를 중위표기법 변환 알고리즘의 맥락으로 간단하게 줄여본 동작과정은 다음과 같습니다.

1. 입력받은 중위표기식에서 토큰을 읽는다.
2. 토큰이 피연산자이면 토큰을 결과에 출력한다
3. 토큰이 연산자(괄호포함)인 경우, 스택의 최상위 노드에 담겨있는 연산자가 토큰보다 우선순위가 높은지 검사한다.
   검사 결과가 참이면, 최상위 노드를 스택에서 꺼내 결과에 출력하며, 이 검사 작업을 반복해서 수행하되 그 결과가 거짓이거나 스택이 비게 되면 작업을 중단한다.
   검사 작업이 끝난 후에는 토큰을 스택에 삽입한다.
4. 토큰이 오른쪽 괄호 ')'이면 최상위 노드에 왼쪽 괄호 '('가 올 때까지 스택에 제거 연산을 수행하고, 제거한 노드에 담긴 연산자를 출력한다.
   왼쪽 괄호를 만나면 제거만 하고 출력하지 않는다.
5. 중위 표기식에 더 읽을 것이 없다면 빠져나가고, 더 읽을것이 있다면 1부터 다시 반복한다.
   (*출처 - 책 '뇌를 자극하는 알고리즘')

Swift 코드로 구현한 결과는 다음과 같습니다.

struct Postfix{
    static func getPostfix(Infix: String)->String?{
        let infix = Infix.components(separatedBy: [" "]).joined()
        var stack = Stack<Character>()
        var postfix = String()
        for element in infix{
            if element.isNumber || element == "."{
                postfix.append(element)
            }else{
                if postfix.last != " " { postfix.append(" ") }
                if element == ")"{
                    while(stack.isEmpty == false){
                        if stack.top! == "(" {
                            _ = stack.pop()!
                            break
                        }
                        postfix.append(stack.pop()!)
                    }
                }else{
                    while(stack.isEmpty == false){
                        //스택 안에 남아있는 연산자가 자신보다 높으면 안됨
                        //즉, 스택 top과 현재 op를 비교하여, top이 높지 않으면 break
                        if stack.top!.isPrior(Op: element) == false {break}
                        if element != "(" {
                            postfix.append(stack.pop()!)
                        }
                    }
                    stack.push(element)
                }
            }
        }
        while(stack.isEmpty == false){
            if postfix.last != " " { postfix.append(" ") }
            postfix.append(stack.pop()!)
        }
        return postfix
    }
}

extension Character{
    func isPrior(Op:Character)->Bool{
        //우선순위이므로 부등호의 방향은 반대
        return self.priority(inStack: true) <= Op.priority(inStack: false)
    }
    func priority(inStack:Bool)->Int{
        enum priority:Character{
            case LEFT_PARENT = "("
            case RIGHT_PARENT = ")"
            case PLUS = "+"
            case MINUS = "-"
            case MULTIPLY = "*"
            case DEVIDE = "/"
        }
        switch priority(rawValue: self){
        case .LEFT_PARENT:
            return inStack ? 3 : 0
        case .MULTIPLY,.DEVIDE:
            return 1
        case .PLUS,.MINUS:
            return 2
        default:
            return 987654321
        }
    }
}

해당 알고리즘으로 푸는 백준문제로 연습해보는것도 괜찮은 방법입니다!

4. 마무리

구현하면서 참 즐거웠던 알고리즘 입니다.
Swift의 extension과 enum, if와 switch, while이 조화롭게 들어가는 아름다움을 느낄 수 있었지요.
눈으로만 보지 말고, 직접 구현해보며 Swift와 알고리즘에 정을 붙여보시길 바랍니다.

그럼 다음 포스팅에서 만나요!