백준 1935 - 후위 표기식2
Updated:
Java
1935 번 - 후위 표기식2
문제
접근 방법
후위 표기식 계산
먼저 후위 표기식을 계산하는 방법을 알야야 하는데,
1. 피연산자면 stack에 push한다
2. 연산자를 만나면 피연산자 2개를 pop한 후 계산하고 push 한다.
이다.
주의할 점은, stack은 LIFO이므로 빼기와 나누기의 계산 순서를 pop 할때 주의하여야 한다.
피연산자 입력
문제에서 입력받는 피연산자는 A부터 차례로 n개로 받는다.
따라서, double Array를 n개만큼 두고, 이후에 피연산자 A ~ Z가 왔을 때 피연산자 - 'A'를 통하여 배열의 인덱스로 접근해 피연산자를 얻는다.
Float? Double?
필자는 처음에 float형으로 계산하였다, 틀렸습니다를 얻었다.
이유는 float은 double보다 소수점 계산 범위가 작기 때문이다.
찾아보니,
웬만하면 double도 쓰지 말고 전부 정수형으로 하는 것이 안전합니다. 물론 실수형 연산이 반드시 필요한 경우라면 double, 간혹 그걸로도 모자라면 long double을 써야 합니다. float는 쓸 일이 아예 없다고 보시면 됩니다.
따라서 앞으로 백준 문제를 풀 때 소수점을 계산해야 한다면, double을 사용하자.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
String str = br.readLine();
double[] opnd = new double[n];
int len = str.length();
//문자열 중 피 연산자들만 분리
for(int i = 0; i < n; i++) {
opnd[i] = stoi(br.readLine());
}
char curC;
// 후위 연산자 계산
Stack<Double> stack = new Stack<>();
Double a, b;
for(int i = 0; i < len; i++) {
curC = str.charAt(i);
if('A' <= curC && curC <= 'Z') {
stack.push(opnd[curC - 'A']);
}
else {
b = stack.pop();
a = stack.pop();
switch(curC) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(a - b);
break;
case '/':
stack.push(a / b);
break;
case '*':
stack.push(a * b);
break;
}
}
}
System.out.printf("%.2f", stack.pop());
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
중위 표기식을 후위 표기식으로 변환
문제와는 관련 없지만, 정리해 두면 좋을 거 같아 정리한다.
1. 피연산자를 만나면 바로 출력한다.
2. 연산자를 만났으며, 스택이 비어있으면 push 한다.
3. 스택에 이미 연산자가 있을 때
a. 현재 연산자 우선순위 > 스택의 연산자 우선순위
스택에 push
b. 현재 연산자 우선순위 <= 스택의 연산자 우선순위
스택의 연산자를 pop한 후, 현재 연산자 push
4. 문자열의 마지막을 만나면 스택을 차례로 pop
괄호가 있을 때
1. 괄호가 여는 괄호이면 무조건 push한다.
2. 괄호가 닫는 괄호이면 stack에서 여는 괄호가 나올 때 까지 pop을 한 후 출력한다.
3. 괄호의 우선순위는 제일 작다. (닫는 괄호가 나올 때 까지 계속 연산자들은 push한다)
총평
후기
float을 사용하여 틀렸으며,
문제의 조건을 잘 못 이해했는지 피 연산자를 입력받을 때 계속 nullPointer 에러가 나와 힘들었다.
