[백준/BOJ] 1935번: 후위 표기식2

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

해설

후위 표기식을 중위 표기식으로 변환하여 계산을 하면 된다.

 

후위 표기법은 연산자가 피연산자들의 뒤에 위치한다.

예제의 ABC*+DE/-를 중위 표기식으로 바꿔보면 A+B*C-D/E가 된다.

 

스택을 이용하여 문제를 풀어보자.

표기식에는 피연산자와 연산자가 존재한다.

 

식의 길이만큼 반복문을 돌린다.

피연산자를 만났다면 스택에 피연산자를 넣어준다.

연산자가 나왔다면 스택의 위 두개를 계산해주면 된다.

 

그림과 같이 봐보자.

소스 코드

import java.text.DecimalFormat
import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val str = readLine()
    var save = ""
    var arr = DoubleArray(n)
    repeat(n) { i -> arr[i] = readLine().toDouble() }

    val stack = Stack<Double>()
    for(i in str) {
        if(i in 'A'..'Z') stack.add(arr[(i-65).toInt()])
        else {
            val a = stack.pop()
            val b = stack.pop()
            when (i) {
                '+' -> stack.add(b + a)
                '-' -> stack.add(b - a)
                '*' -> stack.add(b * a)
                '/' -> stack.add(b / a)
            }
        }
    }
    val df = DecimalFormat("#0.00")
    println(df.format(stack.pop()))
}