큰 수 계산기 간단하게 만드는 알고리즘 기법.

스택을 구현하여 간단하게 큰 수 계산이를 구현할 수 있다.

스택을 다음과 같이 구현한다.

int stack[100000];
int top = -1;
void push(char data){
 stack[++top] = data;
}
void pop(void){
 top--;
}

다음과 같은 구조에서 char 형 300과 20을 2개의 배열에 push 하면

 

 

다음과 같은 2개의 스택이 구현된다.

여기서 중요한 것은 자리수가 다른 것이 입력되더라도 스택을 pop하는 과정에서 자리수가 자연히 일치한다는 것을 확인할 수 있다. 즉 pop을 할 때마다 연산을 하면 정확하고 간결하게 계산을 할 수 있게 된다는 의미이다. pop을 하여 데이터를 더할 때 10이 넘으면 다음 pop 되는 것을 +1을 처리해주고, 뺄 때 마이너스가 되면 다음 pop 되는 것을 -1을 처리해주는 방식이다. 위와 같은 자리는 100000 배열이므로 100000 자리를 시스템 상에서 쉽게 연산을 하고 표현할 수 있다.

이러한 연산의 단위는 단지 순차적인 pop이기 때문에 O(n)에서 해결할 수 있다.