설명
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.
후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.
출력
계산 결과를 소숫점 둘째 자리까지 출력한다.
예시 입력
예시 출력
5
ABC*+DE/-
1
2
3
4
5
JavaScript
복사
6.20
JavaScript
복사
풀이 과정
Java의 컬렉션 기본기를 다지고자, 자료구조와 관련된 알고리즘 문제를 풀고 있습니다. 이번 문제는 후위 표기식이라는 문제인데, 우선 후위 표기식의 정의 부터 알아볼까요?
연산자가 ‘후(뒤)'에 위치하는 '후'위 표기식
예를 들어, 1+1 을 후위 표기식으로 표현하면 11+ 됩니다.
간단하게 예제에 나와 있는 후위 표기식을 볼까요?
우선 ABC*+DE 라는 표기식이 주어지고, 입력하는 순서대로 A, B, C … 에 넣어주는 형식입니다.
모두 다 입력하였다면 123*+45/-가 되겠네요!
후위 표기식은 단순하게 연산자가 나올 때 계산이 작동한다고 생각하시면 됩니다.
예를 들어, 1..23* 가 나왔다면 2*3을 연산하고 결과 값을 다시 스택에 넣어줍니다. (16 …)
순서대로 계산하면 다음과 같습니다.
1.
123*+45/-
2.
16+45/-
3.
745/-
4.
70.8-
5.
6.2
규칙이 보이시나요? 연산자의 바로 앞 두 숫자를 계산 한뒤 다시 스택에 넣어줍니다.
최종 코드
package baekjoon.data_structure.stack;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class _1935 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String expression = br.readLine();
double[] values = new double[N];
for (int i = 0; i < N; i++) {
values[i] = Double.parseDouble(br.readLine());
}
Stack<Double> stack = new Stack();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (Character.isLetter(ch)) {
stack.push(values[ch - 'A']);
} else {
double operand2 = stack.pop();
double operand1 = stack.pop();
switch (ch) {
case '+':
stack.push(operand1 + operand2);
break;
case '-':
stack.push(operand1 - operand2);
break;
case '*':
stack.push(operand1 * operand2);
break;
case '/':
stack.push(operand1 / operand2);
break;
}
}
}
System.out.printf("%.2f", stack.peek());
}
}
JavaScript
복사
