백준 1935: 후위 표기식 2(java)

문제

---

풀이

 

스택을 사용하면 쉽게 해결할 수 있는 문제다. 입력된 수식을 스캔하며 숫자가 나오면 스택에 push하고, 연산자가 나오면 pop하여 가장 최근에 삽입된 두 숫자로 해당 연산을 수행한 뒤 그 결과를 다시 스택에 push하면 된다.

스택으로 후위 표기 수식 계산 참고

스택의 응용: 후위 표기 수식 계산

(위 게시글은 C를 기준으로 작성되었지만 알고리즘은 동일하다)

 

이번에 처리할 문자 ch에 대한 switch문을 사용한다. ch가 +, -, *, /일 때와 문자일 때를 구분하여 작성하였고다. ch가 연산자일 때는 스택에서 pop하여 연산을 수행하고 그 결과를 push하며, 문자일 때는 입력받은 숫자 배열 nums에서 적절한 인덱스의 값을 가져와 push한다.

switch(ch) {
	case '+':
		stack.add(stack.pop()+stack.pop());
		break;
	case '-':
		double n1=stack.pop();
		double n2=stack.pop();
		stack.add(n2-n1);
		break;
	case '*':
		stack.add(stack.pop()*stack.pop());
		break;
	case '/':
		double n3=stack.pop();
		double n4=stack.pop();
		stack.add(n4/n3);
		break;
	default:
		stack.add(nums[ch-'A']);
}

 

전체 코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Stack<Double> stack=new Stack<>();
		
		int N=Integer.parseInt(br.readLine());
		String equation=br.readLine();
		
		double[] nums=new double[N];
		for(int i=0; i<N; i++) {
			nums[i]=Integer.parseInt(br.readLine());
		}
		
		for(int i=0; i<equation.length(); i++) {
			char ch=equation.charAt(i);
			
			switch(ch) {
			case '+':
				stack.add(stack.pop()+stack.pop());
				break;
			case '-':
				double n1=stack.pop();
				double n2=stack.pop();
				stack.add(n2-n1);
				break;
			case '*':
				stack.add(stack.pop()*stack.pop());
				break;
			case '/':
				double n3=stack.pop();
				double n4=stack.pop();
				stack.add(n4/n3);
				break;
			default:
				stack.add(nums[ch-'A']);
			}
		}
		System.out.printf("%.2f", stack.pop());
	}
}

스택을 별도로 구현하지 않고 JDK에서 기본 제공되는 Stack 컬렉션을 사용하였다.