Calculator lv5 stack클래스 이용

Calculator lv5 실습은 우선순위를 고려한 프로그래밍을 작성하는 것이다.

괄호가 있다면 안에있는 괄호가 먼저 계산되어야하고 만약 * / 연산자가 있다면 해당 연산자가 + 나 - 보다 먼저 계산되어야한다는 조건이다.

해당 실습을 위해서 Stack이라는 클래스를 활용해야한다고 한다.

Stack이란 개념은 아직 알고리즘에 익숙하지 않아서 여러 블로그글을 보다가 우연히  아래의 블로그에서 이미지가 잘 설명되어서 참고하였다.

https://mailmail.tistory.com/26

[자료구조] 스택(배열 이용) - push, pop

나는 총 8개의 파일로 분리하여 작성했다.

가장 먼저 작성한 파일은 Operate.kt 파일인데

연산하는 메서드와 우선순위를 담당하는 변수를 넣었다.

package com.ellycrab.calculatorlv5

interface Operator {

    //연산
    fun doOperate(num1:Double, num2:Double):Double

    //우선순위
    val precedence:Int

}

 

그 후 더하기 빼기 곱하기 나누기 나머지 연산 클래스를 작성할때, interface안의 메서드를 상속받아서 override했다.

 

연산클래스

이때 메서드 precedence는 우선순위를 담당하는것인데 곱하기나 나누기는 더하기나 빼기 연산자보다는 우선순위가 높아서 get()을 2로 받았다.

그 후 입력과 출력을 담당하는 Main.kt 파일과 계산하는 로직을 담당하는 Calculator클래스를 만들었다.

먼저 Calculator클래스에서 처음 입력받을때 String타입으로  "(3+10)*10"  이런 연산을 받기때문에

입력받은 문자열을 작은 단위로 나누어 처리하는 과정이 필요하다.

//입력받은 문자열을 작은 단위로 나누어 처리함-토큰화
fun tokenizeExpression(expression:String):List<String>{
    return expression.split(Regex("(?=[-+*/%()])|(?<=[-+*/%()])"))
        .filter { it.isNotBlank() }
}

그 후 만들어진 expression(List<String>타입)의  중위표기법을 후위표기법으로 변환하는 작업이 필요하다.

처음에 변환을 어떻게하는지 몰라 아래 블로그를 참조하였다.

https://simsim231.tistory.com/54

[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix)

글쓴이께서 그 후 스택을 이용하는 방법에대해서도 잘 알려주셨다.

// 중위 표기법을 후위 표기법으로 변환하는 메서드
fun infixToPostfix(infixTokens: List<String>): List<String> {
    // 변환된 후위 표기법 토큰을 저장할 리스트
    val postfixTokens = mutableListOf<String>()

    // 연산자 스택
    val stack = Stack<String>()

    // 주어진 중위 표기법 토큰들을 하나씩 처리
    for (token in infixTokens) {
        when {
            // 피연산자인 경우 바로 결과 리스트에 추가
            token.isNumeric() -> postfixTokens.add(token)

            // 여는 괄호인 경우 스택에 추가
            token == "(" -> stack.push(token)

            // 닫는 괄호인 경우 여는 괄호가 나올 때까지 스택에서 pop하여 결과 리스트에 추가
            token == ")" -> {
                while (stack.isNotEmpty() && stack.peek() != "(") {
                    postfixTokens.add(stack.pop())
                }
                stack.pop() // 여는 괄호 제거
            }

            // 연산자인 경우 스택의 연산자들과 비교하여 우선순위가 높거나 같은 것들을 결과 리스트에 추가하고, 현재 연산자를 스택에 추가
            token in operators -> {
                while (stack.isNotEmpty() && stack.peek() in operators &&
                    operators[stack.peek()]!!.precedence >= operators[token]!!.precedence) {
                    postfixTokens.add(stack.pop())
                }
                stack.push(token)
            }

            // 그 외의 경우 예외 처리
            else -> throw IllegalArgumentException("유효하지 않은 토큰: $token")
        }
    }

    // 스택에 남아있는 모든 연산자를 결과 리스트에 추가
    while (stack.isNotEmpty()) {
        postfixTokens.add(stack.pop())
    }

    // 최종 후위 표기법 토큰 리스트 반환
    return postfixTokens
}

예를들어 중위 표기법이 "3 + (4 * 5)"일 때,

1. token == "3": 숫자인 경우 바로 후위 표기법 리스트에 추가
   • 후위 표기법 리스트: ["3"]
2. token == "+": 연산자인 경우 스택에 추가
   • 후위 표기법 리스트: ["3"]
   • 스택: ["+"]
3. token == "(": 여는 괄호인 경우 스택에 추가
   • 후위 표기법 리스트: ["3"]
   • 스택: ["+", "("]
4. token == "4": 숫자인 경우 바로 후위 표기법 리스트에 추가
   • 후위 표기법 리스트: ["3", "4"]
   • 스택: ["+", "("]
5. token == "*": 연산자인 경우 스택에 추가
   • 후위 표기법 리스트: ["3", "4"]
   • 스택: ["+", "(", "*"]
6. token == "5": 숫자인 경우 바로 후위 표기법 리스트에 추가
   • 후위 표기법 리스트: ["3", "4", "5"]
   • 스택: ["+", "(", "*"]
7. token == ")": 닫는 괄호인 경우, 여는 괄호가 나올 때까지 스택에서 pop하여 후위 표기법 리스트에 추가하고 여는 괄호는 스택에서 제거
   • 후위 표기법 리스트: ["3", "4", "5", "*"]
   • 스택: ["+"]

 

최종적으로 후위 표기법 리스트는 ["3", "4", "5", "*"] 가 된다.

이런 방식으로 메서드를 작성하였다.

그 후 후위 표기법을 평가하는 메서드를 작성했다.

// 후위 표기법을 평가하는 메서드
private fun evaluatePostfix(postfixTokens: List<String>): Double {
    // 계산에 사용될 스택
    val stack = Stack<Double>()

    // 후위 표기법 토큰 리스트를 순회
    for (token in postfixTokens) {
        // 토큰이 숫자인 경우, 해당 숫자를 double 타입으로 변환하여 스택에 push
        if (token.isNumeric()) {
            stack.push(token.toDouble())
        }
        // 토큰이 연산자인 경우
        else if (token in operators) {
            // 스택에서 두 개의 피연산자를 pop하여 해당 연산자로 계산하고 결과를 다시 스택에 push
            val operand2 = stack.pop()
            val operand1 = stack.pop()
            val result = operators[token]!!.doOperate(operand1, operand2)
            stack.push(result)
        }
        // 그 외의 경우는 유효하지 않은 토큰이므로 예외 발생
        else {
            throw IllegalArgumentException("후위 표기법에서 유효하지 않은 토큰: $token")
        }
    }

    // 스택에는 최종 계산 결과가 남아 있어야 함
    return if (stack.size == 1) {
        stack.pop()
    } else {
        throw IllegalArgumentException("유효하지 않은 후위 표기법")
    }
}

위의  후위 표기법 리스트 ["3", "4", "5", "*"]를 예시로들어보자면,

1. 스택 초기 상태: []
2. token == "3": 숫자인 경우, 스택에 push
   • 스택: [3.0]
3. token == "4": 숫자인 경우, 스택에 push
   • 스택: [3.0, 4.0]
4. token == "5": 숫자인 경우, 스택에 push
   • 스택: [3.0, 4.0, 5.0]
5. token == "*": 연산자인 경우, 스택에서 두 개의 피연산자를 pop하고 해당 연산자로 계산한 결과를 스택에 push
   • 스택: [3.0, 20.0]
6. 최종 스택 상태: [20.0]

이렇게 스택이 완성된다.

완성본은 해당 링크에 업로드하였다.

https://github.com/ellycrab/calculatorHomework/tree/Submit1/Calculator5/app/src/main/java/com/ellycrab/calculatorlv5