[2017.09.14] 03. Calculator 프로젝트 [괄호O - Stack 사용O]

중요 로직

 중요 로직은 아래의 그림으로 먼저 확인하자.

중위 순회를 후위 순회로 변경하는 이유는 스택를 사용해 계산 연산을 하기 위함이다.

Step1. 중위 순회 -> 후위 순회

1. 연산자가 입력되었을 때 해당 연산자보다 우선 순위가 높거나 같은 연산자가 있을 경우, 없을 때까지 pop해 출력 후 해당 연산자 push
2. 닫는 괄호를 만나면 여는 괄호 전까지 스택에서 pop 후 출력

Step2. 후위 순회를 연산

1. 숫자를 만나면 스택에 입력하다 연산자를 만나면 2개의 숫자를 pop해 연산 처리 후 다시 스택에 저장
   

   private static double calc(String str) {
       // Step1. 중위 순회를 후위 순회로 변환 
       ArrayList<String> postfix = toPostfix(str);
           
       Stack<String> stack = new Stack<>();
       double front, back;
           
       // Step2. 후위 순회 연산 
       for (int i=0; i<postfix.size(); i=i+1) {
           switch (postfix.get(i)) {
               case "+":
                   back = Double.parseDouble(stack.pop());
                   front = Double.parseDouble(stack.pop());
                   stack.push((front + back)+"");
                   break;
               case "-":
                   back = Double.parseDouble(stack.pop());
                   front = Double.parseDouble(stack.pop());
                   stack.push((front - back)+"");
                   break;
               case "/":
                   back = Double.parseDouble(stack.pop());
                   front = Double.parseDouble(stack.pop());
                   stack.push((front / back)+"");
                   break;
               case "*":
                   back = Double.parseDouble(stack.pop());
                   front = Double.parseDouble(stack.pop());
                   stack.push((front * back)+"");
                   break;
               default:
                   stack.push(postfix.get(i));
    
           }
       }
       return Double.parseDouble(stack.pop());
   }
    

문제점 및 해결

1. 괄호 안 우선 순위 결정
   중위 순회를 후위 순회로 변경하는 과정에서 괄호 문제는 해결하였다. 그러나 괄호 안의 1개 이상의 연산이 들어갈 경우(ex (4 / 2 + 2)) 제대로 된 후위 순위 결과가 나오지 않았다. 이유는 괄호 안을 처리 할 때 우선 순위가 설정되어 있지 않았고 우선 순위 메소드를 설정하므로 문제 해결
   

   /**
    * 사칙연산(*,/,+,-) 사이의 우선순위를 설정하는 메소드
    * @param parm1
    * @return
    */
   private static int getPriority(String parm1) {
       switch(parm1) {
           case "(":    case ")":
               return 0;
           case "+":    case "-":
               return 1;
           case "*":    case "/":
               return 2;
       }
       // -1일 경우, 오류 
       return -1;
   }
    
   /**
    * 중위 순회를 후위 순회로 변경하는 메소드
    * @param str
    * @return
    */
   private static ArrayList<String> toPostfix(String str) {
       ArrayList<String> result = new ArrayList<>();
       String[] calcTarget = str.split(" ");
       Stack<String> stack = new Stack<>();
       String forPrint="";
           
       for (int i=0; i<calcTarget.length; i=i+1) {
           switch (calcTarget[i]) {
               case "(":
                   stack.push(calcTarget[i]);
                   break;
               case ")":
                   forPrint = stack.pop();
                   while(!forPrint.equals("(")) {
                       result.add(forPrint);
                       forPrint = stack.pop();
                   }
                   break;
               case "+":
               case "-":
               case "/":
               case "*":
                   while(!stack.isEmpty() && getPriority(calcTarget[i]) <= getPriority(stack.peek())) {
                       forPrint = stack.pop();
                       result.add(forPrint);
                   }
                   stack.push(calcTarget[i]);
                   break;
               default:
                   result.add(calcTarget[i]);
                   break;
           }
       }
           
       while(!stack.isEmpty()) {
           forPrint = stack.pop();    
           result.add(forPrint);
       }
           
       return result;
   }

스크린 샷

# 중위 순회를 후위 순회로 #중위 순회 #후위 순회 #후위 순회 계산기 #스택 계산기 #순위 순회 후위 순회 변환