#1935 : 후위 표기식2

풀이방법

사용된 것:

Stack

 

2022.07.19

후위 표기식은 무조건 앞에서부터 계산하면 올바른 답이 나오도록 되어있다.

그러니 그냥 식을 앞에서부터 탐색하며, 식이 끝날 때까지 아래와 같은 과정을 반복하면 된다.

 

피연산자가 등장하는 동안에는 피연산자들을 스택에 차곡차곡 쌓다가,

연산자가 등장하면 즉시 그 연산자의 바로 직전에 있는 두 개의 피연산자 즉 스택의 top과 top 바로 아래에 있는 피연산자 두 개를 꺼내온 뒤, 그 두 개를 가지고 연산을 한 값을 다시 스택에 쌓아주면 된다.

 

등장한 연산자가 곱셈/나눗셈인지, 덧셈/뺄셈인지는 신경 쓸 필요 없다. 그들 사이의 우선순위까지 모두 고려하여 그냥 앞에서부터 계산하면 되도록 정렬해놓은 것이 바로 후위 표기식이기 때문이다.

 

코드

Java(2022.07.19)

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{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//입력값 읽어오기
		int n = Integer.parseInt(br.readLine());
		char[] ex = br.readLine().toCharArray();
		double[] nums = new double[n];
		for(int i=0; i<n; i++) nums[i] = Double.parseDouble(br.readLine());
		
		//계산하기
		//스택 선언
		Stack<Double> stack = new Stack<Double>();
		//식의 앞부터 살피기
		for(char c: ex) {
			//피연산자의 경우
			if(c>='A' && c<='Z') {stack.add(nums[c-'A']); continue;}
			//연산자의 경우
			double a = stack.pop();
			double b = stack.pop();
			switch(c) {
				case '+': 
					stack.add(b+a);
					break;
				case '-':
					stack.add(b-a);
					break;
				case '*':
					stack.add(b*a);
					break;
				case '/':
					stack.add(b/a);
					break;
			}
		}
		
		System.out.printf("%.2f", stack.pop());
		

	}

}