[TIL] #1 - 스택으로 Infix to Postfix 계산기 만들기(Java)

학교 자료구조 수업 과제로 스택 자료구조를 이용하여 Infix to Prefix 계산기를 만들어 보았다.

오늘 새벽부터 시작해서 먹고 쉬고 자고 하면서 집중한 시간만 치면 한 10시간? 정도 소요된 것 같다.

구현 과정

Infix에서 Postfix로 식을 만들어야 하는 이유는, 컴퓨터가 Operator의 우선순위를 구분하지 못하기 때문에 한 줄로 주어지는 식의 값을 내기 위해서는 Postfix 형태로 전환한 후 계산시켜야 하기 때문이다.

 

처음에는 왜 스택으로 이러한 기능을 구현하려고 할까 하는 의문이 들었는데, 스택의 peek(), push(), pop()은 순서대로 주어지는 연산자를 비교하여 우선순위를 정해주고, 우선순위에 따라 언제 스택에 쌓아둔 다음 순서대로 꺼내서 postfix에 위치시킬 수 있다는 점에서 안성맞춤이라는 생각이 들었다. 또한 postfix 형태로 변환시킨 식을 다시 계산할 때, opernands들을 원하는 순서대로 꺼내서 사용한 다음 다시 넣어두는 방식으로 순차적으로 계산하는 데에도 스택의 특성이 활용되었다.

 

구현에 앞서 신경써야할 포인트는 다음과 같았다.

1. 연산자들 간의 우선순위 : ( )     ->      ^     ->     (unary) -      ->      / %      ->    (binary) +, -

2. 잘못된 입력에 대한 에러 핸들링 : 짝이 맞지 않는 괄호, 잘못된 연산자, 정의되지 않은 기호, 수학적으로 잘못된 수식

 

TestCase 분석

일단 과제는 testCase를 통과하는 방향으로 구현해야 했기 때문에, 테스트케이스를 분석하며 시작했다.

// infix
16 - 14 % 19 + 21
97 % 52 * 81 - 25 - 95

// infix -> postfix + result 
- 2749 / 3481 * - 59 + 7080
- - 3171 - - 2500 - - - 1894 + 9673 ^ 1

2749 ~ 3481 / 59 ~ * 7080 +
7080
3171 ~ ~ 2500 ~ - 1894 ~ ~ - 9673 1 ^ +
13450

// infix
1041 - 1668 ^ 3 - 3069
( 2971 + 3717 / 5468 + ( 1592 * ( 5394 ) ) )
( 8589 % 7370 * 1026 ) + 3117 % 2956 % ( 7609 )
2133 - 5081 % ( 5979 / ( 310 * 4030 / 7432 + ( 2876 ) ) )

// infix(error handling)
-%%%-+-
/(*-*)/
+-+-+-+-+

// infix + postfix
( - 4149 % 5036 * ( 4745 / 7934 % 3298 ) + - 3570 - ( - 1167 + ( - 2219 + ( 8293 ) - ( - 7279 ) + - - 7157 ) % 1282 ) * ( - - 7892 % - 5442 * ( - - 6826 * 6047 ) + ( - - 8895 / 8426 ^ 3 + 3 / - - 702 ) - - 2485 / 6856 / - 5837 - - 3706 + ( 2603 % ( - - 2184 ) * ( - - 8250 ) % - 5871 ) - - 9955 % - - 6055 ) * ( 7198 ) / - 7005 ) % ( - 3612 ) - ( - - 3614 / ( - 3351 ) - 912 * ( 8170 + - - 162 ) + ( - - 8230 * - 512 ) * - 9444 ) * - 7614 - - 3981 + ( 8188 ) * - 3714 / - - 9707 / ( 5845 - 2747 ) / - 8168 % 4912 % ( 658 ) - 4186 % 9021 - 4549 + - 4829 + - - 4532 * 321 / - - 3326 - - 9449 / ( - - 2046 * ( 2810 ) / 4692 ) + ( - 1448 * ( 5309 ) - 8023 - 4083 / - - 3847 / - - 804 ) * 7484 ^ 2 + 3 - - - 5629 * ( - - 5440 / - 1497 ) * - - 7819 * - 7196 % - - 6755 * - 7152 - - 9515 * ( - - 5621 ) + 3403 - - - 8344 * - 870 - - - 8392 % - 9766 + ( - 6504 / ( - 147 + - 708 + - - 6156 ^ 1 + 1 ) - - 4503 + - - 306 ) % 3339 % ( - 2495 % ( - - 7203 ) - - - 257 ) - - - 2099 ^ 2 + 3 / - - 8951 / 4230 % ( - - 6101 ^ 1 + 1 )

4149 ~ 5036 % 4745 7934 / 3298 % * 3570 ~ + 1167 ~ 2219 ~ 8293 + 7279 ~ - 7157 ~ ~ + 1282 % + 7892 ~ ~ 5442 ~ % 6826 ~ ~ 6047 * * 8895 ~ ~ 8426 3 ^ / 3 702 ~ ~ / + + 2485 ~ 6856 / 5837 ~ / - 3706 ~ - 2603 2184 ~ ~ % 8250 ~ ~ * 5871 ~ % + 9955 ~ 6055 ~ ~ % - * 7198 * 7005 ~ / - 3612 ~ % 3614 ~ ~ 3351 ~ / 912 8170 162 ~ ~ + * - 8230 ~ ~ 512 ~ * 9444 ~ * + 7614 ~ * - 3981 ~ - 8188 3714 ~ * 9707 ~ ~ / 5845 2747 - / 8168 ~ / 4912 % 658 % + 4186 9021 % - 4549 - 4829 ~ + 4532 ~ ~ 321 * 3326 ~ ~ / + 9449 ~ 2046 ~ ~ 2810 * 4692 / / - 1448 ~ 5309 * 8023 - 4083 3847 ~ ~ / 804 ~ ~ / - 7484 2 ^ * + 3 + 5629 ~ ~ 5440 ~ ~ 1497 ~ / * 7819 ~ ~ * 7196 ~ * 6755 ~ ~ % 7152 ~ * - 9515 ~ 5621 ~ ~ * - 3403 + 8344 ~ ~ 870 ~ * - 8392 ~ ~ 9766 ~ % - 6504 ~ 147 ~ 708 ~ + 6156 1 ^ ~ ~ + 1 + / 4503 ~ - 306 ~ ~ + 3339 % 2495 ~ 7203 ~ ~ % 257 ~ ~ - % + 2099 2 ^ ~ ~ - 3 8951 ~ ~ / 4230 / 6101 1 ^ ~ ~ 1 + % +
-128084970207258

 

위를 보면 알 수 있듯, 각 입력은 공백으로 구분되어 있으며 연속된 연산자, 연속된 숫자, 과도한 공백 등이 섞여서 입력되기 때문에 이런 입력에 대한 handling을 하는 일에 시간이 많이 소모되었다. 에러로 판단되면 바로 Catch하여 "Error"를 출력 후,  다음 입력을 받아야 한다.

 

전체적인 설계는 infix to Postfix의 기능, Prefix의 결과값을 계산하는 기능을 가진 Class를 만드는 방향으로 진행했다.

 

String Parsing

우선은 한 줄로 입력되는 문자열을 이용하기 적당한 형태로 parsing해줘야 했다.

replaceAll("\\s+", " ");을 사용해서 input에 존재하는 중복된 공백들을 하나의 공백으로 replace해줬다.

 

이후 StringTokenizer를 이용해서 모든 연산자 + 공백으로 문자열을 token화 했고, StringTokenizer가 다음 토큰을 가지고 있다는 조건으로 반복문을 돌려서 postfix로 전환하는 메서드를 실행했다.

 

Infix to Postfix

ChangeExpression 클래스는 postfix로 전환하는 과정에서 operator를 쌓아둘 stack<String>을 가지고 있고, postfix를 저장할 String[]을 가지고 있으며 남아있는 열린 괄호의 갯수를 판단하는 braceCount 변수를 가지고 있다.

 

전체적인 로직의 방향성은 아래와 같다.

1. 현재 토큰이 피연산자이면 그냥 postfix 배열에 저장한다.

2. 연산자이면 스택에 저장된 연산자와 비교하여 우선순위에 따라 push(), pop() 여부를 결정해준다. 우선순위가 높으면 스택에 넣고, 아니라면 스택에 저장된 연산자를 postfix 배열에 넣어준다.

3. 2의 과정에서 비교는 연산자가 없을 때, 또는 열린 괄호를 만날 때까지 지속한다.

4. 연산자로 갇힌 괄호로 들어오면, 열린 괄호가 나올 때까지 안에 있는 연산자들을 postfix로 보내준다.

5. token을 모두 검사한 다음, 스택에 남은 연산자들을 postfix 배열에 저장해준다.

 

여기서 binary '-'와 unary '-'는 입력 형태는 같지만 속성은 다르기 때문에 '-'가 어떤 연산자인지 판단하는지에 대한 로직을 구상해줘야 했다. 노트에 직접 여러가지 경우의 수를 두고 다이어그램을 그려봤고, '-'가 연속적으로 입력되거나, 이전 token이 operator였거나(앞을 포함) 하는 경우에 unary로 판단하면 된다고 생각했다. unary - 에 더해서, right-associative인 ^(power) 연산자도 다른 연산자와 다른 방식으로 처리를 해줘야 했다.

또한 연산자가 token으로 연속해서 들어오는지에 판단하는 변수, 괄호의 짝이 맞는지에 대한 변수를 두고 맞지 않으면 exception을 throw했다.

 

Calculate Postfix

메서드 하나를 만들어서 opernands를 쌓아둘 stack을 두고, 각 연산자에 따라 결과값을 return하여 다시 stack에 쌓아두는 식으로 결과값 계산을 진행했다.

 

연산자에 따른 return값을 만들어 줄 때, 수학적으로 잘못된 입력이 들어오면 Exception을 throw했다. 또한 unary와 binary에 따라 호출하는 메서드를 달리 하여 pop()을 몇 번 해야하는지도 구분했다.

 

일단 전반적인 로직을 짜는 일도 쉽지 않았지만, Error Handling을 하는 일에도 시간이 많이 들었다.

 

느낀점

무턱대고 코드를 짜기 시작하지 말기. 전체적인 로직에 대한 윤곽을 그리고 시작하는 것이 후에 Error Handling 상황에도 유연하게 대처할 수 있다. 애초에 Error Handling도 기능의 일부라고 생각하고 시작해야 한다.

 

각각의 에러에 대한 상황을 property를 두고 조건을 걸어서 체크해줬는데, 에러의 케이스가 많아지니 이러한 property를 종합적으로 판단하기가 어려웠다. 프로퍼티가 많아지니 값을 언제 초기화해주고 체크해야하는지에 대한 관리에 무리가 생겼다.

 

메서드를 조금 더 잘게 나누고 싶었는데, 처음에 코드를 무턱대고 짜기 시작해서 반복적인 부분에 대한 구조화를 하는 것이 거의 불가능했다. 앞으로는 답답해도 조금 더 생각하고 개발을 시작하자...