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

후위표기법을 계산하는 방법은 아래 포스팅을 확인하기 바랍니다.

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

[전체 구현 소스 코드 확인하기]

이번 포스팅은 스택 자료구조를 활용해서 중위 표기법을 후위 표기법으로 바꾸는 방법을 알아본다.

중위 표기법을 후위 표기법으로 바꾸는 데에는 아래와 같은 규칙이 있다.

[소괄호가 없는 중위표기법]

1. 중위 표기법을 저장하는 배열 A와 후위 표기법을 저장하는 배열 B가 있다.

2. 아래 규칙에 따라, 피연산자와 연산자를 배열 A에서 배열 B로 이동시킨다.

1) 피연산자는 무조건 B 배열로 이동시킨다.

2) 연산자는 스택에 저장한다.

•  스택이 비어있다면, 연산자를 저장한다.
•  스택이 비어있지 않다면, 이미 저장된 연산자(a)와 저장할 연산자(b)의 우선순위를 비교한다.
•  a 연산자가 우선순위가 더 낮다면, b 연산자를 그냥 저장한다.
•  a 우선순위가 더 높다면, a 연산자를 배열 B로 이동시키고, b연산자를 스택에 넣는다.
•  a와 b의 우선순위가 같다면, a를 배열 B로 이동시키고, b를 스택에 넣는다.

3) 후위 표기법에서는 우선순위가 더 높은 연산자가 우선적으로 나와야한다.

• 스택에 우선순위가 낮은 연산자가 있다면 그 위에 우선순위가 더 높은 연산자를 저장함으로써 우선순위가 낮은 연산자가 먼저 나오는 것을 방지하는 것이다.
• 우선순위가 같을 경우에는 먼저 나온 연산자가 우선순위가 더 높으므로 배열 B로 이동시킨 후, 그 다음 연산자를 스택에 넣는다.

3. 피연산자를 배열 B로 모두 옮겼으면, 스택에 남아있는 연산자를 모두 배열 B로 옮긴다.

[괄호 없는중위표기법을 후위표기법으로 바꾸는 슬라이드 첨부]

012345678

[소괄호가 있는 중위표기법]

후위 표기법의 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야

한다는 사실을 알게 되었다.

(1 + 2 x 3) / 4 의 중위 표기법을 후위 표기법으로 바꿀 때 '/' 연산자보다 '+' 와 'x' 연산자가 먼저 스택에서 빠져 나가야 한다. 즉, '/' 연산자를 스택에 저장할 때, 스택에 '+' 와 'x' 연산자가 있다면 이들을 모두 빼서 B 배열로 이동시킨 후, '/' 연산자를 스택에 저장한다.

1. 중위 표기법을 저장하는 배열 A와 후위 표기법을 저장하는 배열 B가 있다.

2. 아래 규칙에 따라, 피연산자와 연산자를 배열 A에서 배열 B로 이동시킨다.

1) 피연산자는 무조건 B배열로 이동시킨다.

2) 연산자는 스택에 저장한다. (괄호 또한 연산자로 취급한다.)

• 연산자를 스택에 저장하는 방식은 "괄호가 없는 중위 표기법"과 방식이 같다.

• 하지만, 다른 점은 여는 괄호가 어느 연산자보다도 우선순위가 낮다고 가정해야 한다.

• 만약, 닫는 괄호가 나타났다면 여는 괄호 이전까지의 모든 연산자들을 배열 B로 옮겨야 한다.

• 단, 여는 괄호와 닫는 괄호는 B 배열로 옮기지 않는다.

3. 피연산자를 B배열로 모두 옮겼다면, 스택에 저장된 연산자도 모두 B배열로 옮긴다.

[괄호 있는 중위표기법을 후위표기법으로 바꾸는 슬라이드 첨부]

012345678910111213

[연산자의 우선순위를 반환하는 코드]

// 연산자의 우선순위를 반환하는 메소드
    public int getOpPrec(char op) {
 
        switch (op) {
        case '*':
        case '/':
            return 5;
 
        case '+':
        case '-':
            return 3;
 
        case '(':
            return 1;
        }
        return -1;
    }

[두 연산자의 우선순위를 비교하는 코드]

// op1의 우선순위가 높으면 true, 낮으면 false를 반환
    public boolean isProceed(char op1, char op2) {
 
        int op1Prec = getOpPrec(op1);
        int op2Prec = getOpPrec(op2);
 
        if (op1Prec >= op2Prec)
            return true;
        else
            return false;
 
    }
 

[중위표기법을 후위표기법으로 변환하는 코드]

// 중위표기법으로 표기된 exp를 후위표기법으로 변환하는 메소드
    public String convToExpression(String exp) {
 
        Stack<Character> stack = new Stack<>();
        int len = exp.length();
        String postFix = "";
 
        for (int i = 0; i < len; i++) {
 
            char ch = exp.charAt(i);
            if (ch >= '1' && ch <= '9') {
 
                postFix += ch;
 
            } else {
 
                switch (ch) {
 
                case '(':
                    stack.push(ch);
                    break;
 
                case ')':
                    while (true) {
                        char pop = stack.pop();
                        if (pop == '(')
                            break;
                        postFix += pop;
                    }
                    break;
 
                case '+':
                case '-':
                case '*':
                case '/':
                    while (!stack.isEmpty() && isProceed(stack.peek(), ch))
                        postFix += stack.pop();
                    stack.push(ch);
                    break;
                }
 
            }
        }
 
        while (!stack.isEmpty())
            postFix += stack.pop();
 
        return postFix;
 
    }