자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Stack,Queue_후위식 연산_Stack)

 

 

4. 후위식 연산(postfix)

 

예시 입력 1 

352+*9-

예시 출력 1

12

 

 

후의식이란 숫자가 앞에있고 연산자만 뒤에 빠지는 것 입니다.

중의식 : 5+3, 5-3

후의식 : 53+, 53-

 

후의식으로 할때 빼기를 당하는 숫자는 왼쪽에 있는 숫자입니다.

 

 

숫자면 stack에 푸시하고 연산자를 만나면 꺼냅니다. 먼저 뺀게 오른쪽, 나중에 뺀게 왼쪽,

왼쪽에서 오른쪽을 빼야 합니다.

그래서 후의식을 다 연산하고 나면 스택에 숫자 딱 하나 남아있습니다.

 

강의 풀이 (Time: 155ms Memory: 27MB)

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

public class Main {

    public int solution(String str) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        for (char x : str.toCharArray()) {
            // x가 숫자인지 판단, 0이 아스키 넘버로 48이다. 48 = '0'
            if (Character.isDigit(x)) stack.push(x - 48);
            else {
                int rt = stack.pop();
                int lt = stack.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);

            }
        }
        answer = stack.get(0);
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        System.out.println(T.solution(str));
    }
}