스택의 활용 : 수식의 괄호쌍

수식의 괄호 쌍

주어진 괄호 문자열이 올바른지 판단하는 문제

 

해결방법

문자열을 앞에서부터 읽어나가며, 닫는 괄호가 나올 경우 가장 최근에 나왔던 여는 괄호와 짝을 지어본다

이때 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다

가장 나중에 입력된 괄호가 가장 먼저 나오기 때문에 스택구조를 응용하면 해결이 가능하다

여는 괄호가 나오면 스택에 저장하고 닫는 괄호를 만나면 스택 top 값과 비교한다

짝이 지어진다면 pop으로 없애고, 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다

 

BOJ

4949. 균형잡힌 세상

조건 

(), [] 2종류의 괄호로 이루어진 문자열이 올바른 괄호쌍을 이루고 있는지 판단한다

 

해결

1. 여는 괄호가 나오면 스택에 넣는다

2. 닫는 괄호가 나오면 스택 top에 있는 값과 짝을 짓는다 

단 아래 조건에 해당할 경우 바르지 않은 괄호쌍이다

• 스택이 비어있다
• 닫는 괄호와 top에 있는 값이 짝을 이루지 않는다

3. 문자열을 모두 검사한 후 스택에 남아있는 값이 있다면 바르지 않은 괄호쌍으로 판별한다

 

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var string = ""
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val stack = Stack<Char>()

    while (true) {
        var isValid: Boolean = true
        string = readLine()
        if (string == ".")
            break

        for (c in string) {
            when (c) {
                '[','(' -> {
                    stack.push(c)
                }
                ']' -> {
                    if (stack.empty() || stack.peek() != '[') {
                        isValid = false
                        break
                    } else {
                        stack.pop()
                    }
                }
                ')' -> {
                    if (stack.empty() || stack.peek() != '(') {
                        isValid = false
                        break
                    } else {
                        stack.pop()
                    }
                }
                else -> Unit
            }
        }

        if (!stack.empty()) {
            isValid = false
            stack.clear()
        }

        when (isValid) {
            true -> bw.write("yes\n")
            false ->  bw.write("no\n")
        }
    }

    bw.close()
}

 

https://youtu.be/cdjjk-ryPKc