여러 복합 계산 : 후위연산자, Stack 개념 활용

계산기를 구현하다가 만약 여러 연산자가 섞인 입력값이 들어오면 어떻게 처리해야 할까?

예를 들어서, ((2+4)/6*10-5*8)/(3-6*5) 말이다 ...

 

이때 필요한 개념은 후위 연산자와 스택이다.

 

복합 계산 입력값을 컴퓨터가 이해할 수 있도록 바꿔주려면 후위 연산자 개념이 필요하다.

예를 들어, (2+4)*8/6 을 계산하고 싶다면, 컴퓨터가 이해하기 쉽도록 후위 연산자 표현인 2 4 + 8 * 6 / 으로 바꿔줘야 한다. 해당 표현으로 바꿔주면 컴퓨터는 해당 복합 연산식을 계산할 수 있다.

 

후위 연산자는 숫자가 앞에 있고, 연산자가 뒤(후)에 있도록 나열하는 방식이다. 주어진 후위 연산자 표현 2 4 + 8 * 6 /

표현을 컴퓨터는 어떻게 계산하는지 살펴보자

 

2 4 + 8 * 6 / 
// 첫번쨰 연산 : 2 + 4 = 6

6 8 * 6 /
// 두번째 연산 : 6 * 8 = 48

48 6 /
//마지막 연산 : 48 / 6 → 8

 

이런 식으로 컴퓨터는 순차적으로 계산을 처리할 수 있다. 이것을 어떻게 코드로 구현할까?

 

Step 1. 입력값 String 을 토큰화하여 배열로 만들자!

사용자로부터 (2 + 4) * 8 / 6 을 받았다고 예시를 들자. 그러면, 각각의 값들에 접근하기 위해서는 공백을 기준으로 문자열을 토큰화하여 배열로 만들어줘야 한다. 이때, split 함수만 쓰면 List 로 값이 반환되기 때문에 배열로 바꾸고 싶은 경우 따로 함수 처리를 해줘야 한다.

val input = "(2 + 4) * 8 / 6"

var tempStr = s.replace("(", "( ") // 토큰화를 위한 공백 처리
tempStr = tempStr.replace(")", " )") // 토큰화를 위한 공백 처리

val result1 = tempStr.split(" ").toTypedArray() // 공백을 기준으로 토큰화 하기
// result1 : Array<String> // ["2","+","4","*","8","/","6"]

val result2 = tempStr.split(" ")
// result2 : List<String>

 

 

Step 2. 토큰화한 배열에 접근하여 후위 연산자 표현으로 바꾸자!

이제 해당 배열의 값을 꺼내오면서 후위 연산자의 표현으로 바꿔야 한다.  즉 2 4 + 8 * 6 / 으로 말이다. 후위 연산자를 만들기 위해서는 stack 이 필요하다. stack 은 쌓이는 구조로, FILO(First In Last Out) 또는 LIFO(Last In First Out)의 형태를 가진다.  heap함수(스택의 맨 위 원소 확인), push함수(원소를 스택에 넣는 것), pop함수(가장 맨 위의 원소를 빼는 것) 가 있다. 여기서는 if 대신 while 을 사용하여 조건을 만족하면 계속 해당 로직이 수행되도록 하였다. (복잡한 연산 고려) 해당 로직을 연산하고 나면 answer 변수에는 "2 4 + 8 * 6 / " 이 저장된다.

이때, e 가 연산자일때 코드의 의미를 살펴보자.

1. 스택이 비어있을 때 → e 를 스택안에 넣는다

2. 스택이 비어있지 않을 때 → 스택 맨 위 원소의 우선순위가 e 보다 높으면 빼고, 아니면 e 를 넣는다 (우선순위가 높은 연산자가 먼저 계산되어야 하므로 우선순위가 높은걸 빼야한다!)

그리고,  e가 ")" 일 때는 "("를 만나기 전까지 전부 빼고, 마지막에 "(" 도 빼야 한다. (참고로 스택에 "(",")"는 넣지 않는다)

 

val stack = Stack<String>()
val answer : String = "" // 후위 연산 결과 값을 저장할 변수
for (e in result1) {
                when (e) {
                    "+", "-", "*", "/" -> {
                        while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(e)) {
                            // 이미 스택에 뭔가 존재하는데 맨 위에 존재하는게 우선순위가 더 높을때
                            answer += stack.pop() + " "
                        }
                        stack.push(e)
                    }

                    "(" -> {
                        stack.push(e)
                    }

                    ")" -> {
                        while (stack.peek() != "(") {
                            answer += stack.pop() + " "
                        }
                        stack.pop() // ( 제거
                    }

                    else -> {
                        answer += "$e "
                    }
                }
            }

    while (!stack.isEmpty()) {
        answer += stack.pop() + " "
    }
            
    fun precedence(operation: String): Int {
            return when (operation) {
                "*", "/" -> 2
                "+", "-" -> 1
                else -> 0
            }
        }

 

Step 3. 후위 연산식을 컴퓨터에게 넘겨서 계산하게 하자!

이제 컴퓨터가 이해할 수 있도록 식을 바꿨기 때문에, 이제 컴퓨터에 넘겨주기만 하면 된다. 이때는 스택 개념이 필요하다.

해당 로직을 수행하고 난 후 나오는 answer 값이 우리가 처음에 입력한 (2+4)*8/6 의 결과값이 된다!

str = "2 4 + 8 * 6 / "

val strArr = str.split(" ") // 이번엔 List<String> 으로 받아보자! 
val stack = Stack<String>()
var answer = 0 // 최종 연산 값

for (e in strArr) {
    when (e) {
        "+" -> {
            val num1 = stack.pop().toInt()
            val num2 = stack.pop().toInt()
            answer = num1 + num2
            stack.push(answer.toString())
        }

        "-", "*", "/" → 로직이 "+" 와 같이 때문에 생략 ...

        else -> { // 숫자인 경우
            stack.push(e)
        }
    }