[백준] 1935 후위 표기식2 - 자료구조 + 스택 JAVA

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

코드설명

스택 자료구조를 활용합니다.

 

후위표기식 계산방법은,

1. 만약 피연산자('A'~'Z')일경우 Stack에 넣습니다.

2. 만약 연산자('+ * - / ' )일경우 Stack에서 2가지 숫자를 내와서 ( 두번쨰 Stack -  * / + 처음 Stack ) 연산을 진행하고, 다시 해당값을 Stack에 넣습니다.

3. 올바른 후위표기식일경우 모든 연산자를 계산했을경우 Stack에 값이 1개만 남고 해당값을 출력합니다.

 

문제에서 헷갈렷던점은, ABC*+DE/- 와 같이 식이 주어지고, arr[str.charAt(i) - 'A'] 와 같이 알파벳이 26개인점을 활용하여 ABCDE에 피연산자를 사용했던점이 어려운점이었습니다.

 

후위표기식을 만드는방법같은경우는, https://passionfruit200.tistory.com/596 이전에 풀어본 경험이 있습니다.

1. 피연산자 일경우도 StringBuilder에 넣습니다.

2. 연산자일경우 Stack.pop() 과 현재 연산자의 우선순위값을 비교하여 만약 현재 Stack.peek () >= 현재 연산자의 우선순위 라면, Stack이 비어있을때까지 계속해서 Stack.pop을 통해 출력시킵니다. (즉, 만약 Stack에 * 혹은 / 일떄 + 가 들어왔다고 생각해봅시다. 이때 +는 연산자 우선순위가 가장 낮은 '(' 가 나올떄까지 모든 Stack을 비웁니다.

3.  '(' 가 들어오면 스택에 넣습니다.

4. ')' 가 들어오면 '(' 괄호가 나올때까지 연산자 스택에 담아둔 연산을 모두 꺼내어 출력한 후 '(' 괄호는 출력하지 않고 꺼내줍니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int answer = 0;
	public static Stack<Double> stack = new Stack<Double>();
	public static double[] arr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	String str = st.nextToken();
    	arr = new double[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Double.parseDouble(st.nextToken());
    	}
    	
    	double result = 0;
    	for(int i=0;i<str.length();i++) {
    		if( str.charAt(i) >='A' && str.charAt(i) <='Z') {
    			stack.push(arr[str.charAt(i) - 'A']); //arr의 값을 사용하기 위해 다음과 같이 사용합니다.
    		}else { //연산자일경우
    			double num1 = stack.pop();
    			double num2 = stack.pop();
                if (str.charAt(i) == '+') {
                    stack.push(num2 + num1);
                } else if (str.charAt(i) == '*') {
                	stack.push(num2 * num1);
                } else if (str.charAt(i)  == '-') {
                	stack.push(num2 - num1);
                } else if (str.charAt(i)  == '/') {
                	stack.push(num2 / num1);
                }
    		}
    	}
    	
    	System.out.println(String.format("%.2f",  stack.pop()));
    	
    }
    
    
    
}