[자료구조] 스택으로 후위표기식 계산하기 :: 늦깎이 IT

 이전 포스팅에서는 스택을 활용해서 중위 표기법을 후위 표기법으로 변환했다.

이 포스팅을 읽기 전에 이전 포스팅일 먼저 읽어보기 바란다.

2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 구현하기 :: 늦깎이 IT

[후위 표기식 계산하기]

1. 피연산자는 무조건 스택에 저장한다.

2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다. 단, 여기서 주의할 점은 스택에서 먼저 꺼낸 피연산자가 연산자의 뒤에 위치해야한다.

3. 계산 결과는 다시 스택에 넣는다.

후위표기식을 만들었으면, 계산하는 것은 어렵지 않다.

우선, "3 2 4 x +" 와 같은 후위 표기법이 있다고 가정해보자. 후위 표기식에서는 연산자를 만나면 그 연산자와

앞의 두 개의 피연산자를 계산하는 방식이다. 

• 3 2 4 x +  : x를 만났으면, 2 x 4를 계산하고 그 값으로 바꿔준다
• 3 8 + : 그 다음 +를 만났으면 3 + 8을 계산하고 그 값으로 바꿔준다.
• 11 : 계산을 마쳤다.

[후위 표기식 계산 소스 코드]

[후위표기식 변환 및 계산 전체코드 확인하기]

import java.util.Stack;
 
public class PostCalculator {
 
    public static int calPostfix(String input) {
 
        Stack<Integer> stack = new Stack<>();
        int len = input.length();
 
        for (int i = 0; i < len; i++) {
 
            char op = input.charAt(i);
 
            if (op >= '1' && op <= '9') {
                stack.push(op - '0');
            } else {
 
                int op2 = stack.pop();
                int op1 = stack.pop();
 
                switch (op) {
 
                case '+':
                    stack.push(op1 + op2);
                    break;
                case '-':
                    stack.push(op1 - op2);
                    break;
                case '*':
                    stack.push(op1 * op2);
                    break;
                case '/':
                    stack.push(op1 / op2);
                    break;
                }
            }
        }
        return stack.pop();
    }
}