스택 (2) - 후위 표기법 계산기

스택을 활용하면 String으로 입력된 중위표기법 수식을 후위표기법으로 바꿔서 계산할 수 있다.

 

1. 수식 표기법

수식은 세가지 방법으로 표시할 수 있다.

• 전위 표기 : + A B
• 중위 표기 : A + B
• 후위 표기 : A B +

 

인간은 중위표기법을 널리 사용하여 이해하기 편하고 좋지만, 연산의 우선순위를 알기위해 반드시 괄호가 필요하다는 단점이 있다. 때문에 여기에서는 중위표기법으로 수식을 입력받아서 괄호 없이 우선순위를 알 수 있는 후위표기법으로 변환하고, 계산한다.

 

2. 후위표기 알고리즘 (완전 괄호)

완전괄호 후위표기 알고리즘은 연산자 우선순위를 고려하지 않기 때문에 변환하려는 중위표기 수식에 반드시 괄호가 완벽하게 쳐져있어야 한다.

 

• 숫자를 만나면 string에 더하기
• 연산자를 만나면 스택에 push
• ')'를 만나면 연산자를 pop해서 더하기
• '('를 만나면 무시하기

    public String transform(String inFix) {
        char[] f = inFix.toCharArray();
        ListStack stack = new ListStack();
        String postFix = "";

        for (char c : f) {
            if (c >= '0' && c <= '9') postFix += c;
            else if (c == '+' || c == '-' || c == '*' || c == '/') stack.push(c);
            else if (c == ')') postFix += (char) stack.pop();
        }

        return postFix;
    }

 

3, 후위표기 알고리즘 (불완전 괄호)

불완전괄호 후위표기 알고리즘은 괄호가 완벽하지 않아도 사용 가능하며, 연산자 우선순위를 고려하는데, 괄호는 우선순위가 제일 낮고, +,-는 중간, *,/는 우선순위가 가장 높다.

 

• '('를 만나면 스택에 push
• ')'를 만나면 '(' 나올때까지 연산자를 pop해서 string에 더하고 '('는 버리기
• 연산자를 만나면 하위연산자가 나올때까지 상위연산자를 모두 pop해서 string에 더하고 자기자신 push
• 숫자를 만나면 string에 더함 
• 만약 모든 문자를 처리했는데 스택에 아직 연산자가 남았다면 순서대로 string에 더함

    private int precedence(char c) {
        if (c == '*' || c == '/') return 2;
        else if (c == '+' || c == '-') return 1;
        else return 0;
    }
    
    public String transform(String inFix) {
        char[] f = inFix.toCharArray();
        ListStack stack = new ListStack();
        String postFix = "";

        for (char c : f) {
            if (c == '(')
                stack.push(c);

            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(')
                    postFix += (char) stack.pop();

                stack.pop();
                
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!stack.isEmpty() &&
                        precedence((char) stack.peek()) >= precedence(c))
                    postFix += (char) stack.pop();

                stack.push(c);
                
            } else if (c >= '0' && c <= '9')
                postFix += c;
        }

        while (!stack.isEmpty())
            postFix += (char) stack.pop();

        return postFix;
    }

 

4. 계산 알고리즘

• 숫자를 만나면 stack에 push
• 두개 pop해서 연산 (먼저 뺀게 뒤로가야함)
• pop a, b => b - a나 b / a 처럼

    public int calculate(String inFix) {
        ListStack stack = new ListStack();
        String formula = postFix.transform(inFix);
        System.out.println(formula);
        char[] f = formula.toCharArray();

        for (char c : f) {
            if (c >= '0' && c <= '9')
                stack.push(Integer.parseInt(String.valueOf(c)));

            else if (c == '+' || c == '-' || c == '*' || c == '/') {
                int a = stack.pop();
                int b = stack.pop();

                if (c == '+') stack.push(b + a);
                if (c == '-') stack.push(b - a);
                if (c == '*') stack.push(b * a);
                if (c == '/') stack.push(b / a);
            }
        }

        return stack.pop();
    }

 

5. Reference