컴퓨터는 순서대로 데이터를 읽기 때문에
인간이 사용하는 infix 형태의 수식에서 연산자의 우선순위를 고려한 형태의 수식인 postfix로 변환이 필요하다.
infix : 숫자(=피연산자)와 숫자(=피연산자) 사이에 연산자가 위치 ex) 1+1
postfix : 숫자(=피연산자)가 나오고 연산자가 위치
이번 포스팅에는 infix 수식을 postfix 수식으로 변환하는 과정을 통해 Stack 자료구조를 정리해보려고 한다.
메인함수에서는 수식을 입력받고 convert함수를 호출하여 입력받은 infix수식을 전달하여 postfix배열에 받아 계산결과를 출력한다.
스택은 책을 탑처럼 쌓아 올리는 것과 같은 자료구조로 가장 나중에 쌓은 책부터 치울 수 있는 Last In, First Out 의 순서를 가진다. (책을 stack으로 쌓는 아이가 공부를 못한다라는 연구가 있다..)
이를 코드로 구현하기 위해서 배열에 데이터를 저장하는 push 함수와, 데이터를 추출하는 pop 함수를 추가하였다. 데이터가 저장될 위치는 top으로 전역변수로 선언하였으며 데이터를 저장할 때는 top을 +1 증가하고 배열에 저장, 추출할 때는 데이터를 추출하고 -1을 감소시킨다.
그리고 배열의 길이는 MAXSTACK으로 TOP의 위치가 MAXSTACK-1인 경우 배열의 가장 마지막을 의미하기 때문에 STACK FULL을 출력한다.
convert 함수는 infix를 postfix로 변환함수로 반복문을 실행하기 전, postfix 저장위치를 가리킬 cnt변수를 초기화하며, stack의 끝을 알리기 위하여 EOS를 stack에 저장한다. 반복문은 infix에 더 이상 변환할 수식이 없을 동안 반복된다. ( for(int i=0; infix[i]!=0; i++) )
1. 간결한 코드를 위해 token에 infix[i]를 저장한다.
2. 숫자를 판단하는 함수인 isDigit을 선언하여 token이 숫자인지 판별한다. (다음 단락에서 함수 소개)
token이 숫자라면 token을 바로 postfix 배열에 저장하고 cnt를 증가시킨다.
3. token이 숫자가 아닌 경우 연산자들의 우선순위를 판단하여 postfix에 저장한다.
⓵token이 ‘)’인 경우, stack에 저장된 연산자 중 괄호 시작까지의 모든 연산자를 postfix 배열에 저장한다.
이는 괄호안의 연산이 가장 우선되어야 하기 때문이다 ex) 1x(2+3) -> 의 경우 2+3 계산이 선행되어야한다. 따라서 괄호 시작까지의 연산자를 모두 postfix에 넣어준다. cnt의 위치가 괄호 시작의 경우 수행할 연산이 없기 때문에 덮어쓸 수 있도록 cnt를 감소시키고 다음 token을 검사한다.
⓶token이 연산자인 경우, stack에 저장되어야 하지만 연산이 실행되어야하는 순서를 비교해가며 push할 필요가 있다.
예를 들어 2+3 x 4 에서 3 x 4 가 우선으로 실행되어야 함으로 순서대로 데이터를 읽는 postfix에는 +보다 먼저 저장되어야 한다.
따라서 stack에 저장되어있던 연산자의 우선순위와 token의 우선순위를 비교하여, stack에 저장되어 있던 연산순위가 높거나 같다면 먼저 postfix에 저장한다. (getStackPriority는 스택의 데이터 우선순위 파악, getpriority는 token의 우선순위를 파악한다, 다음단락에서 설명)
⓷위의 조건에 모두 해당하지 않는 경우 stack에 token을 저장한다.
-> 여기서 연산자가 처음으로 스택에 저장되고 다음 연산자가 나왔을 때 ⓵,⓶ 과정에서 postfix로 저장된다.
4. infix의 모든 내용이 postfix 또는 stack으로 옮겨졌을 때 반복문이 종료되고 stack에 남은 모든 연산자를 postfix 스택으로 옮겨준다. 이는 마지막으로 postfix 저장된 값이 EOS일 때까지 실행된다.
isDigit함수는 매개변수로 건네받은 데이터가 숫자인지 아닌지 알려주는 함수로 숫자라면 1을 반환하고, 숫자가 아니라면 0을 반환한다. 데이터는 char형 변수이기 때문에 아스키코드 값에 있는 문자 0에서 9사이에 있는지 확인한다.
getPriority는 infix 배열 속 연산자의 우선순위, getInStackPriority는 stack 배열 속 연산자의 우선순위를 반환한다. 한 가지 차이점은 괄호 시작 ‘(’의 우선순위가 stack안에서는 가장 낮게 변한다는 점이다. 이는 수식에 괄호가 있는 경우 괄호 안의 내용이 먼저 계산되어야 하기 때문이다.
evaluate은 postfix에 저장된 새로운 수식을 매개변수로 받아 연산을 실행하여 계산결과를 반환한다.
반복문은 postfix에 더 이상 계산할 내용이 없을 때 종료된다.
1. 간결한 계산을 위해 token에 postfix[i]값을 저장한다.
2. token이 숫자인 경우( if(isDigit(token)), stack에 token을 숫자형으로 변환하여 저장한다. *****
token-‘0’ 의 연산은 문자로 저장된 숫자를 숫자로 변환하는 것으로 stack에는 정수형 숫자가 저장된다.
3. token이 연산자인 경우( else ), 현재 위치 이전의 두개의 피연산자를 불러와 token값으로 연산을 실행, 다시 stack에 저장한다.
먼저 pop함수를 호출한 것이 op1이기 때문에 op1이 나중에 stack에 저장된 숫자라는 것을 알 수 있다. 따라서 연산자에 따라 op2에서 op1을 계산하고 이를 다시 stack에 저장한다.
ex) infix 3-2 -> postfix에서는 3 2 - , 이를 다시 stack에 push하여(*****분기에 따라) 2 3 로 저장됨
이 경우 token : - , op1=2, op2=3 이 된다.
4. postfix에 더 이상 계산할 내용이 없을 때 반복문이 종료된다. 모든 계산 결과 값은 stack에 저장되어 있을 것이므로 마지막으로 저장된 결과를 pop함수 호출 통해 반환한다.
postfix를 통해 스택과, 컴퓨터의 연산과정에 대하여 이해할 수 있었다. 현재는 한 자리 숫자에 대한 연산만이 가능했다. 만약 두 자리, 세 자리 숫자 연산은 어떻게 할 수 있을까?
'Computer > Data structure' 카테고리의 다른 글
| [C언어 자료구조] 선택정렬, 이진탐색 (술자리 게임처럼 간단하게 이해하기) (0) | 2022.04.11 |
|---|