Stack(3) - 계산기(문자열 수식), 백트래킹 기법

계산기(문자열 수식 계산하기)

계산기의 문자열 계산식을 스택을 사용하여 해결할 수 있다.

1. Stack을 이용하여 중위표기법^[각주:1]의 수식을 후위표기법^[각주:2]으로 변경
2. 후위표기법의 수식을 Stack을 이용하여 계산

1. 중위표기식을 후위표기식으로 변환하기

1. 입력받은 중위표기식에서 토큰을 읽음
2. 토큰이 피연산자이면 토큰을 출력
3. 토큰이 연산자(괄호포함)일 경우
1. 토큰이 스택의 top에 저장된 연산자보다 우선순위가 높으면 push
2. 그렇지 않다면 토큰의 우선순위가 더 높을때까지 pop한 후 토큰의 연산자를 push
3. top에 연산자가 없으면 push
4. 토큰이 오른쪽 괄호 ')' 일 경우
1. Stack top에 왼쪽 괄호 '(' 가 올 때까지 pop
2. pop한 연산자를 출력
5. 중위표기식에 더 읽을 것이 없다면 중지, 더 읽을 것이 있다면 1부터 반복
6. Stack 남아있는 연산자를 모두 pop하여 출력

1-1. 중위표기식을 후위표기식으로 변환하는 알고리즘 구현하기

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
 
public class Stack_중위표기법변환 {
    // 스택 내에서 연산자 우선순위 맵
    private static Map<Character, Integer> operPriorityMap;
    private static Stack<Character> operStack ;
    static {
        operPriorityMap = new HashMap<>();
        operPriorityMap.put('(', 0);
        operPriorityMap.put('+', 1);
        operPriorityMap.put('-', 1);
        operPriorityMap.put('*', 2);
        operPriorityMap.put('/', 2);
        
        operStack = new Stack<>();
    }
 
    public static void main(String[] args) {
        String input = "(6+5*(2-8)/2)";
        List<Character> output = new ArrayList<>();
        
        char[] inputChars = input.toCharArray();
        
        for(int i=0; i<inputChars.length; i++) {
            char c = inputChars[i];
            
            // 연산자
            if(isOperation(c)) {
                // 연산자 스택이 비었다면 push 
                if(operStack.isEmpty()) {
                    operStack.push(c);
                } // 연산자 우선순위 비교 
                else {
                    // 닫는 괄호일경우 여는 괄호 '(' 가 나올떄까지 pop
                    if(c == ')') {
                        char top = ' ';
                        do {
                            top = operStack.pop();
                            if(top != '(') {
                                output.add(top);
                            }
                        } while(top != '(');
                    } // 여는 괄호는 무조건 push 
                    else if(c == '(') {
                        operStack.push(c);
                    } // 그외 연산자인 경우 
                    else {
                        int tokenPriority = operPriorityMap.get(c);
                        
                        char top = operStack.peek();
                        int topPriority = operPriorityMap.get(top);
                        // 토큰의 우선순위가 더 높다면 스택에 추가
                        if(tokenPriority > topPriority) {
                            operStack.push(c);
                        } // 토큰의 우선순위가 더 높을때까지 pop 한 후 push 
                        else {
                            top = operStack.pop();
                            output.add(top);
                            
                            do {
                                if(operStack.isEmpty()) {
                                    operStack.push(c);
                                } else {
                                    top = operStack.peek();
                                    topPriority = operPriorityMap.get(top);
                                    if(tokenPriority > topPriority) {
                                        operStack.push(c);
                                    } else {
                                        top = operStack.pop();
                                        output.add(top);    
                                    }
                                }
                            } while(tokenPriority <= topPriority);
                        }
                    }
                }
            } // 피연산자
            else {
                output.add(c);
            }
        }
        
        // 6528-*2/+
        for(int i=0; i<output.size(); i++) {
            System.out.printf("%c", output.get(i));
        }
    }
    
    /**
     * 연산자 여부 확인
     * @param c
     * @return
     */
    public static boolean isOperation(char c) {
        if(')' == c) {
            return true;
        }
        
        return operPriorityMap.containsKey(c);
    }
}
 

2. 후위표기법의 수식을 Stack을 이용하여 계산하기

위에서 구한 후의표기법을 이용하여 계산을 수행해보자. 알고리즘은 아래와 같다.

1. 피연산자를 만나면 Stack에 push
2. 연산자를 만나면 필요한 만큼의 피연자를 Stack에서 pop하여 계산하고 연산 결과를 다시 Stack에 push함
   피연산자의 숫자는 pop한 순서와 반대임
3. 수식이 끝나면 마지막으로 Stack을 pop하여 출력

2-1. 후위표기법으로 계산 구현하기

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
 
public class Stack_후위표기법계산 {
    private static Stack<Integer> numberStack = new Stack<>();
 
    public static void main(String[] args) {
        String input = "6528-*2/+";
        char[] inputChars = input.toCharArray();
        
        for(int i=0; i<inputChars.length; i++) {
            char c = inputChars[i];
            
            // 피연산자이면 스택에 추가
            if(!isOperation(c)) {
                int num = Integer.parseInt(new Character(c).toString());
                numberStack.push(num);
            } 
            else {
                int num1 = numberStack.pop();
                int num2 = numberStack.pop();
                
                int result = 0 ;
                switch(c) {
                case '+' :
                    result = num2 + num1;
                    break;
                case '-' :
                    result = num2 - num1;
                    break;
                case '*' :
                    result = num2 * num1;
                    break;
                case '/' :
                    result = num2 / num1;
                    break;
                }
                numberStack.push(result);
            }
            
        }
 
        int result = numberStack.pop();
        System.out.println(result); // -9
    }
    
    /**
     * 연산자 여부 확인
     * @param c
     * @return
     */
    public static boolean isOperation(char c) {
        char[] operations = {'(', ')', '*', '+', '-', '/'};
        for(int i=0; i<operations.length; i++) {
            if(c == operations[i]) {
                return true;
            }
        }
        return false;
    }
}
 

백트래킹(Backtracking)

해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법이다. 이를 이용하여 최적화(Optimization) 문제와 결정(Desision)문제^[각주:3]를 해결할 수 있다.

미로찾기 구현

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;
 
public class Stack백트래킹_미로찾기 {
    private static Stack<Pos> posStack = new Stack<>();
    private static Map<Pos, Boolean> visitHistory = new HashMap<>();
    
    // 0은 벽, 1은 통로, 2는 출구
    private static int[][] mazeArr = {
            {1, 0, 0, 0},
            {1, 1, 1, 0},
            {0, 1, 0, 0},
            {0, 1, 1, 1},
            {0, 2, 0, 0}
    };
    
    
    // 시계방향으로 이동가능한지 확인을 위함
    private static int[][] directionArr = {
            {1, 0}, // 우 
            {0, 1}, // 하
            {-1, 0}, // 좌
            {0, -1} // 상
    };
    
    public static void main(String[] args) {
        Pos now = new Pos(0, 0);
        posStack.push(now);
        
        do {
            System.out.println(now);
            visitHistory.put(now, true);
            
             Pos movablePos = move(now);
             if(movablePos != null) {
                  posStack.push(movablePos);    
             } else {
                movablePos = posStack.pop();
             }
            now = movablePos;
        } while(mazeArr[now.getY()][now.getX()] != 2);
    }
    
    /**
     * 이동할 수 있는 위치 반환. 이동할 수 없다면 null 반환
     * @param pos
     * @return
     */
    private static Pos move(Pos pos) {
        int x = pos.getX();
        int y = pos.getY();
        
        // 현재위치에서 시계방향으로 이동할 수 있는 곳을 체크함
        for(int i=0; i<4; i++) {
            int[] direction = directionArr[i];
            int moveX = direction[0];
            int moveY = direction[1];
            
            // 미로 범위안에서 이동가능 체크
            if((x + moveX) >= 0 && (x + moveX) <= 3
                    && (y + moveY) >= 0 && (y + moveY) <= 4) {
                if(mazeArr[y+moveY][x+moveX] == 0) {
                    continue;
                } 
                // 1(통로) 아니면 2(도착지)
                Pos movePos = new Pos(x+moveX, y+moveY);
                
                boolean isVisit = posStack.contains(movePos);
                if(!isVisit) {
                    Boolean hasVisitHisotry = visitHistory.get(movePos);
                    if(hasVisitHisotry == null) {
                        return movePos;
                    }
                }
            }
        }
        return null;
    }
}
 
 
class Pos {
    private int x;
    private int y;
    
    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
    
    @Override
    public boolean equals(Object obj) {
        if(obj == null || !(obj instanceof Pos)) {
            return false;
        }
        Pos pos = (Pos)obj;
        if(pos.getX() == x && pos.getY() == y) {
            return true;
        }
        return false;
    }
    
    public int hashCode() {
        return Objects.hash(x,y);
    }
    
    public String toString() {
        StringBuffer bf = new StringBuffer();
        bf.append("x: "+x+",");
        bf.append("y: "+y);
        return bf.toString();
    }
}
 

1. 연사자를 피연산자의 가운데 표기하는 방법 ex) A+B [본문으로]
2. 연산자를 피연산자 뒤에 표기하는 방법. 컴퓨터로 연산할 때 자주쓰임 ex) AB+ [본문으로]
3. 문제의 조건을 만족하는 해가 존재하는지의 여부를 'YES' OR 'NO'가 답하는 문제 ex) 미로 찾기, n-Queen, Map Coloring, 부분 집합의 해 [본문으로]