[JAVA] 알고리즘 : Stack- 후위식 연산(postfix)

import java.util.*;

public class Main {
    public int solution(String str) {
        int answer=0;
        Stack<Integer> stack = new Stack<>();

        for(char x : str.toCharArray()){
            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 sc = new Scanner(System.in);
        String str = sc.next();
        System.out.println(T.solution(str));
    }
}

 

입력된 후위식 연산이 352+*9- 라고 하자.

숫자 3, 5, 2 를 차례대로 스택에 넣는다. 

연산자를 만났을 때 가장 위에 있는 2를 rt, 5를 lt로 하고 계산한후, 스택에 집어 넣는다.

스택에 3, 7(5+2) 순서로 남아있게 되고 다시 *를 만났으니 계산하면 3*7=21이 된다.

그리고 숫자 9를 넣고 21-9 를 하여 12가 답이된다.