[Swift] 백준 1935번 - 후위 표기식2

백준 문제 모음

문제 링크

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

1935번: 후위 표기식2

 

문제

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

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26)가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는 값 , 5번째 줄에는 C... 이 주어진다, 그리고 피연산자에 대응하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소수점 둘째 자리까지 출력한다.

입출력 예시

알고리즘 분류

• 자료 구조
• 스택

---

문제 풀이

• 후위표기식이란 피연산자가 먼저 쓰이고, 그 뒤로 연산자가 나오는 표기식이다.
  • ex) 4*(7+2) => 4 7 2 + *
• 피연산자의 개수 n과 후위표기식 input를 입력받는다.
• 피연산자를 순서대로 담을 Double형 배열 stack과 각 피연산자에 대응하는 값을 받을 Double형 배열 arr를 선언한다.
• 0부터 n까지 arr에 피연산자에 대응하는 값을 저장한다.
• 입력받은 후위표기식을 switch문을 사용하여 각 요소에 해당하는 동작을 수행한다.
  • + 라면 마지막 요소 2개를 더하고, - 라면 마지막에서 2번째 요소에서 마지막 요소를 뺀다.
  • * 라면 마지막 요소 2개를 곱하고, / 라면 마지막에서 2번째 요소에서 마지막 요소를 나눈다.
  • 연산자가 아니고 피연산자 라면, index에 현재 피연산자의 아스키코드 값에서 65를 빼서 저장한다. (A=0... Z=25)
    • 이후 stack에 arr의 index번 째 요소를 추가한다.
      • A부터 순서대로 대응되는 값을 stack에 넣을 수 있도록 index는 아스키코드값에서 65를 빼서 사용한다.
      • ex) A B A + +, A=1 B=2인 경우 arr = [1, 2]가 저장된다. 계산은 1+2+1이기 때문에 인덱스를 각 알파벳에 대응될 수 있도록 아스키코드를 사용하여 계산한다.

소스코드

import Foundation

let n = Int(readLine()!)!
let input = readLine()!.map{$0}
var stack = [Double]()
var arr = [Double]()

for _ in 0..<n {
    arr.append(Double(readLine()!)!)
}

for i in input {
    switch i {
    case "+":
        stack.append(stack.removeLast() + stack.removeLast())
    case "-":
        let f = stack.removeLast()
        stack.append(stack.removeLast() - f)
    case "*":
        stack.append(stack.removeLast() * stack.removeLast())
    case "/":
        let f = stack.removeLast()
        stack.append(stack.removeLast() / f)
    default:
        let index = i.asciiValue! - 65
        stack.append(arr[Int(index)])
    }
}
print(String(format: "%.2f", stack[0]))