후위식 연산(postfix)

설명

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.

만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 12입니다.

 

입력

첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다.

식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어진다.

 

출력

연산한 결과를 출력합니다.

 

예시 입력 1 

352+*9-

 

예시 출력 1

12

 

 

문제 해결

 

후위식 연산을 하기 위해 연산자가 나오면 연산자를 기준으로 앞에 두 숫자를 연산해서 저장하고, 이 과정을 반복해 가는 걸로 문제를 접근했다.

 

바로 가보쟈. 연산을 String으로 입력받아 저장해주고, Integer 형의 스택을 만들어준다. 

Scanner in = new Scanner(System.in);
String input = in.nextLine();

Stack<Integer> stack = new Stack<>();
int result = 0;

 

스택은 LIFO 구조이므로 숫자만 스택에 차례로 넣다가 연산자를 만나면 pop을 연속 2번 해주며 연산하고 그 결과를 저장하는 방식을 생각했다. 생각은 쉬웠지만, Character.isDigit()의 함수를 생각해내지 못해 한 번 막혔다.

Character.isDigit(char ch) 은 char형이 숫자인지를 판별해주는 함수이다.

숫자인 경우만 스택에 push를 하는데, 이 때 우리는 입력 받은 값을 문자로 추출하지만 후에 연산은 숫자로 해야하므로

-'0'을 해주어 문자를 숫자로 변환해주는 작업을 꼭 해주어야 한다. 

그리고 숫자가 아닌 경우, 즉 연산자를 만난 경우에는 pop을 두 번 하여 최근에 push된 숫자 두 개를 꺼내와 해당 연산을 해주고 스택에 다시 넣어주면 된다.

for (int i = 0; i < input.length(); i++) {
    if(Character.isDigit(input.charAt(i))) { //숫자인 경우만 스택에 push
        stack.push(input.charAt(i)-'0'); // 문자 -> 숫자
    } else {
            int num2 = stack.pop();
            int num1 = stack.pop();
            if (input.charAt(i) == '+') {
                result = num1 + num2; // 7
            }
            else if (input.charAt(i) == '-') {
                result = num1 - num2;
            }
            else if (input.charAt(i) == '*') {
                result = num1 * num2;
            }
            else if (input.charAt(i) == '/'){
                result = num1 / num2;
            }
            stack.push(result);
        }
    }

 

 

마지막까지 연산을 끝냈다면 스택에 남아있는 마지막 값을 pop해서 출력해주면 된다.

System.out.println(stack.pop());

 

 

최종 코드

 

import java.util.Scanner;
import java.util.Stack;

public class P04_후위식연산 {
    public static void main(String[] args) {

        /** 연산자가 나오면 앞에 두 숫자를 연산해서 저장.**/
        // 3 5 2 + * 9 -

        Scanner in = new Scanner(System.in);
        String input = in.nextLine();

        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for (int i = 0; i < input.length(); i++) {
            if(Character.isDigit(input.charAt(i))) { //숫자인 경우만 스택에 push
                stack.push(input.charAt(i)-'0'); // 문자 -> 숫자
            } else {
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    if (input.charAt(i) == '+') {
                        result = num1 + num2; // 7
                    }
                    else if (input.charAt(i) == '-') {
                        result = num1 - num2;
                    }
                    else if (input.charAt(i) == '*') {
                        result = num1 * num2;
                    }
                    else if (input.charAt(i) == '/'){
                        result = num1 / num2;
                    }
                    stack.push(result);
                }
            }

        System.out.println(stack.pop());
    }
}