[문제풀이] 05-04. 후위식 연산

인프런, 자바(Java) 알고리즘 문제풀이

Stack, Queue(자료구조) - 0504. 후위식 연산

---

🗒️ 문제

---

🎈 나의 풀이

	private static int solution(String str) {
        Stack<Character> stack = new Stack<>();

        for(int i=str.length(); i>0; i--) {
            char c = str.charAt(i - 1);
            if(c - '0' >= 0 && c - '0' <= 9) {
                char top = stack.peek();

                while(top != '+' && top != '-' && top != '*' && top != '/' && !stack.empty()) {
                    stack.pop();

                    if(stack.peek() == '+') c = (char)((c - '0') + (top - '0') + '0');
                    else if(stack.peek() == '-') c = (char)((c - '0') - (top - '0') + '0');
                    else if(stack.peek() == '*') c = (char)((c - '0') * (top - '0') + '0');
                    else if(stack.peek() == '/') c = (char)((c - '0') / (top - '0') + '0');

                    stack.pop();
                    if(!stack.empty()) top = stack.peek();
                }
            }
            stack.push(c);
        }

        return stack.peek() - '0';
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(solution(str));
    }

---

🖍️ 강의 풀이

    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 kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}

---

💬 짚어가기

해당 문제는 stack을 이용하여 풀 수 있다. 나의 풀이에서는 수식이 담긴 배열을 뒤부터 접근하였다.

1. 연산자인 경우 : 스택에 보관
2. 피연산자이며 스택의 상단에 피연산자가 들어있는 경우
   : 스택의 그 다음 요소(연산자)와 피연산자 2개를 연산한 후 결과를 스택에 보관
3. 피연산자이며 스택의 상단에 연산자가 들어있는 경우 : 스택에 보관

강의에서는 수식이 담긴 배열의 앞부터 접근하였다.

1. 피연산자인 경우 : 스택에 보관
2. 연산자인 경우 : 스택에서 2개의 피연산자를 꺼내어 연산 후 결과를 스택에 보관

☕️ 여담으로

후위식이란 단어에 당연히 뒤에서부터 접근해야한다고 착각하였더니 로직이 더욱 복잡하게 되었다..