다항식 계산기 프로젝트
다항식 문자열을 입력 받아 계산 결과를 정수로 반환하는 Calc클래스의 메서드를 구현했다.
TDD개발론을 적용했기 때문에 중복 코드는 제거하고 쉽게 기능 추가를 할 수 있었다.
실제 코드를 구현하기까지 총 20개의 테스트 케이스를 통과하며 테스트 코드를 작성했다.
package org.example;
public class Calc {
public static int run(String exp) {
// 공백이 없는 문자열(단일항)이라면 정수로 변환해서 바로 반환
if (!exp.contains(" ")) {
return Integer.parseInt(exp);
}
int sum = 0;
// 어떤 연산을 할 지 미리 확인
boolean needToMulti = exp.contains("*");
boolean needToPlus = exp.contains("+") || exp.contains(" - ");
boolean needToCompound = needToPlus && needToMulti;
boolean needToFirst = exp.contains("(");
// 괄호를 포함한다면 괄호 제거함수 delpar 호출해서 괄호 제거
if (needToFirst) {
exp = delpar(exp);
}
// 괄호가 없는 연산
if (needToCompound) {
exp = exp.replace("- ", "+ -");
String[] bits = exp.split(" \\+ ");
for (int i = 0; i < bits.length; i++) {
if (bits[i].contains("*")) {
bits[i] = String.valueOf(run(bits[i]));
}
sum += Integer.parseInt(bits[i]);
}
return sum;
} else if (needToPlus) {
exp = exp.replace("- ", "+ -");
String[] bits = exp.split(" \\+ ");
for (int i = 0; i < bits.length; i++) {
sum += Integer.parseInt(bits[i]);
}
return sum;
} else if (needToMulti) {
String[] bits = exp.split(" \\* ");
sum = 1;
for (int i = 0; i < bits.length; i++) {
sum *= Integer.parseInt(bits[i]);
}
return sum;
}
// 예외처리
throw new RuntimeException("해석 불가");
}
// 괄호 제거 함수 구현
public static String delpar(String exp) {
// 첫번째 "(" 인덱스 저장
int open = exp.indexOf("(");
// 마지막 ")" 인덱스 저장
int close = exp.lastIndexOf(")");
// 첫번째 "("가 0번 인덱스를 가진다면
// first 변수에 괄호 내부 저장하고 run호출
// run 실행 결과로 치환
// 두번째 변수에 나머지 문장 저장 후 두 문장 합체
if (open == 0) {
String first = String.valueOf(run(exp.substring(open + 1, close)));
String after = exp.substring(close + 1);
exp = first + after;
// 첫번째 "("가 0번 인덱스가 아니라면
// first 변수에 괄호 외부 저장
// 두번째 변수에 괄호 내부 저장하고 run호출
// run 실행 결과로 치환
// 두 문장 합체
} else {
String first = exp.substring(0, open);
String after = String.valueOf(run(exp.substring(open + 1, close)));
exp = first + after;
}
return exp;
}
}3개의 테스트 케이스 통과시키기를 과제로 받았다. 학원에서 1개만 하고 집에서 나머지 테스트 케이스를 검사해보니, 다 통과가 됐다. 코드를 수정할 필요가 없었다. 그래서 그냥 최종 목표 테스트 케이스까지 통과하도록 구현했다.
구현한 코드는 다항식을 문자열로 입력받아 우선순위를 따진 후에 순서대로 연산을 하고 그 결과를 정수로 반환해준다.
연산 우선순위는 괄호 -> 곱하기 -> 더하기(빼기) 순서로 연산된다.
만약 입력받은 문자열에 괄호가 포함되어 있다면 delpar 함수를 호출한다. 괄호 외부와 괄호 내부로 문자열을 잘라 분리하고, 괄호 내부는 run함수를 호출하여 연산을 먼저하게 된다.
run함수의 반환 타입은 정수형이기 때문에 다시 문자열로 형변환하여 괄호 외부 문장과 결합하고, 그 결과를 반환한다.
괄호가 중첩되어 있다면 delpar함수 실행 중에도 run함수와 delpar 자기자신을 계속 호출하기도 한다. 계속 반복하며 괄호 내부 계산하고 괄호를 지우는 동작을 한다.
📌 업데이트 : 수정
위에서 구현한 코드는 중첩 괄호를 포함하는 다항식 중 (((1 + 1)))형식의 중첩 괄호만 계산이 가능하다. ((1 + 1) + (1 + 1)) 같은 다항식은 연산을 하지 못하는 문제점을 발견했다.
이 코드에서 나누기를 계산하지 못하는 것처럼(부동소수점 방식) ((1 + 1) + (1 + 1)) 형태의 계산식도 그냥 못할 줄 알았다. 근데 가능한 거였고, 가능하게 했다...
package org.example;
public class Calc {
public static boolean debug = true; // true로 고쳐 실행 중간의 exp 변화 확인
public static int runCount = 0;
public static int run(String exp) {
// 디버깅 모드
if(debug) {
System.out.printf("exp(%d) : %s\n", runCount, exp);
}
runCount++;
// 단일항일 경우 바로 0 반환
if (!exp.contains(" ")) {
return Integer.parseInt(exp);
}
int sum = 0;
// 어떤 연산을 할 지 미리 확인
boolean needToMulti = exp.contains("*");
boolean needToPlus = exp.contains("+") || exp.contains(" - ");
boolean needToCompound = needToPlus && needToMulti;
// 괄호를 없앨 때까지 괄호 없애는 함수 실행
while (exp.contains("(")) {
exp = delpar(exp);
}
// 괄호가 없는 문장 연산
if (needToCompound) {
exp = exp.replace("- ", "+ -");
String[] bits = exp.split(" \\+ ");
for (int i = 0; i < bits.length; i++) {
if (bits[i].contains("*")) {
bits[i] = String.valueOf(run(bits[i]));
}
sum += Integer.parseInt(bits[i]);
}
return sum;
} else if (needToPlus) {
exp = exp.replace("- ", "+ -");
String[] bits = exp.split(" \\+ ");
for (int i = 0; i < bits.length; i++) {
sum += Integer.parseInt(bits[i]);
}
return sum;
} else if (needToMulti) {
String[] bits = exp.split(" \\* ");
sum = 1;
for (int i = 0; i < bits.length; i++) {
sum *= Integer.parseInt(bits[i]);
}
return sum;
}
throw new RuntimeException("해석 불가");
}
// 괄호 없애기 함수
// 괄호 내부를 먼저 연산하고, 그 결과를 기존 위치에 치환한다.
public static String delpar(String exp) {
int open = -1; // '(' 위치 저장
int close = -1; // ')' 위치 저장
int i; // 괄호의 인덱스 저장
// 마지막 '('를 찾는다.
for (i = 0; i < exp.length(); i++) {
if (exp.charAt(i) == '(') {
open = i;
}
}
// 마지막 '('의 짝꿍을 찾는다.
for(i = open; i < exp.length(); i++) {
if (exp.charAt(i) == ')') {
close = i;
break;
}
}
// 가장 먼저 연산해야할 괄호를 기준으로 문자열은 3조각으로 나눠서 배열에 저장
String[] expparts = new String[3];
expparts[0] = exp.substring(0, open);
expparts[1] = exp.substring(open + 1, close);
expparts[2] = exp.substring(close + 1);
// 괄호 내부 run
String parRun = String.valueOf(run(expparts[1]));
// 괄호 내부를 연산한 결과를 기존 문장과 합체
String newexp = expparts[0] + parRun + expparts[2];
return newexp;
}
}전 코드와 가장 큰 차이점은 delpar 함수 내부다. delpar 함수의 기능은 가장 바깥의 괄호를 쌍으로 없애는 기능을 했었기 때문에 괄호 안에 두 쌍의 괄호가 연속으로 있을 때, 자신의 쌍을 찾지 못하는 문제가 있었다.
이 문제를 해결하기 위해 가장 마지막 여는 괄호를 찾아 인덱스를 저장하고, 마지막 열기괄호 뒤쪽에서 가장 먼저 위치하는 닫기 괄호를 찾아 인덱스를 저장한다.
(3 + (1 - 8) * 3 + ((1 - 3) * (5 + 2)) 계산식의 경우 33 + (1 - 8) * 3 + ((1 - 3) * |5 + 2|) |의 위치)
괄호가 연속으로 나열된 경우 앞에서부터 계산하는 것이 맞지만 같은 우선순위에 위치한다면 뒤부터 계산해도 문제 없기 때문이다. (앞에 위치한 괄호(1 - 3)의 인덱스를 저장할 방법을 찾지 못한 이유도 있다...)
저장된 여는 괄호 인덱스와 닫는 괄호 인덱스와 split 함수를 활용해서 문자열을 3개로 나눠 배열에 저장한다.
3 + (1 - 8) * 3 + ((1 - 3) * , 5 + 2, ) 이렇게 3개가 저장이 될 것이다.
여는 괄호와 닫는 괄호를 기준으로 나눴기 때문에 배열은 크기가 3으로 고정되고 1번 인덱스에 괄호 내부가 저장된다. 1번 인덱스에 저장된 문자열을 run함수를 호출해 연산 결과를 반환받는다.
연산 결과는 원래 위치해 있던 1번 인덱스에 초기화하고 3개의 문자열(요소)을 합체한다.
이것은 괄호 내부를 먼저 계산하고 결과를 기존 위치에 치환하는 것과 같다.
(((1 + 1) * (3 + 7)) - 8) -> (((1 + 1) * 10) - 8)
또 delpar 함수는 exp(계산할 문자열)가 (를 포함하지 않을 때까지 반복되기 때문에 위 과정을 남은 계산식에 계속 반복한다. 과정을 나열해보자면 아래와 같다.
3 + (1 - 8) * 3 + ((1 - 3) * (5 + 2))
3 + (1 - 8) * 3 + ((1 - 3) * |5 + 2|)
3 + (1 - 8) * 3 + ((1 - 3) * |7|)
3 + (1 - 8) * 3 + ((1 - 3) * 7)
3 + (1 - 8) * 3 + (|1 - 3| * 7)
3 + (1 - 8) * 3 + (|-2| * 7)
3 + (1 - 8) * 3 + (-2 * 7)
3 + (1 - 8) * 3 + |-2 * 7|
3 + (1 - 8) * 3 + |-14|
3 + (1 - 8) * 3 + -14
3 + |1 - 8| * 3 + -14
3 + |-7| * 3 + -14
3 + -7 * 3 + -14
3|-7 * 3|-14
3|-21|-14
-32어제 코드를 구현할 때는 내 메서드에 대한 확신이 없었다. 그냥 테스트는 통과한 코드 정도였는데 오늘 수정한 코드는 조금 확신이 들었다. 아무리 복잡한 다항식이 입력돼도 계산 할 수 있을 것만 같다.
