[알고리즘] 후위표기식

 

후위표기식이란?

일반적으로 사용하는 사칙연산은 피연산자(숫자) 사이에 연산자(+-*/) 가 들어가는 형태로 중위표기식 이라고 한다.

그러나 후위표기식은 피연산자가 먼저 쓰이고, 그 뒤로 피연산자가 나오는 형태를 말한다.

예를들어, 4 7 2 + * 일 경우 읽는 법은

 

1.  왼쪽부터 순차적으로 읽으면서 연산자를 찾는다.

2.  +연산자를 찾았다. +연산자를 기준으로 앞쪽 두개의 피연산자 7, 2 를 더한다.

3.  연산을 진행하고 나면 연산된 값을 적어둔다. 4 9 *

4.  다시 순차적으로 연산자를 찾는다.

5.  *연산자를 찾았다. 앞쪽 두개의 피연산자를 이용하여 연산을 진행한다.

6.  연산결과는 36

 

 

1. 후위표기식2 문제 (1935번)

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));
		
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		double[] operand = new double[n]; //숫자 피연산자를 저장
		
		char[] inputVal = br.readLine().toCharArray(); //후위 표기식을 저장
		
		Stack<Double> stack = new Stack<>(); //후위 표기식의 알파벳을 통해 도출한 숫자 피연산자를 저장
		
		for(int i=0; i<n; i++) {
			
			operand[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i=0; i<inputVal.length; i++) {
			
			if(Character.isAlphabetic(inputVal[i])) { //알파벳이라면
				
				int index = (int)inputVal[i]-65;
				stack.push(operand[index]);
				
			}
			else {//연산자라면
				
				Double result = 0.d;
				Double pop1 = stack.pop();
				Double pop2 = stack.pop();
				
				if(inputVal[i]=='+') {
					result = pop2 + pop1;
				}
				
				if(inputVal[i]=='-') {
					result = pop2 - pop1;
				}
				
				if(inputVal[i]=='*') {
					result = pop2 * pop1;
				}
				
				if(inputVal[i]=='/') {
					result = pop2 / pop1;
				}
				
				stack.push(result);
			}
		}
		
		System.out.format("%.2f", stack.pop());
	}
}