실력키우기 후위표기법(JAVA)

1221 : 후위표기법

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 527회    시도횟수: 2053회   

우리가 일반적으로 사용하는 계산방식은 중위표기법(Infix Notation)이라 하는데, A + B와 같이 피연산자 'A'와 'B' 중간에 연산자 '+'가 위치하여 이렇게 불린다. 컴퓨터공학에서는 후위표기법 (Postfix Notation)을 많이 사용하는데, 후위표기법은 A B + 와 같이 피연산자 'A'와 'B'의 뒤에 연산자 '+'가 위치한 표기법을 말한다.

중위표기법에서 (5+8)*2 와 같은 수식은 '*'가 '+'보다 연산자 우선순위가 높으므로 앞의 수식 에서처럼 5+8 을 먼저 계산해야한다면 괄호를 사용해야한다. 하지만 수식 (5+8)*2 을 후위표기법으로 바꾸면 5 8 + 2 * 와 같이 되어, 후위표기법은 괄호가 없이도 연산자의 우선 순위 를 명확히 할 수 있다는 장점이 있다. 이런 이유로 소프트웨어로 구현되는 계산기들은 후위표기 법을 많이 사용한다. 그럼 후위표기법의 수식을 입력 받아 계산하는 프로그램을 작성해 보자. 또한, 계산기는 예외처리에도 신경을 써야 하므로 만약 0으로 나누는 경우가 발생하면 계산을 중단 한다.

 

입력의 첫 줄에는 총 입력되는 연산자와 피연산자의 개수의 합 M(3≤M≤11 )이 입력되며, 그 다음줄에 M개의 연산자와 피연산자가 한 칸씩의 공백 을 두고 입력된다. 피연산자 X 는 0≤X≤9 의 범위를 가지는 정수이며, 연산자는 사칙연산인 '*', '/', '+', '-'의 네 가지가 입력된다. 0으로 나누는 경우는 입력되지 않는다.

피연산자나 연산자가 부족한 경우와 같이 완전하지 않은 수식은 입력되지 않는다. 나눗셈 연산의 경우, 소수점 이하는 버리고 몫만 계산되며 정수로 나타난다. 예를 들어 10 3 / 은 3이 된다.

[Copy] 3 2 3 +

[Copy] 5

[Copy] 3 9 3 /

[Copy] 3

[Copy] 5 5 8 + 2 *

[Copy] 26

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

/**************************************************************     Problem: 1221     User: a132034     Language: Java     Result: Success     Time:160 ms     Memory:9348 kb ****************************************************************/     import java.util.Scanner; import java.util.Stack;   public class Main {     private static Scanner sc;     public static int[] result;     public static void main(String[] args) {         sc = new Scanner(System.in);         Stack<Integer> op = new Stack<Integer>();         int N = sc.nextInt();         int a,b;         sc.nextLine();                   String str = sc.nextLine();                   char[] arr = str.toCharArray();                   for(int i = 0 ; i <  N; ++ i)         {             Character item = arr[2*i];                           //숫자인 경우             if( item >= '0' && item <= '9' )             {                 op.add(Integer.parseInt(item.toString()));             }else{ //연산자인 경우                 b = op.pop();                 a = op.pop();                 if(item == '+'){                     op.push((a+b));                 }else if(item == '-'){                     op.push((a-b));                 }else if(item == '*'){                     op.push((a*b));                 }else if(item == '/'){                     op.push((a/b));                 }             }         }                   System.out.println(op.pop());                         } }

푸는 중 특이한 것은 char의 wrapping class인 Character class를 사용했다는 것.(toString 메서드를 사용해서 String으로 변경해야 Integer.ParseInt를 사용 가능하기 때문.)

그 외에는 제약조건으로 온전한 입력이 주어지고, 0~9까지의 숫자(자릿수가 1개)가 주어지기 때문에 특별히 예외처리나 복잡하게 구현할 필요가 없었다. 

우선 여기서 후기표기법은 

1. 입력 버퍼가 있다. 

2. 입력 버퍼 중 숫자를 넣어줄(피연산자) 스택을 사용한다. 

이렇게 두 가지만 기억하면 더욱 복잡한 제약사항이 있더라도 어렵지 않을 것이다. 

풀이는

1. 입력 버퍼에서 하나씩 값을 꺼내온다.

2. 숫자(피연산자)라면 - 스택에 넣어준다.

   연산자라면 - 스택에서 연산자에 맞게 값을 꺼내 연산한 후 다시 스택에 넣어준다. 

3. 모든 버퍼가 비워질 때 스택에 정답이 들어가 있다. 

여기서 헷갈릴 수 있는 것은 

예를 들어 

1 2 + 의 값이 들어갈 경우 

스택에는 

1 2 순서로 들어가게 될 것이다. 

꺼낼 경우 1 2 의 순서가 아닌 2 1의 순서로 꺼내지게 된다.(Last in First Out = First In Last Out) 

+, -, *의 경우 사실 위치가 크게 상관이 없으나, /연산의 경우 답이 달라질 수 있으므로 주의한다.