여러상황에서 Stack 학습하기

Practice1 문자열을 역순으로 변환하는 프로그램

import java.util.Stack;

    public class Practice1 {
        public static String reverseString(String str) {
            Stack stack = new Stack();
            String result = "";

            for (String i : str.split("")) {
                stack.push(i);
            }
            while (!stack.isEmpty()) {
                result = result + stack.pop();
            }
            return result;
        }

        public static void main(String[] args) {
            // Test code
            String result = reverseString("Hello");
            System.out.println("result = " + result);

            result = reverseString("1 3 5 7 9");
            System.out.println("result = " + result);
        }
    }

reverseString 메서드

1. Stack과 결과 문자열 초기화

public static String reverseString(String str) {
	Stack stack = new Stack();
    String result = "";

-stack은 문자를 저장할 스택
-result는 역순으로 된 문자열을 저장할 변수

2. 문자열을 Stack에 push

for (String i : str.split("")) {
	stack.push(i);
}

-입력된 문자열 str을 split("") 메서드를 사용하여 개별 문자로 분리
-각 문자를 Stack에 push함 예를들어 "Hello" 는 ["H", "e", "l", "l", "o"]로 분리됨

3. Stack 에서 pop하여 결과 문자열 생성

while (!stack.isEmpty()) {
	result = result + stack.pop();
}

-Stack이 비어있지 않을 때까지 반복
-Stack 에서 pop하여 꺼낸 문자를 result 문자열에 추가. Stack의 맨 위 요소부터 꺼내기 때문에 문자열이 역순으로 변환

4. 결과 문자열 반환

return result;

-최종적으로 역순으로 변환된 문자열을 반환

예시) reverseString("1 3 5 7 9")
1. 초기상태
-stack : []
-result : ""

2. 문자열을 Stack에 push
   -stack : ["1", " ", "3", " ", "5", " ", "7", " ", "9"]

3. Stack에서 pop 하여 결과 문자열 생성
   -result : "9" (pop : "9")
   -result : "9 " (pop : " ")
   -result : "9 7" (pop : "7")
   -result : "9 7 " (pop : " ")
   -result : "9 7 5" (pop : "5")
   -result : "9 7 5 " (pop : " ")
   -result : "9 7 5 3" (pop : "3")
   -result : "9 7 5 3 " (pop : " ")
   -result : "9 7 5 3 1" (pop : "1")

4. 최종 반환값 : "9 7 5 3 1"

Practice2 괄호 짝 검사하는 프로그램

import java.util.Stack;

public class Practice2 {
    public static void checkParenthesis(String str) {
        Stack stack = new Stack();
        boolean checkFlag = true;

        for (String string : str.split("")) {
            if (string.equals("(")) {
                stack.push(string);
            } else {
                if (stack.isEmpty()) {
                    checkFlag = false;
                    break;
                } else {
                    stack.pop();
                }
            }
        }
        if (checkFlag && stack.isEmpty()) {
            System.out.println("Pass");
        } else {
            System.out.println("Fail");
        }
    }

    public static void main(String[] args) {
        // Test code
        checkParenthesis("(");         
        checkParenthesis(")");         
        checkParenthesis("()");        
        checkParenthesis("()()()");    
        checkParenthesis("(())()");    
        checkParenthesis("(((()))");   
    }
}

checkParenthesis 메서드

1. 메서드 시그니처

public static void checkParenthesis (String str)

-checkParenthesis 메서드는 문자열 str을 인자로 받아들여 이 문자열에 포함된 괄호의 유효성을 검사하는 역할

2. Stack 선언

Stack stack = new Stack();

-문자열 괄호를 저장하기 위해 Stack클래스 사용

3. 괄호검사

for (String string : str.split("")) {
	if (string.equals("(")) {
    	stack.push(string);
    } else {
    	if (stack.isEmpty()) {
        	checkFlag = false;
            break;
        } else {
        	stack.pop();
        }
    }
}

-str.split("") 문자열을 통해 문자열 str을 한글자씩 처리
-문자열이 "(" 인경우, Stack에 문자열을 push
-문자열이 ")" 인경우 Stack이 비어있다면,
1. 닫는괄호에 맞는 여는 괄호가 없다는 의미이므로 checkFlag 를 false로 설정하고 검사를 멈춤
2. Stack에서 pop 하여 짝이 맞는 여는 괄호를 제거

4. 결과 출력

if (checkFlag && stack.isEmpty()) {
	System.out.pintln("Pass");
} else {
	System.out.prinln("Fail");
}

-검사를 마친 후 checkFlag 가 true이고 스택이 비어있다면 모든 괄호가 유효하게 맞아 떨어졌기 때문에 Pass 출력
-그렇지 않으면 Fail 출력

Practice3 후위 표기법 연산 프로그램

import java.util.Stack;

public class Practice3 {
    public static double calculate(String string) {
        Stack<Double> stack = new Stack();
        for (String s : string.split(" ")) {
            if (s.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (s.equals("-")) {
                stack.push(-stack.pop() + stack.pop());
            } else if (s.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (s.equals("/")) {
                stack.push(1 / stack.pop() * stack.pop());
            } else {
                stack.push(Double.parseDouble(s));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(calculate("2 2 +"));    
        System.out.println(calculate("2 2 -"));    
        System.out.println(calculate("2 2 *"));    
        System.out.println(calculate("2 2 /"));    

        System.out.println(calculate("1 1 + 2 * 3 * 2 / 5 -"));
        System.out.println(calculate("5 2 * 3 - 8 * 4 /"));

    }
}

** 전위표기법, 중위표기법, 후위표기법 이란?

수학적 식이나 수식을 표현하는 방법론. 각각의 표기법은 연산자와 피연산자의 위치를 다르게 배치하여 수식을 표현

1. 전위표기법(Prefix Notation)
   연산자가 피연산자 앞에 위치하는 방식
   예시)
   수식 : (A + B) X (C - D)
   전위표기법 : X + AB - CD

2. 중위표기법(Infix Notation)
   일반적으로 흔히 사용하는 수식의 표기방식. 연산자가 피연산자들 사이에 위치
   예시)
   수식 : (A + B) X (C - D)
   중위표기법 : (A + B) X (C - D)

3. 후위표기법(Postfix Notation)
   연산자가 피연산자 뒤에 위치하는 방식 Stack을 이용한 계산에 유용하게 사용됨
   예시)
   수식 : (A + B) X (C - D)
   후위표기법 : AB + CD - X

각 표기법의 장단점

1. 전위표기법
   -연산자가 피연산자 앞에 위치하기 때문에 해석이 쉽고, 연산자 우선순위에 따른 괄호 필요성이 줄어듬

2. 중위표기법
   -일반적으로 사용하는 방식이기에 익숙하고 자연스럽게 사용
   -연산자 우선순위에 따라 괄호를 사용해야 할 수 있음

3. 후위표기법
   -Stack을 사용하여 계산하기에 매우 효율적. 연산자와 피연산자의 계산 순서가 명확하게 정의되어 있어 계산기 구현등에 유용함

calculate 메서드

1. 메서드 시그니처

calculate(String string)

-주어진 후위 표기법 수식을 계산하여 결과를 반환

2. Stack 선언

Stack<Double> stack = new Stack();

-Double 형식의 데이터를 저장할 스택 생성

3. 조건생성

for (String s : string.split(" ")) {
	if (s.equals("+")) {
    	stack.push(stack.pop() + stack.pop());
    } else if (s.equals("-")) {
    	stack.push(-stack.pop() + stack.pop());
    } else if (s.equals("*")) {
    	stack.push(stack.pop() * stack.pop());
    } else if (s.equals("/")) {
    	stack.push(1 / stack.pop() * stack.pop());
    } else {
    	stack.push(Double.parseDouble(s));
    }
}

-string.split(" ") : 분리된 요소를 순회함. 문자열 안에 띄어쓰기를 기준으로 각각의 요소를 분리하기 위해 공백으로 표시
-for (String s : string.split(" ")) : 분리된 요소를 순회함
1. 요소가 + 연산자일 경우 Stack에서 두개의 값을 pop하여 더한후 다시 스택에 push
2. 요소가 - 연산자일 경우 Stack에서 두개의 값을 pop하여 더한후 다시 스택에 push
3. 요소가 * 연산자일 경우 Stack에서 두개의 값을 pop하여 곱한후 다시 스택에 push
4. 요소가 / 연산자일 경우 Stack에서 두개의 값을 pop하여 곱한후 다시 스택에 push
5. 위 연산자가 아닐경우, 요소를 Double 형으로 변환하여 스택에 push

4. 결과출력

return stack.pop();

-Stack에 남은 최종 결과 값을 반환

예시)

calculate("2 2 +")
-stack : []
-"2" stack에 push -> [2.0]
-"2" stack에 push -> [2.0, 2.0]
-"+" stack안에 두개의 값을 더하고 결과를 다시 stack에 push -> [4.0]

calculate("2 2 -")
-stack : []
-"2" stack에 push -> [2.0]
-"2" stack에 push -> [2.0, 2.0]
-"-" stack안에 두개의 값중 첫번째 pop값에 -를 붙인 후, 두개의 값을 더하고(-2.0 + 2.0) 결과를 다시 stack에 push -> [0.0]

calculate("2 2 /")
-stack : []
-"2" stack에 push -> [2.0]
-"2" stack에 push -> [2.0, 2.0]
-"/" stack안에 두개의 값중 첫번째 pop값에 1을 나눈 후, 두개의 값을 곱하고(0.5 * 2.0) 결과를 다시 stack에 push -> [1.0]

calculate("5 2 3 - 8 4 /")
-stack : []
-"5" stack에 push -> [5.0]
-"2" stack에 push -> [5.0, 2.0]
-"*" stack안에 두개의 값을 곱하고 결과를 다시 stack에 push -> [10.0]
-"3" stack에 push -> [10.0, 3.0]
-"-" stack안에 두개의 값중 첫번째 pop값에 -를 붙인 후, 두개의 값을 더하고(-3.0 + 10.0) 결과를 다시 stack에 push -> [7.0]
-"8" stack에 push -> [7.0, 8.0]
-"*" stack안에 두개의 값을 곱하고 결과를 다시 stack에 push -> [56.0]
-"4" stack에 push -> [56.0, 4.0]
-"/" stack안에 두개의 값중 첫번째 pop값에 1을 나눈 후, 두개의 값을 곱하고(0.25 * 56.0) 결과를 다시 stack에 push -> [14.0]

Practice4 문자열 비교 후 특정문자 직전의 문자를 지우는 프로그램

import java.util.Stack;

public class Practice4 {

    public static boolean stringCompare(String s1, String s2) {
        String s1After = doBackspace(s1);
        String s2After = doBackspace(s2);
        return s1After.equals(s2After);
    }

    public static String doBackspace(String s) {
        Stack stack = new Stack();
        for (char c : s.toCharArray()) {
            if (c == '#' && !stack.empty()) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return String.valueOf(stack);
    }

    public static void main(String[] args) {
        // Test code
        String s1 = "tree";
        String s2 = "th#ree";
        System.out.println(stringCompare(s1, s2));

        s1 = "ab#a";
        s2 = "aab#";
        System.out.println(stringCompare(s1, s2));

        s1 = "wo#w";
        s2 = "ww#o";
        System.out.println(stringCompare(s1, s2));
    }
}

1. stringCompare 메서드

public static boolean stringCompare(String s1, String s2) {
	String s1After = doBackspace(s1);
    String s2After = doBackspace(s2);
    return s1After.equals(s2After);

-두 문자열 s1과 s2를 받아서 백스페이스 연산을 수행한 후, 결과 문자열을 비교하여 같은지 다른지 판단
-doBackspace(s1) 을 호출하여 s1에서 백스페이스 연산을 수행한 결과를 s1After에 저장
-doBackspace(s2) 를 호출하여 s2에서 백스페이스 연산을 수행한 결과를 s2After에 저장
-s1After 와 s2After 를 equals 메서드를 사용해 비교하고 결과 반환

2. doBackspace 메서드

public static String doBackspace(String s) {
	Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
    	if (c == '#' && !stack.empty()) {
        	stack.pop();
        } else {
        	stack.push(c);
        }
    }
    return String.valueOf(stack);
}

-주어진 문자열 s 에서 백스페이스 연산을 수행한 결과를 반환
-문자열 s를 문자 단위로 순회(toCharArray() 메서드 사용)
-c가 # 이고 stack이 비어있지 않으면(이전에 문자가 stack에 쌓여있을 때), 스택에서 pop연산을 수행하여 이전 문자를 식제
-그렇지 않으면 stack에 문자 c를 push
-반복이 끝나면 stack에 남아있는 문자들을 문자열로 변환하여 반환 (String.valueOf(stack))