[Java 실습] 스택 후위 표기 계산기

중위 표기 계산기를 후위 표기 계산기로 바꾸기

1. Stack 직접 구현

2. Collection Stack 사용

---

1. 스택 직접 구현

 

input => 113 + 11 - (32 - (9 - 2 + 6))

output  => 113 + 11 - (32 - (9 - 2 + 6)) = 105

 

StringUtils.inNumeric( )은 매개변수가 숫자인지 아닌지 boolean값으로 리턴해줍니다.

 

StringUtils는 https://commons.apache.org/proper/commons-lang/download_lang.cgi 에서 다운 받아 

사용 가능합니다.

 

package Stack1;

// 거의 대부분의 문자열 처리를 수행
// 파라미터 값으로 null을 주더라도 절대 NullPointException을 발생시키지 않음.
import org.apache.commons.lang3.StringUtils;

public class IntStack {
	 static String str = "113 + 11 - (32 - (9 - 2 + 6))";
	 static String[] arr = str.split("");	// str split
	 static int count;
	 static String[] stack = new String[str.length()];
	 static String postfix = "";
	 
	 // 맨 위를 지우는 메서드
	 public static String pop() {
		 // 지울게 없으면
        if(count == 0){
            return null;
        }
        // 지울거 있으면
        else {
            int tmp = count-1;
            System.out.println("pop : " + stack[tmp]);
            count--;
            return stack[tmp];
        }
	 }
	 public static void push(String num){
        System.out.println("push : " + num);
        // 인덱스가 0이면?
        if (count == 0){
            stack[0] = num;
        }
        // 인덱스가 0 이상이면?
        else {
            stack[count] = num;
        }
        count++;
	 }
	
	  public static void main(String[] args) {
	    // 후위표기법으로 저장
	    count = 0;
	    for (int i = 0; i < arr.length; i++) {
	        System.out.println(arr[i]);
	        // 문자열이 모두 숫자이면 true를 반환
	        if (StringUtils.isNumeric(arr[i])) {
	            postfix += arr[i];
	        // 빈칸이면 그대로
	        } else if (arr[i].equals(" "))
	            postfix += arr[i];
	        // 열린 괄호이면 push
	        else if (arr[i].equals("(")) {
	            push(arr[i]);
	        // 닫힌 괄호이면?
	        } else if (arr[i].equals(")")) {
	            for (int k = 0; k < stack.length; k++) {
	                System.out.print(stack[k]);
	            } do {
	                postfix += " ";
	                postfix += pop();
	            // 열린 괄호가 나올때까지 pop
	            } while (!stack[count].equals("("));
	                postfix += pop();
	            } else {
	                if (count == 0)
	                    push(arr[i]);
	                else if (stack[count - 1].equals("+") || stack[count - 1].equals("-")) {
	                    postfix += pop();
	                    push(arr[i]);
	                } else {
	                    push(arr[i]);
	                }
	            }
	        }
	    	// 2칸 빈칸을 1칸 빈칸으로
	        postfix = postfix.replace("  ", " ");
	        // ( 를 ""로
	        postfix = postfix.replace("(", "");
	        System.out.println(postfix);
	
	        // calc
	        stack = new String[str.length()];
	        count = 0;
	        // postfix를 스플릿한걸 담을 sStack
	        String[] sStack = postfix.split(" ");
	        for (int i = 0; i < sStack.length; i++) {
	        	// sStack[i]가 문자열이 숫자인지 확인하기
	            if (StringUtils.isNumeric(sStack[i]))
	                push(sStack[i]);
	
	            else if (sStack[i].equals("+"))
	                push(Integer.toString(Integer.parseInt(pop()) + Integer.parseInt(pop())));
	
	            else if (sStack[i].equals("-"))
	                push(Integer.toString(-Integer.parseInt(pop()) + Integer.parseInt(pop())));
	        }
	        System.out.println(str + " = " + stack[0]);
	    }
}

---

2. Collection Stack 사용

 

package Stack1;

import org.apache.commons.lang3.StringUtils;
import java.util.*;

public class GenericStack {
    static String str = "113 + 11 - (32 - (9 - 2 + 6))";
    static String[] items = str.split("");
    static ArrayList<String> postFixes = new ArrayList<String>(Arrays.asList(items));	// 후위 표기
    static Stack<String> stack = new Stack<String>();
    static Stack<Integer> calcul = new Stack<Integer>();
    
    public static void main(String[] args) {
        System.out.println("중위 표기법 : 113 + 11 - (32 - (9 - 2 + 6))");
        String postfix = "";
        // 후위 표기 싹 다 돌려보기
        for (String element: postFixes) {
        	// 문자열이 숫자인지 확인
            if (StringUtils.isNumeric(element)) {
                postfix += element;
            }
            // ( 라면?
            else if (element.equals("("))
                stack.push(element);
            // ) 라면?
            else if (element.equals(")")) {
            	// 맨 위의 값이 ( 가 아니라면
                while (!stack.peek().equals("("))
                    postfix += " " +stack.pop();
                stack.pop();
            }
            // 빈칸이라면?
            else if(element.equals(" "))
                postfix += " ";
            else{
            	// 스택이 비어있지 않으면
                if(!stack.empty()) {
                	// ( 포함한다면
                    if(stack.contains("(")) {
                    	// 맨 위의 값이 (이 아니라면
                        while (!stack.peek().equals("(")) {
                            postfix += stack.pop();
                        }
                    }
                    else
                        postfix += stack.pop();
                }
                    stack.push(element);
            }
        }
        // stack에 한개가 남아서 뽑아준다.
        if (stack.size() == 1)
            postfix += " " + stack.pop();
        // 두 칸 띄워쓰기를 한 칸으로 줄인다.
        postfix = postfix.replace("  ", " ");

        System.out.println("후위표기법\n"+postfix);
        String[] calc = postfix.split(" ");
        for(int i = 0; i < calc.length; i++) {
            if(StringUtils.isNumeric(calc[i]))
                calcul.push(Integer.parseInt(calc[i]));
            else if(calc[i].equals("+"))
                calcul.push(calcul.pop() + calcul.pop());
            else
                calcul.push(-calcul.pop() + calcul.pop());
        }
        System.out.println("답 = " + calcul);
    }
}

---

느낀점

 

스택을 구현하면서 크게 어려움을 많이 느꼈다.

내가 짜는데에 어려움을 많이 느꼈고, 주변 친구들의 많은 코드들을 보며 코드 리뷰를 하였다.

확실히 컬렉션은 편리하다는 것을 느꼈고, 다음에는 진짜로 나만의 코드를 짜볼 수 있게 노력해야겠다.

---

배운 코드 출처 : https://jwaiting.tistory.com/14?category=1109715