인간이 사용하는 연산식은 피연산자 사이에 연산자가 위치하는 "중위 표기식"이다.
예컨대, 1 + 1 = 2 와 같다.
그러나 컴퓨터는 중위 표기식을 맞이하면, 1 + 에서 무엇을 더해야할 지 알 수 없기 때문에, 연산자가 피연산자들의 뒤에 있는, "후위 표기식"을 통해서 연산을 실시한다.
따라서 컴퓨터가 연산을 하기 위해서는 1. 중위 표기식을 입력 받고 2. 중위 표기식을 후위 표기식으로 변환한 뒤 3. 연산 결과를 출력하는 방식의 프로세스를 거치게 된다.
본 문제는 상기한 프로세스를 구현하는 문제로, 연산자가 나올 때 비로소 이전에 저장한 피연산자들을 꺼내 연산을 해야하기 때문에 Stack을 사용한다.
package BOJ.dataStructure.stack;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Stack;
public class BOJ1935 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 피연산자의 갯수
int n = Integer.parseInt(br.readLine());
// 후위표기식
String postfix = br.readLine();
// 피연산자들에 대응하는 값을 넣기 위한 배열(나누기 연산 때문에 double)
Double[] doubleArr = new Double[n];
// 배열에 입력
for(int i = 0; i < doubleArr.length; i++) {
doubleArr[i] = Double.parseDouble(br.readLine());
}
br.close();
// 후위표기식의 원자들을 대입하기 위한 임의의 char형 변수 선언
char ch = 'a';
// 후위표기식을 계산하기 위한 스택 변수 선언
Stack<Double> stack = new Stack<>();
// Double-Ended Queue 도 사용 가능. 현재 자바에서는 여러 이유로 스택을 대신하여 데큐의 사용을 권장하고 있음.
// ArrayDeque<Double> deque = new ArrayDeque<>();
// 후위표기식을 하나씩 쪼갬
for(int i = 0; i < postfix.length(); i++) {
ch = postfix.charAt(i);
// 피연산자일 경우
if(ch >= 'A' && ch <= 'Z') {
// 대응되는 숫자로 치환해 스택에 push
// 이때 인덱스값은 ch-'A'
// A, B, C ... 는 순서대로 doubleArr[0], doubleArr[1], doubleArr[2] ... 으로 치환되므로
stack.push(doubleArr[ch-'A']);
} else { // 연산자일 경우
// 스택에 넣었던 피연산자 2개를 꺼낸 뒤 연산 결과를 push
double d1 = stack.pop();
double d2 = stack.pop();
// 연산 결과를 담을 변수 선언
double d3 = 0.0;
// 스위치문 통해 연산자에 따른 연산 실시
switch(ch) {
case '+':
d3 = d2 + d1;
break;
case '-':
d3 = d2 - d1;
break;
case '*':
d3 = d2 * d1;
break;
case '/':
d3 = d2 / d1;
}
// 연산 결과를 다시 스택에 push
stack.push(d3);
}
}
// System.out.printf("%.2f", deque.pollLast());
// 조건에 맞게 소숫점 둘째 자리까지 표현
// .peek() 으로 가장 위 element를 반환
System.out.printf("%.2f", stack.peek());
}
}
'코딩테스트 > Java' 카테고리의 다른 글
[BaekJoon][자료 구조][Stack][Java] 2563: 색종이 (0) | 2024.08.10 |
---|---|
[BaekJoon][자료 구조][Stack][Java] 10799 : 쇠막대기 (0) | 2024.08.10 |
[BaekJoon][자료 구조][Stack][Java] 10773 : 제로 (0) | 2024.08.10 |
[BaekJoon][자료구조][Java] Stack 구현하기 (0) | 2024.08.10 |
[BAEKJOON] 2798.블랙잭 (1) | 2024.03.14 |