[Kotlin] 계산기 - 후위연산식 구현

neoneoneo·2024년 3월 11일

kotlin kotlin_stack 계산기 자료구조_후위연산식

kotlin

목록 보기

26/49

배경

캠프에서 과제로 계산기를 만드는 과정에서 연산자와 계산 항이 여러 개인 계산식을 처리하기 위해 후위연산식 처리가 필요했다.

내가 구현한 코드가 엉망진창이라 부끄럽기는 하지만.. 후위연산식 처리 부분에 대해서만 간단하게 소개를 하고, 튜터 선생님의 코드와 비교하여 개선해야 하는 점들이 무엇인지 스스로 탐구하는 시간을 가지고자 한다.

본 포스팅에는 그 과정을 적어본다.

나의 코드

FreeOperation 클래스 구성

클래스 안에는 4개의 함수가 작성되어있다.

class FreeOperation: AbstractOperation() {
	fun getPriority(operator: Char): Int { ... }
    fun operationPostfix(postfixText: String): Double { ... }
    fun exchangePostFix(infixText: String): String { ... }
    override fun operation() { ... }    
getPriority(operator: Char): Int: 연산자의 우선순위를 반환하는 함수이다. 연산자에 따라 우선순위가 다르게 설정되어 있다.

operationPostfix(postfixText: String): Double: 후위 표기법으로 표현된 수식을 계산하는 함수이다. 스택을 활용하여 계산이 이루어진다.

exchangePostFix(infixText: String): String: 중위 표기법(일반적인 수식 표현)으로 주어진 수식을 후위 표기법으로 변환하는 함수이다. 연산자 스택과 출력 스택을 사용하여 변환을 수행한다.

operation(): 사용자에게 수식을 입력받아 해당 수식의 계산 결과를 출력하는 함수이다. 사용자로부터 숫자와 연산자를 동시에 입력받아 계산을 수행한다.

함수는 operation 함수에서 다른 함수들을 호출하는 방식으로 구성했다.

operation

exchangePostFix -> 후위표기법으로 변환

getPriority -> 전환 과정에서 우선순위 판별

operationPostfix -> 후위표기식 계산

getPriority

fun getPriority(operator: Char): Int {
        return when (operator) {
            '+', '-' -> 1
            '*', '/' -> 2
            else -> 0
        }
    }

받아오는 operator 연산자가
- '+' '-' 인 경우에는 우선순위 1
- '*' '/' 인 경우에는 우선순위 2
- 그 외는 0으로 처리한다.

opertationPostfix

  fun operationPostfix(postfixText: String): Double {
        var result = 0.0
        var stack = Stack<Double>()
        //공백을 기준으로 데이터를 배열에 저장해두기
        var splitPostFix = postfixText.split(' ')
        splitPostFix.forEach {
            when {
                it == "+" -> stack.push(stack.pop() + stack.pop())
                it == "-" -> {
                    val op2 = stack.pop()
                    val op1 = stack.pop()
                    stack.push(op1 - op2)
                }
                it == "*" -> stack.push(stack.pop() * stack.pop())
                it == "/" -> {
                    val op2 = stack.pop()
                    val op1 = stack.pop()
                    stack.push(op1 / op2)
                }
                else -> {
                    stack.push(it.toString().toDouble())
                }
            }
        }
        result = stack.pop() //후위계산식 결과
        return result
    }

두 자리 수 이상의 수도 처리할 수 있도록 모든 숫자 또는 연산자는 ' ' 공백으로 구분되어 있으므로, split(' ')하여 공백을 기준으로 데이터를 배열에 저장해둔다.
그렇게 가공된 데이터에 하나씩 접근하면서, 연산자일 경우에는 해당하는 연산 처리를 하여 다시 스택에 push해둔다.
최종적으로 모든 연산 처리가 완료된 결과를 result에 저장하여 리턴한다.

exchangePostFix

    fun exchangePostFix(infixText: String): String {
        var postFixText = ""
        var output = StringBuilder()
        var operators = Stack<Char>()
        if (infixText.isNotEmpty()) {
            var i = 0
            while (i < infixText.length) {
                var accCount = 0
                when {
                    //숫자 저장 파트
                    infixText[i].isLetterOrDigit() -> {
                        var numberBuiler = StringBuilder()
                        var nextIndex = i + 1
                        if (nextIndex < infixText.length && infixText[nextIndex].isDigit()) { //다음이 숫자면
                            accCount = nextIndex - 1
                            while (accCount < infixText.length && infixText[accCount].isDigit()) { //다음이 숫자가 아닐 때까지
                                numberBuiler.append(infixText[accCount])
                                accCount++
                            }
                            if (numberBuiler.isNotEmpty()) {
                                numberBuiler.append(' ')
                                output.append(numberBuiler.toString())
                            }
                            i += (accCount - i)
                            continue
                        } else { //다음이 숫자가 아니면
                            numberBuiler.append(infixText[i])
                            if (numberBuiler.isNotEmpty()) {
                                numberBuiler.append(' ')
                                output.append(numberBuiler.toString())
                            }
                        }
                    }
                    //연산자 저장 파트
                    //괄호 처리
                    infixText[i] == '(' -> operators.push(infixText[i])
                    infixText[i] == ')' -> {
                        while (operators.isNotEmpty() && operators.peek() != '(') {
                            output.append(operators.pop())
                            output.append(' ')
                        }
                        operators.pop() //'(' 제거
                    }
                    //괄호 외 연산자 처리
                    else -> {
                        //스택에서 우선순위가 높거나 같은 연산자들을 pop하여 저장 후, 현재 연산자를 스택에 push
                        while (operators.isNotEmpty() && getPriority(operators.peek()) >= getPriority(infixText[i])) {
                            output.append(operators.pop())
                            output.append(' ')
                        }
                        operators.push(infixText[i])
                    }
                }
                i++
            }
            //스택에 남아있는 연산자가 있을 경우 모두 output에 저장
            while (operators.isNotEmpty()) {
                output.append(operators.pop())
                output.append(' ')
            }
            output.deleteAt(output.lastIndex) //후위계산식의 맨 마지막 공백 제거
            postFixText = (output.toString())
        }
        return operationPostfix(postFixText).toString()
    }

크게 숫자 저장, 연산자 저장 파트로 나눌 수 있다.
숫자 저장 파트
- 숫자는 2자리 이상 일 수도 있기 때문에 nextIndex를 이용하여 다음 인덱스의 값을 미리 읽어보고, 다음도 숫자라면 두 자리 수 이상으로 판단한다.
  - accCount를 nextIndex에서 1을 뺀 수로 초기화 해준다.
    - 그래야 나중에 중복해서 digit을 저장하지 않도록 i에 더하여 사용할 수 있다.
    - 이 작업을 하지 않았더니 10 2 3 이런 식을 저장해야 하는 숫자를 10 0 2 3 이런식으로 저장했었다.
  - 다음이 숫자가 아닐 때 까지(즉, 연산자가 나올 때까지) 반복하면서 숫자를 저장해둔다.
- 저장해둔 숫자를 output에 넣을 때 ' ' 을 함께 저장하여 향후 계산처리할 때 숫자 사이를 구분할 수 있도록 한다.
연산자 저장 파트
- 괄호 중에 (가 오면 무조건 operator 스택에 저장해둔다.
- 괄호 중에 )가 오면 operator 스택에서 (를 만날 때까지 계속 pop하여 output에 더해준다. (는 제거해준다.
- 괄호 외의 연산자를 만나면 gerPriority() 함수를 호출하여 우선순위를 판단한 후, 우선순위가 더 높거나 같다면 pop하여 ouput에 저장해둔다. 이 때 마찬가지로 ' '를 함께 더해준다.
- 마지막으로 스택에 남은 연산자가 있으면 모두 pop하여 ouput에 더해준다.
또한 ' '를 계속 함께 더했더니 후위연산 처리를 할 때 ' '이 껴있다고 계속 오류가나서 deleteAt으로 가장 마지막 인덱스에 저장되어 있는 공백을 제거해주었다.
그 이후 산출된 후위연산식은 operationPostfix() 함수를 호출하여 계산한다.

튜터 선생님의 코드

클래스 구성

클래스는 4개의 함수로 구성되어 있다.

class FreeOperation: AbstractOperation() {
	fun precedence(operator: String): Int { ... }
    fun strToArr(str: String): Array<String> { ... }
    fun finalCalc(result: String): Int { ... }
    fun getPostFixExpressionOperation(originalExpression: String): Int { ... }    
연산자의 우선순위를 반환한다.

계산식을 하나씩 쪼개서 문자열을 배열로 변환한다.

후위표기법으로 된 수식을 계산한다.

중위표기법 수식을 후위표기법으로 변환하고 계산한다.

    fun precedence(operator: String): Int {
        return when(operator) {
            "+", "-" -> 1
            "*", "/" -> 2
            else -> 0
        }
    }

이 부분은 내가 구현한 내용과 비슷하다.

    fun strToArr(str: String): Array<String> {
        var tempStr = str.replace("(", "( ")
        tempStr = tempStr.replace(")", " )")
        return tempStr.split(" ").toTypedArray()
    }
괄호는 ' ' 을 앞 또는 뒤에 추가한다.

단, 이 함수로 구현할 때에는 input 자체를 (2 + 3) * 2 이런식으로 괄호를 제외한 숫자와 연산자에 공백을 포함하여 받아야 한다.

    fun finalCalc(result: String): Int {
        val stack = Stack<String>()
        val calResult = result.split(" ")
        var result = 0
        for(e in calResult) {
            when(e) {
                "+" -> {
                    result = stack.pop().toInt() + stack.pop().toInt()
                    stack.push(result.toString())
                }
                "-" -> {
                    result = -stack.pop().toInt() + stack.pop().toInt()
                    stack.push(result.toString())
                }
                "*" -> {
                    result = stack.pop().toInt() * stack.pop().toInt()
                    stack.push(result.toString())
                }
                "/" -> {
                    val num2 = stack.pop().toInt()
                    val num1 = stack.pop().toInt()
                    result = num1 / num2
                    stack.push(result.toString())
                }
                else -> {
                    stack.push(e)
                }
            }
        }
        return result
    }

연산자에 따른 연산 처리를 하여 result를 리턴한다.

      fun getPostFixExpressionOperation(originalExpression: String): Int {
        val stack = Stack<String>()
        val arr = strToArr(originalExpression)
        var result = ""
        for(e in arr) {
            when(e) {
                "+", "-", "*", "/" -> {
                    while(!stack.isEmpty() && precedence(stack.peek()) >= precedence(e)) {
                        result += stack.pop() + " "
                    }
                    stack.push(e)
                }
                "(" -> {
                    stack.push(e)
                }
                ")" -> {
                    while(stack.peek() != "(") {
                        result += stack.pop() + " "
                    }
                    stack.pop() // "(" 제거
                }
                else -> {
                    result += "$e "
                }
            }
        }
        while(!stack.isEmpty()) {
            result += stack.pop() + " "
        }
        println("---최종---")
        println("후위표기법: $result")
        val realResult = finalCalc(result)
        println("결과: $realResult")
        return realResult
    }

for문을 통해 피연산/연산자를 하나씩 꺼내오면서,
- 연산자일 경우 precedence() 함수를 호출하여 우선순위 판단 후 처리
- (일 경우 바로 push
- )일 경우 기존에 들어있는 스택에서 pop하고 (를 만나면 중단 후 (는 제거
- 그 외일 경우, 즉 숫자인 경우에는 "$e " 처리한다.
while 문을 돌면서 스택에 남아있는 게 있으면 pop하여 result에 공백과 함께 저장해둔다.
후위연산 계산은 finalCalc()함수를 호출하여 처리한다.

배운점

튜터 선생님은 애초에 input을 받을 때 공백이 포함되도록 받기 때문에 내 코드보다 더 간결하게 작성을 하신 것 같다. 데이터를 받아오는 방식에 대한 정책부터가 달랐기 때문에.. 서로 정확하게 비교하기는 어렵지만, 이번에 내가 쓴 코드는 임시로만 사용하고 버리는 변수들이 많았던 것 같다. 임시 변수가 많아지면 코딩을 할 때 머리가 복잡해지고 오류가 어디에서 발생하는지 찾아내기가 힘든 것 같다. 특히 nextIndex, accCount, numberBuilder 얘네 3개는 계속 프린트해보면서 정상적으로 처리가 되고 있는지 감시해야 했는데, 그 과정에서 인덱스가 꼬여 애를 먹었다.
- 임시변수 따위 필요 없게 초천재처럼 코드를 짜거나.. 그게 어려우면 임시변수의 이름이라도 더 직관적으로 쉽게 받아들일 수 있게 짓던지 해야겠다. 블로그에 올리는 코드는 최종적으로 리네이밍을 한거지만.. 코드 쓰는 중간중간에 변수명이 마음에 안들어서 계속 바꿨더니 더 머릿 속에서 헷갈렸던 것 같다. 진짜 모든 내용을 다 짠다으면 리네이밍을 하거나 최초에 이름을 잘 지어야할 것 같다.