[스택] 코딩테스트 문제 TIL (후위 표기식2) - 백준 1935번

오늘 문제는 스택 자료구조 하면 떠오르는 문제죠. 후위 표기식 문제입니다. 그럼 살펴볼까요?

---

1. 오늘의 학습 키워드

• 스택
• 후위 표기식

---

2. 문제: 후위 표기식2

• 단계: 🥈실버 3단계
• 주제: 자료 구조, 스택
• 출처: https://www.acmicpc.net/problem/1935

문제

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

입력

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

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

출력

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

예제 입력 1 복사

5
ABC*+DE/-
1
2
3
4
5

예제 출력 1 복사

6.20

예제 입력 2 복사

1
AA+A+
1

예제 출력 2 복사

3.00

---

3. 문제 풀이

Step1. 문제 이해하기

오늘 문제는 주어진 후위 표기식을 해결하는 문제입니다.

후위 표기식의 원리만 잘 파악한다면 충분히 해결하는데 어려움이 없는 문제입니다.

후위 표기식이 뭔지 살펴보기전 문제의 입출력을 먼저 알아보도록 하겠습니다.

• Input:
  • 첫째 줄에 피연산자의 개수가 주어집니다. 1이상 26이하 입니다.
  • 둘째 줄에는 후위 표기식이 주어집니다. 여기서 피연산자는 A~Z의 영대문자이며, A부터 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않습니다.
    • 이 길이가 시간 복잡도에 영향을 줄 것으로 보입니다. 길이가 100을 넘지 않기 때문에 충분히 여유가 있을것입니다.
  • 셋째 줄부터 N + 2번째 줄까지는 각 피연산자에 대응하는 값이 주어집니다.
• Output:
  • 후위 표기식의 결과를 출력합니다.

Step2. 문제 분석하기

그럼 후위 표기식에 대해 알아보겠습니다.

후위 표기식은 수식을 표현하는 방법 중 하나로, 연산자가 피연산자 뒤에 위치하는 표기법입니다.

예를 들어, 일반적인 중위 표기식(Infix Notation)인 A+B는 후위 표기식으로는 AB+로 표현됩니다.

후위 표기식의 특징

1. 괄호가 필요 없음:
   • 후위 표기식은 연산의 우선순위와 결합 방향이 명확하기 때문에 괄호가 필요하지 않습니다.
   • 예: (A+B)×C는 후위 표기식으로 AB+C∗로 표현됩니다.
2. 계산 순서가 명확함:
   • 후위 표기식에서는 왼쪽에서 오른쪽으로 순차적으로 처리하며, 연산자를 만날 때마다 스택을 이용해 계산하면 됩니다.
3. 컴퓨터에서 쉽게 처리 가능:
   • 후위 표기식은 중위 표기식보다 계산이 단순하며, 컴퓨터가 이해하기 쉽습니다. 컴파일러가 중위 표기식을 후위 표기식으로 변환하는 것도 이러한 이유에서입니다.

후위 표기식의 예시

1. 간단한 예제

중위 표기식: A+B

후위 표기식: AB+

2. 복잡한 예제

중위 표기식: (A+B)×(C−D)

후위 표기식: AB+CD−∗

3. 숫자로 된 예제

중위 표기식: 3+4 * 5

후위 표기식: 345*+

(곱셈이 덧셈보다 우선순위가 높기 때문)

즉, 연산자들을 피연산자 뒤로 옮기지만 우선순위가 높은 연산자들을 피연산자에 가깝게 두는것입니다.

그렇다면 첫번째 예시를 살펴볼까요?

수식: ABC*+DE/-

해당 수식을 중위 표기식으로 나타내면 다음과 같습니다.

후위 표기식: A + B * C - D / E

피연산자들은 저장해두었다가 연산자 수식이 나오면 최근 피연산자 두 개를 꺼내서 계산을 수행하면 해결할 수 있습니다. 즉, LIFO원리가 적용됩니다.

따라서, 스택 자료 구조를 활용해서 구현하면 해결됩니다.

스택 자료구조의 연산들의 시간 복잡도는 상수이기 때문에 전체 후위 표기식의 $O(N)$의 시간 복잡도로 구현이 가능합니다.

Step3. 코드 설계

1. 입력 처리:
   • 피연산자의 개수 N과 후위 표기식 문자열 equation을 입력받습니다.
   • 각 피연산자에 대응하는 값을 입력받아 num_list에 저장합니다.
2. 스택 초기화:
   • 후위 표기식은 LIFO 구조로 처리되므로, 스택을 초기화합니다.
3. 후위 표기식 순회:
   • 문자열 equation을 한 글자씩 순회하며 처리합니다.
   • 문자가 영문 대문자(A~Z)라면 대응하는 숫자를 스택에 push합니다.
   • 문자가 연산자(+, -, *, /)라면 스택에서 두 개의 값을 pop하여 연산 후 결과를 다시 스택에 push합니다.
4. 결과 출력:
   • 후위 표기식 처리가 끝나면 스택에 남아 있는 하나의 값이 최종 결과입니다.
   • 이 값을 소수점 둘째 자리까지 포맷팅하여 출력합니다.

Step4. 코드 구현

import sys
N = int(sys.stdin.readline().strip())
equation = sys.stdin.readline().strip()
stack = []
num_list = [0] * N
for i in range(N):
    num_list[i] = int(sys.stdin.readline().strip())
    
for i in equation:
    if 'A' <= i <= 'Z':
        stack.append(num_list[ord(i) - ord('A')])
    else:
        str2 = stack.pop()
        str1 = stack.pop()
        
        if i == '+':
            stack.append(str1 + str2)
        elif i == '-':
            stack.append(str1 - str2)
        elif i == '*':
            stack.append(str1 * str2)
        elif i == '/':
            stack.append(str1 / str2)
print(f"{stack[0]:.2f}")        

코드 설명:

• 피연산자 처리:
  • 후위 표기식에서 A~Z는 대응되는 숫자 값을 의미합니다.
  • ord(i) - ord('A')를 통해 현재 문자가 어떤 피연산자인지 인덱스를 계산합니다.
• 연산자 처리:
  • 스택에서 두 값을 pop한 뒤 연산을 수행합니다.
  • 연산 결과는 다시 스택에 push하여 다음 연산에서 사용할 수 있도록 합니다.
• 출력:
  • 스택의 마지막 값이 계산 결과이므로 이를 소수점 둘째 자리까지 출력합니다.

시간 복잡도:

• 입력 처리:
  • 피연산자 값을 입력받는 데 O(N) 시간이 걸립니다.
• 후위 표기식 계산:
  • 후위 표기식의 길이가 최대 100이므로, 순회하는 데 O(L) (L: 후위 표기식 길이)의 시간이 걸립니다.
  • 각 연산은 스택의 push/pop이므로 O(1)입니다.
• 전체 시간 복잡도: O(L)

결과:

---

4. 마무리

후위 표기식을 계산하는 문제는 스택 자료구조를 활용하여 효율적으로 풀 수 있습니다. 문제의 핵심은 피연산자와 연산자를 구분하고, 연산자를 만날 때마다 스택에서 값을 꺼내 계산하는 방식입니다. 시간 복잡도는 입력 크기와 후위 표기식의 길이에 선형적으로 비례하며, 구현도 간단합니다. 이 문제를 통해 후위 표기식의 원리를 다시 한 번 이해하고, 스택 자료구조를 활용한 문제 해결 능력을 강화할 수 있었습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다.

매일매일 발전하자!!