[자료구조] 후위식 연산 (postfix)

 

 

 

설명

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.
만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 12입니다.

 

 

 

입력

첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다.
식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어진다.

 

 

 

출력

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

 

 

 

예시 입력1

352+*9-

 

 

 

예시 출력1

12

 

 

 

 

풀이

숫자는 그대로 두고 연산자만 뒤로 빼는 것을 후위식 연산이라고 한다.

숫자이면 스택에 push한다.

• 숫자인지 확인할 때는 Character 클래스의 isDigit을 이용한다.
• 스택에 넣을 때는 문자가 아니라 숫자로 넣어야 한다. 문자 '0'은 아스키 넘버로 48이다. 따라서 (문자 - 48) 를 스택에 push한다.

 

연산자이면, 스택에서 총 2번을 pop한다. (한 번의 연산을 할 때는 두 개의 숫자가 필요하므로)
첫 번째로 꺼낸 값이 rt, 두 번째로 꺼낸 값이 lt이다. (두번째에 pop된 값이 연산을 당하는 것이다.)
계산한 값을 스택에 push한다.


연산이 끝나면 스택에는 하나의 숫자만 남아있을 것이다. 마지막 남은 수인 stack.get(0) 을 리턴하면 된다.

 

 

 

 

코드

package inflearn._5_4;

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

public class Main {

    public static int solution(String str) {

        Stack<Integer> stack = new Stack<>();

        for(char x: str.toCharArray()) {
            if (Character.isDigit(x)) { // 숫자이면 push
                stack.push(x - 48); // 문자를 숫자로 바꾸고 push
            }
            else {
                int rt = stack.pop();
                int lt = stack.pop(); // 두번째로 pop 된 값이 연산을 당함

                if (x == '+') stack.push(lt + rt);
                else if (x == '-') stack.push(lt - rt);
                else if (x == '*') stack.push(lt * rt);
                else if (x == '/') stack.push(lt / rt);
            }
        }

        return stack.get(0);

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();

        bw.write(sb.append(solution(str)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}