수학식 후위 표기식으로 변경 (차량기지 알고리즘)

[ 후위 표기식? ]

 

우리가 일반적으로 사용하는 수학식은 '중위 표기식'을 사용합니다.

 

'3 + 5'와 같이 연산자가 (+, -, *, / ) 피연산자(숫자) 중간에 위치하는 방식이 '중위 표기식' 입니다.

 

'후위 표기식'은 '35+'와 같이 연산자가 피연산자 뒤에 있는 방식입니다. 

 

중위 표기식을 후위 표기식으로 바꾸는 일은 스택(Stack)을 활용한 차량기지 알고리즘으로 가능합니다.

 

---

[ 차량기지 알고리즘 ]

 

수학식을 맨 앞부터 참조하며 

 

1. 피연산자(숫자)는 바로 출력

 

2. 연산자의 경우

 

2 - 1. ' ( ' 의 경우 바로 스택에 저장

 

2 - 2. ' ) ' 의 경우, ' ( '을 만날 때까지 스택에서 pop한 값 출력

 

2 - 3. 곱하기와 나누기( * , / )는 스택 맨위의 연산자가 곱하기 또는 나누기일 때, 그 연산을 처리하고 곱하기와 나누기를 스택 맨 위에 추가해준다.

 

2 - 3 더하기와 빼기( + , - )는 ' ( ' 연산자를 만나기 직전까지 스택의 연산자를 pop한 후 스택에 추가

 

3. 수학식을 모두 탐색했다면 스택에 남아있는 것들 출력

 

static int priority(char tmp) {
    if (tmp == '(') return 0;
    else if (tmp == '+' || tmp == '-') return 1;
    else return 2;
}
 
public String getPostfix(String input) {
 
    StringBuilder postfix = new StringBuilder();
    Stack<Character> stack = new Stack<>();
 
    for (int i = 0 ; i < input.length() ; i++) {
 
        char tmp = input.charAt(i);
 
        if (tmp >= '0' && tmp <= '9') {
            postfix.append(tmp);
        } else if (tmp == '(') {
            stack.add(tmp);
        } else if (tmp == ')') {
            while (!stack.isEmpty()) {
                if (stack.peek() == '(') {
                    stack.pop();
                    break;
                }
                postfix.append(stack.pop());
            }
        } else {
            while (!stack.isEmpty() && priority(stack.peek()) >= priority(tmp)) 
                postfix.append(stack.pop());
            
            stack.add(tmp);
        }
    }
 
    while (!stack.isEmpty()) 
        postfix.append(stack.pop());
 
    return postfix.toString();
}  

 

---

[ 후위표기식 계산 ]

 

생성한 후위 표기식 계산 또한 스택으로 구현 가능하다.

 

1. 후위  표기식 처음부터 끝까지 탐색

2. 숫자는 바로 스택에 추가

3. 연산자 참조하면 스택에서 숫자 두 개 꺼내어 연산자로 계산하고 결과값을 다시 스택에 추가. 유의할 점은 먼저 나온 숫자가 뒤에, 나중에 나온 숫자가 앞에 위치해야한다.

 

public int calcPostfix(String input) {
 
    Stack<Integer> stack = new Stack<>();
 
    for (int i = 0 ; i < input.length() ; i++) {
 
        char op = input.charAt(i);
 
        if (op >= '0' && 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();
}

---