6. 중위식 데이터 배열 -> 후위식 데이터 배열로 변환

1. 중위식을 전용 데이터 배열로 변환

2. 중위식으로 이루어진 전용 데이터 배열을 후위식으로 이루어진 전용 데이터배열로 변환

3. 후위식으로 이루어진 데이터배열을 연산하여 결과를 추출

이번 포스트에는 2번의 내용을 담습니다.

간단하게 설명을 드리자면 이 로직에는 두가지의 자료구조가 있습니다.

스택과 데큐입니다(데큐는 배열, 큐로 대체가 가능합니다)

처음부터 끝까지 순회 하면서, 조건이 없는 숫자들은 일단 데큐에 넣습니다.

그리고 연산자들은 스택에 넣습니다.

괄호는 왼쪽괄호는 스택에 넣고, 오른쪽 괄호가 나올때까지 스택의 값들을 데큐에 넣습니다.

+, - 기호의 경우는 스택이 비거나, 왼쪽 괄호가 나올때까지의 값들을 데큐에 넣은 후 해당 위치의 기호를 스택에 넣습니다.

* / 기호의 경우는 스택이 비거나, 스택의 값이 * / 연산자 일동안의 스택의 값을 데큐에 넣은 후 해당 위치의 기호를 스택에 넣습니다. 

반복이 끝나면, 스택에서 빠져나오지 못한 기호들을 전부다 데큐에 넣습니다.

위는 연산자 우선순위를 고려하기때문에 경우가 다 다릅니다. + - 보다는 * / 가 우선이고, * / 보다는 () 괄호 처리가 우선이기때문에, 다음과 같은 경우의 수를 가집니다.

스위프트로 구현된 코드는 다음과 같습니다.

func InfixToPostfix(_ array: Array<CalculatorData>) -> Array<CalculatorData>{
    var tmpStack: Stack<CalculatorData> = Stack<CalculatorData>()
    let length = array.count-1
    var postfixDequeue: Dequeue<CalculatorData> = Dequeue<CalculatorData>()
    var type: CalculatorEnumeration = .etc
    
    for index in 0...length{
        //값일때는 그냥 배열에 넣고 다음 반복으로 넘어간다
        if(array[index].type == .value){
            postfixDequeue.Insert(array[index])
            continue
        }
        
        //연산자이거나, 괄호인 경우에는...
        type=array[index].type
        switch type{
        case .lParen :
            //왼쪽 괄호일 경우, 현재 기호를 넣는다
            tmpStack.Push(array[index])
        case .rParen :
            //오른쪽 괄호 일 경우 왼쪽 괄호가 나올때까지의 값을 식에 넣는다
            while tmpStack.Top().type != .lParen{
                postfixDequeue.Insert(tmpStack.Pop())
            }
            // ( 괄호를 지운다
            _ = tmpStack.Pop()
        case .operatorPlus, .operatorMinus :
            //덧셈, 뺄셈일 경우에는 스택이 비거나, 괄호가 나올때까지 값을 식에 넣는다
            while tmpStack.IsEmpty == false && tmpStack.Top().type != .lParen{
                postfixDequeue.Insert(tmpStack.Pop())
            }
            //기호는 스택에 넣는다
            tmpStack.Push(array[index])
        case .operatorMultiple, .operatorDivide :
            //곱셈,나눗셈일 경우에는 스택이 비거나, 현재 값이 곱셈,나눗셈일 동안 스택에 넣는다
            while tmpStack.IsEmpty == false && (tmpStack.Top().type == .operatorMultiple || tmpStack.Top().type == .operatorDivide){
                postfixDequeue.Insert(tmpStack.Pop())
            }
            //기호는 스택에 넣는다
            tmpStack.Push(array[index])
        default:
            //그 외에는 그냥 넘어간다(그외에 들어오는것은 에러)
            break
        }
    }
    
    //스택의 남은 값들을 식에 넣는다
    while tmpStack.IsEmpty == false{
        postfixDequeue.Insert(tmpStack.Pop())
    }
    
    //식을 반환한다
    return postfixDequeue.DequeueToArray()
}

스택은 비워지고, 후위표기로 정제된 데큐 배열이 반환됩니다.