[LeetCode] 227. Basic Calculator II - 스택(Stack) + 문자열(String) + 구현(Implementation) JAVA

https://leetcode.com/problems/basic-calculator-ii/description/

코드설명

스택(Stack) + 문자열(String) + 구현(Implementation) 을 활용합니다.

 

문제를 해석해보면, 주어진 문자열 s는 표현식으로써, 해당 표현식을 계산하고 값을 반환하라입니다.

또한, 정수 나눗셈은 0으로 절삭하라. 즉 버림을 하라는 의미입니다. ( 항상 0 으로 가까워지도록 ) 

이는, 음수인경우에도 동일합니다. ( -7/3 ->  -2 )

 

 

먼저, 스택을 활용하는 이유입니다.

스택을 사용하여야만, 연산자의 순서에 맞게 차례대로 연산할 수 있습니다. LIFO이기에 그렇습니다.

큐를 사용한다면 FIFO 이기에 안됩니다.

 

또한, 구현을 하면서 아래의 조건문을 작성하게 되는데,

이떄 왜 else if 문으로 숫자가 아닌경우를 배제하면 되는것 아닐까 라는 생각이 듭니다.

if(c >= '0' && c <='9'){
    num = num * 10 + (c - '0'); 
}
 
if( (  (c < '0' || c > '9') && c != ' ') || i == s.length() - 1){

하지만, 이러한 방법을 사용해야 하는 이유는, i == s.length() - 1 조건 떄문입니다.

마지막 숫자인 경우에는 바로 끝나는게 아닌, operator 연산자를 적용해주어야 하기 때문에 이와 같이 처리합니다.

 

세번쨰, 왜 operand의 초기값이 '+' 일까요?

처음값은 반드시 스택에 넣고서, 그 이후의 값부터 연산에 사용한다는 의미입니다.

코드

정답코드입니다.

class Solution {
    public int calculate(String s) {
        if(s == null || s.length() == 0) return 0;
 
        Stack<Integer> st = new Stack<>();
        int num = 0;
        char operator = '+';
 
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
 
            if(c >= '0' && c <='9'){
                num = num * 10 + (c - '0'); 
            }
            if( (  (c < '0' || c > '9') && c != ' ') || i == s.length() - 1){
            // if( (!(c >= '0' && c <='9') && c != ' ' ) || i == s.length() -1 ) {
                //이전 연산자(operator)를 기준으로 스택 처리
                if(operator == '+'){
                    st.push(num);
                }else if(operator =='-'){
                    st.push(-num);
                }else if(operator == '*'){
                    st.push(st.pop() * num);
                }else if(operator == '/'){
                    st.push(st.pop() / num);
                }
 
                operator = c; //현재 연산자를 저장
                num = 0;
            }
        }
 
        //스택에 남은 숫자들의 합 계싼
        int result = 0;
        while(!st.isEmpty()){
            result += st.pop();
        }
        return result;
    }
}

 

처음에 잘못 접근한 코드입니다.

class Solution {
    public int calculate(String s) {
        int idx = 0;
        int sum = 0;
        Stack<Integer> numSt = new Stack<>();
        Stack<Character> operationSt = new Stack<>();
        boolean isOperationCalled = false;
        while(idx < s.length()){
            char ch = s.charAt(idx++);
            System.out.println("==================="+ch);
            if(ch == ' ') continue;
        
            if(ch >= '0' && ch <= '9'){
                sum = sum * 10 + ch - '0';
                System.out.println("sum: "+sum);
            }  else if(isOperationCalled == true){
                numSt.push(sum);
                sum = 0;
                int secondNum = numSt.pop();
                char operation = operationSt.pop();
                int firstNum = numSt.pop();
                System.out.println("OPERATION CALLED:"+firstNum+" "+operation+" "+firstNum);
                if(operation == '*'){
                    numSt.push(firstNum * secondNum);
                } else if(operation == '/'){
                    numSt.push(firstNum / secondNum);
                }
                isOperationCalled = false;
            }
            
            if(ch == '*'){
                numSt.push(sum);
                operationSt.push(ch);
                System.out.println("hi ***** IS OPERATION CALLED IS BEING TRUE");
                isOperationCalled = true;
                sum = 0;
            } else if(ch == '/'){
                numSt.push(sum);
                operationSt.push(ch);
                sum = 0;
                isOperationCalled = true;
            } else if(ch == '+'){
                numSt.push(sum);
                operationSt.push(ch);
                sum = 0;
            } else if(ch == '-'){
                numSt.push(sum);
                operationSt.push(ch);
                sum = 0;
            }
        }
        numSt.push(sum);
 
        for(int a : numSt){
            System.out.print("SUM:" + a);
        }
 
        while(numSt.size() > 1){            
            int secondNum = numSt.pop();
            char operation = operationSt.pop();
            int firstNum = numSt.pop();
            System.out.println("hi lets go" + "firstNum:"+ firstNum+" "+operation+" "+secondNum);
            if(operation == '*'){
                numSt.push(firstNum * secondNum);
            } else if(operation == '/'){
                numSt.push(firstNum / secondNum);
            } else if(operation == '+'){
                numSt.push(firstNum + secondNum);
            } else if(operation == '-'){
                numSt.push(firstNum - secondNum);
            }
        }
        System.out.println("answer:");
        int answer = -99;
        if(!numSt.isEmpty()){
            answer = numSt.pop();
        }
        return answer;
    }
}