문자열 수식 계산하는 메서드 만들기

최근, 한 기업에서 라이브 코테를 보는데 명확하게 풀지 못했던 문제를 다시 풀어보려고 한다.

조건

1. 문자열은 계산할 수 있는 식으로 주어진다.

2. 숫자는 모두 양수로 주어진다.

3. 연산은 +, -, * 만 주어진다.

 

테스트 케이스

1.

입력값 : "20+33-2*5" 

결과 : 43

 

2. 

입력값 : "5-7*2+3"

결과 : -6

 

 

풀이

 

숫자와 연산자를 분리하기

수식을 계산하기 위해서는 숫자와 연산자를 분리하는 것이 필요하다고 생각했다.

 

문자열을 다루는데 유용한 자바 정규식 라이브러리를 사용해서 분리한 뒤, 리스트에 담는다.

 

public int sol(String input) {

        List<String> list = new ArrayList<>();
        Pattern p = Pattern.compile("\\d+|\\D");
        Matcher m = p.matcher(input);

        while (m.find()) {
            String split = m.group();
            list.add(split);
        }

        return result;
    }

 

정규식 부분은, 숫자 혹은 숫자가 아닌 항목을 추출하는 식이다.

 

위 과정을 거치면 "20+33-2*5" 이 입력되었을 때,

 

리스트에 ["20" , "+" , "33" , "-" , "2" , "*" , "5"] 와 같이 채워진다.

 

이제, 연산을 차례대로 하면 될 것 같지만 수식은 곱셈이 우선으로 연산되어야 한다.

 

따라서, 곱셈 연산을 한번 처리해주어야 한다. ( 이 부분을 라이브 코테에서 간과했다가.. 당황했다..)

 

 public int sol(String input) {

        
        List<String> list = new ArrayList<>();
        Pattern p = Pattern.compile("\\d+|\\D");
        Matcher m = p.matcher(input);

        while (m.find()) {
            String split = m.group();
            list.add(split);
        }

        Stack<String> s = new Stack<>();
        
        for (int i = 0; i < list.size(); i++) {
            if (!s.isEmpty() && s.peek().equals("*")) {
                // * 연산자 제거
                s.pop();

                // 계산할 수 가져오기
                String pop = s.pop();

                // 곱셈 계산 후 다시 스택에 입력
                s.push(String.valueOf(Integer.parseInt(pop) * Integer.parseInt(list.get(i))));
            } else {
                s.push(list.get(i));
            }
        }



        return result;
    }

 

곱셈 연산은 스택 자료구조를 활용하면 간단하게 해결할 수 있다.

 

리스트에 저장된 원소를 순회하다가, 스택에 꼭대기에 "*" 가 있는 경우

 

"*" 직전에 스택에 입력되었던 수와 입력할 수를 곱한뒤 입력해주면 된다.

 

그러면, 스택은  ["20" , "+" , "33" , "-" , "10" ] 와 같이 곱셈이 계산되어 곱셈 연산자가 사라진 원소만 남아있게 된다.

 

 

    public int sol(String input) {

        Stack<String> s = new Stack<>();
        List<String> list = new ArrayList<>();
        Pattern p = Pattern.compile("\\d+|\\D");
        Matcher m = p.matcher(input);

        while (m.find()) {
            String split = m.group();
            list.add(split);
        }

        for (int i = 0; i < list.size(); i++) {
            if (!s.isEmpty() && s.peek().equals("*")) {
                // * 연산자 제거
                s.pop();

                // 계산할 수 가져오기
                String pop = s.pop();

                // 곱셈 계산 후 다시 스택에 입력
                s.push(String.valueOf(Integer.parseInt(pop) * Integer.parseInt(list.get(i))));
            } else {
                s.push(list.get(i));
            }
        }

        int result = Integer.parseInt(s.get(0));

        for (int i = 1; i < s.size(); i += 2) {
            String op = s.get(i);
            switch (op) {
                case "+":
                    result += Integer.parseInt(s.get(i + 1));
                    break;
                case "-":
                    result -= Integer.parseInt(s.get(i + 1));
            }
        }

        return result;
    }

 

이제 연산자를 순서대로 계산하면 된다.

 

입력값은 정상적으로 계산되는 수식이 들어옴을 보장하므로

 

연산자는 스택의 홀수번째 인덱스에 존재함도 보장할 수 있다.

 

따라서, 연산자에 따라 switch 문법을 사용하던, if 조건문을 활용하던 해당하는 연산을 해주면 완료된다.