섹션 5. Stack, Queue - 4. 후위식 연산 (Postfix)

📌 문제 설명

후위 연산식(Postfix Notation)이 주어지면 이를 계산하여 결과를 출력하는 프로그램을 작성합니다.

예를 들어, 중위 표기식 3 * (5 + 2) - 9는 후위 표기식으로 352+*9-가 되고, 계산 결과는 12가 됩니다.

---

📝 입력 & 출력

입력

• 첫 번째 줄에 후위 연산식이 주어집니다.
• 연산식의 길이는 50을 넘지 않으며, 식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어집니다.

출력

• 계산된 결과를 출력합니다.

---

🔹 예제 입력 & 출력

예제 입력 1

352+*9-

 

예제 출력 1

12

---

💡 해결 방법

• 후위 연산식은 연산자보다 피연산자가 먼저 나오는 구조입니다.
• 숫자가 나오면 Stack에 push하고, 연산자가 나오면 Stack에서 두 개의 숫자를 pop하여 연산한 뒤 다시 push합니다.
• 식의 끝까지 반복하면 Stack에는 최종 결과 하나만 남게 됩니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.*;

public class Problem4 {
	public int solution(String s) {
		int rt=0, lt=0;
		Stack<Integer> stack = new Stack<>();
		for(char x: s.toCharArray()) {
			if(Character.isDigit(x)) stack.push(x-48);
			else {
				rt = stack.pop();
				lt = stack.pop();
				if(x == '+') stack.push(lt + rt);
				else if(x == '-') stack.push(lt - rt);
				else if(x == '*') stack.push(lt * rt);
				else if(x == '/') stack.push(lt / rt);
			}
		}
		return stack.pop();
	}

	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner kb = new Scanner(System.in);
		System.out.print(T.solution(kb.next()));
		kb.close();
	}
}

---

📖 코드 설명

if(Character.isDigit(x)) stack.push(x-48);

• 문자를 숫자로 변환해 Stack에 저장합니다.

rt = stack.pop();
lt = stack.pop();

• 연산을 위해 숫자 두 개를 Stack에서 꺼냅니다.

if(x == '+') stack.push(lt + rt);

• 해당 연산자를 적용한 결과를 다시 Stack에 저장합니다.

---

⏳ 시간 복잡도 분석

• 연산식 길이가 최대 50이므로 O(N) 시간 복잡도로 처리할 수 있습니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런