[알고리즘/Stack] 후위표기식으로 변환 및 계산

3+2*4-9/3의 연산 결과는 8이 나와야한다.

이는 중위표기식으로 표현한 식인데, 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위표기식으로 변환해서 계산해야한다.

3+2*4-9/3 --> 324*+93/-으로 변환되고 이를 계산하면 8이 된다. 

실제로 이 알고리즘은 어느 회사 면접에서 라이브 코딩으로 물어봤던 내용이다.

예전부터 공부했지만, 매번 까먹는 내용이다보니 확실히 기억하기 위해 상세히 적어본다..

 

# 후위 표기식으로 변환

1. 숫자는 바로 변환하는 후위식에 넣어준다.

2. 연산자일 경우 스택에 넣는다. (단, 스택에 현재 연산자보다 우선순위가 낮은게 있을때까지 빼서 후위식에 넣어준다. 그 다음 스택에 넣기) 

(이는 즉, 스택에 현재 연산자보다 우선순위가 높거나 같은건 다 나와야 한다는 것이다.)

3. 위 반복을 완료하고, 스택에 남은 연산자를 모두 식에 넣어준다.

 

- 상세 과정

이를 위에 식인 3+2*4-9/3로 예를 들고, 후위 표기식으로 변환되는 식은 post라고 하겠다.

1. 3은 숫자이므로 그대로 post에 3을 넣어준다. (post : 3   |  stack : empty)

2. +는 연산자이고, 스택은 비어있으므로 그냥 스택에 넣어준다. (post : 3   |   stack : (+))

3. 2는 숫자이므로 그대로 post에 넣어준다. (post : 3 2   |  stack : (+))

4. *은 연산자이므로 스택에 넣는데, 스택에 있는 연산자는 +인 자신보다 우선순위가 낮으므로 그냥 넣어준다. (post : 3 2   |   stack : (+, *))

5. 4는 숫자이므로 (post : 3 2 4   |   stack : (+, *))

6. -는 연산자인데, 스택에 자신보다 우선순위가 높거나 같은 것이 *, + 모두 있으므로 이를 모두 빼서 식에 넣어준다. (post : 3 2 4 * +   |   stack : (-))

7. 9는 숫자이므로 (post : 3 2 4 * + 9   |   stack : (-))

8. /는 연산자이므로 자신보다 우선순위가 낮으므로 그냥 스택에 넣는다.  (post : 3 2 4 * + 9   |   stack : (-, /))

9. 3은 숫자이므로  (post : 3 2 4 * + 9 3   |   stack : (-, /))

10. 스택에 남은 -, /를 빼서 넣어준다. (post : 3 2 4 * + 9 3 / -   |   stack : empty)

 

# 후위 표기식 계산

1. 숫자를 만나면 스택에 넣는다.

2. 연산자가 나오면 스택에 있는 것은 두번 pop해서 나온 순서 반대로 계산한다. (먼저 pop된게 뒤로 가도록 해서 계산)해서 push

 

- 상세과정

위에 과정으로 나온 post식은 3 2 4 * + 9 3 / - 이다. 이를 계산하면

1. 3은 숫자이므로 스택에 넣는다. (stack : 3)

2. 2도 숫자이므로 (stack : 3, 2)

3. 4도 숫자이므로  (stack : 3, 2, 4)

4. *는 연산자이므로 두번 pop하면 4, 2가 있고, 2*4를 계산하면 8을 다시 스택에 넣는다. (stack : 3, 8)

5. +도 연산자이므로, 3+8을 계산하면 11을 스택에 넣는다. (stack : 11)

6. 9는 숫자이므로 스택에 넣는다. (stack : 11, 9)

7. 3도 숫자이므로 스택에 넣는다. (stack : 11, 9, 3)

8. /는 연산자이므로, 두번 pop한 9 / 3을 계산한 3을 스택에 넣는다. (stack : 11, 3)

9. -는 연산자이므로, 두번 pop한 11-3을 계산한 8을 스택에 넣는다. (stack : 8)

10. 이로써 반복문은 끝나고, 스택에 남은 8이 최종 결과가 된다.

 

# 소스코드

시간복잡도 : O(N), 공간복잡도 : O(N)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
 
public class Postfix {
    private static HashMap<Character, Integer> opMap;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        defineOperation();
 
 
        String input = scanner.nextLine();
 
        String result;
        result = input.replace("*", " * ");
        result = result.replace("/", " / ");        
        result = result.replace("-", " - ");
        result = result.replace("+", " + ");
 
        ArrayList<Object> post = infixToPostfix(result);
        System.out.println(calculatePostfix(post));
        System.out.println(post.toString());
    }
 
    private static void defineOperation(){
        opMap = new HashMap<>();
        opMap.put('*', 3);
        opMap.put('/', 3);
        opMap.put('+', 2);
        opMap.put('-', 2);
    }
 
    public static boolean isProceed(char op1, char op2) {
        int op1Prec = opMap.get(op1);
        int op2Prec = opMap.get(op2);
 
        if (op1Prec >= op2Prec)
            return true;
        else
            return false;
 
    }
 
    public static boolean isNumeric(String str) {
        return str.matches("-?\\d+(\\.\\d+)?");  //match a number with optional '-' and decimal.
    }
 
        /*
            1. 숫자는 그냥 후위식에 바로 넣어준다.
            2. 연산자일 경우 스택에 넣는다. 
            (단, 스택에 현재 연산자보다 우선순위가 낮은게 나올때까지 모두 다 빼서 후위식에 넣어줌. 
            즉, 스택에 현재꺼보다 우선순위가 높거나 같은건 다 먼저 나오게)
            
            스택에 있는 연산자는 이전에 있던 연산자인데, 이전에 있는 것이 지금 나온 연산자보다 우선순위가 높거나 같을 경우 다 빼주는 거임
        */
    public static ArrayList infixToPostfix(String s){
        ArrayList<Object> postFix = new ArrayList<>();
        String[] strs = s.split(" ");
        Stack<Character> stack = new Stack<>();
 
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            if (isNumeric(str)) {
                postFix.add(Integer.parseInt(str));
            }
            else {
                                
                char ch = str.charAt(0);
                switch (ch) {
                    case '+':
                    case '-':
                    case '/':
                    case '*':
                                                //현 스택에 ch보다 우선순위가 높거나 같은거는 다 빼서 넣어줌 (낮은것만 안뺌)
                        while (!stack.isEmpty() && isProceed(stack.peek(), ch))
                            postFix.add(stack.pop());
                        stack.push(ch);
                        break;
                }
 
            }
        }
 
        while (!stack.isEmpty())
            postFix.add(stack.pop());
 
        return postFix;
    }
 
 
        /*
            1. 숫자를 만나면 스택에 넣는다.
            2. 연산자가 나오면 스택에 있는 것을 두번 pop해 나온 순서 반대로 계산 (먼저 pop된게 뒤로 가게)해서 push
        */
    public static long calculatePostfix(ArrayList<Object> postfix){
        Stack<Long> stack = new Stack<>();
 
        for (int i = 0; i< postfix.size(); i++) {
            Object obj = postfix.get(i);
            if(obj instanceof Integer) {
                int num = (Integer) obj;
                stack.push((long) num);
 
            }else{ //연산자인 경우
                long b = stack.pop();
                long a = stack.pop();
 
                char op = (char) obj;
                if(op == '+'){
                    stack.push((a+b));
                }else if(op == '-'){
                    stack.push((a-b));
                }else if(op == '*'){
                    stack.push((a*b));
                }else if(op == '/'){
                    stack.push((a/b));
                }
            }
        }
 
        return stack.pop();
    }
}