2-4 미니 프로젝트

계산기

• 괄호 없이 문자열로 계산식 입력받기
• 공백 제거하기
• 공백 제거한 문자열은 중위표기법이라 후위표기법으로 바꾸기
  • 연산자 우선순위를 비교해야 스택1에서 어떤 연산자를 먼저 빼낼지 확인 가능함
  • 예시
    • A + B * C => A B C * +
    • A * B + C => A B * C +
    • 10 - 5 + 2 * 11 => 10 5 - 2 11 * + = 27
    • 100 - 10 / 2 * 10 / 4 + 10 => 100 10 2 / 10 * 4 / - 10 + = 98
• 후위표기법으로 전환된 수식 문자열 계산하기 (스택2 이용)
  • 연산자를 만나면 숫자를 2번 pop하고, 그 결과를 스택에 push함

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CHAR_TO_INT(X) (X - '0') //char(0~9)=ascii(48~57)
enum { MAX_LENGTH = 1024, MAX = 100, TRUE = 1, FALSE = -1 };

int stack_op[MAX];						//연산자 스택 (스택1)
int stack_calc[MAX];					//수식 계산 스택 (스택2)
int top;								//스택 현재 위치

void InitStack();						//스택 초기화
int Push_op(int data);					//연산자 Push
int Push_num(int data);					//숫자 Push
int Pop_op();							//연산자 Pop
int Pop_num();							//숫자 Pop

int GetTop();							//top 위치 받기
int EmptyTop();							//top 비어있는지 검사
int IsOperator(char c);					//연산자인지 검사
int IsNumber(char c);					//숫자인지 검사
int Level(char c);						//연산자 우선순위 비교
void Change(char* dest, char* src);		//중위표기법(src)에서 후위표기법(dest)으로 변환
int Calculate(char* c);					//후위표기법 수식 계산

int main()
{
	int ch;
	int i = 0;
	char input[MAX_LENGTH];
	char output[MAX_LENGTH];
	int result = 0;

	while ((ch = getchar()) != '\n') //엔터 전까지 입력 받기
		if (ch != ' ') //공백 제거
			input[i++] = ch; //공백 제거된 문자만 입력 넣기
	input[i] = '\0'; //마지막에 널문자 추가
	Change(output, input); //후위식으로 변환
	result = Calculate(output); //계산
	printf("= %d\n", result);
	return 0;
}

void InitStack()
{
	top = -1; //top은 비어있음
	//배열이 0부터 시작하기 때문에 0은 데이터가 하나 들어있는 상태로 지정함
}

int Push_op(int data)
{
	if (top < MAX - 1) { //top이 스택의 마지막 요소보다 작을 때만 푸시함
		++top; //top 1 증가
		stack_op[top] = data;
		return TRUE;
	}
	else
		return FALSE; //스택 오버플로우
}

int Push_num(int data)
{
	if (top < MAX - 1) {
		++top;
		stack_calc[top] = data;
		return TRUE;
	}
	else
		return FALSE;
}

int Pop_op()
{
	if (top >= 0)
		return stack_op[top--]; //top 위치값 읽기, top 1 감소
	else
		return FALSE; //스택 언더플로우
}

int Pop_num()
{
	if (top >= 0)
		return stack_calc[top--];
	else
		return FALSE;
}

int GetTop()
{
	return (top >= 0) ? stack_op[top] : FALSE;
}

int EmptyTop()
{
	return (top < 0);
}

int IsOperator(char c)
{
	return (c == '+' || c == '-' || c == '*' || c == '/');
}

int IsNumber(char c)
{
	return (c >= '0' && c <= '9');
}

int Level(char c) // *,/ 은 +,- 보다 우선순위가 높음
{
	if (c == '+' || c == '-')
		return 1;
	if (c == '*' || c == '/')
		return 2;
	return 0;
}

void Change(char* dest, char* src)
{
	InitStack();

	while (*src != '\0') {
		if (IsOperator(*src)) { //들어온 데이터가 연산자일 때
			while (!EmptyTop() //연산자 스택이 비어있지 않는 조건과
				&& Level(GetTop()) >= Level(*src)) {
				//연산자 스택 0번째와 갓 들어온 1번째 비교 후 0번째가 빠져나가도 되는 조건일 때
				*dest = Pop_op(); //연산자를 빼내어 dest값에 입력함
				dest++;
				*dest = ' '; //두자리 이상 수를 받을때 헷갈리니까 분리함
							 //10-5 => 105- => 10_5-
				dest++;
			}
			Push_op(*src);
			src++;
		}
		else if (IsNumber(*src)) { //들어온 데이터가 숫자일 때
			do {
				*dest = *src; //값 입력
				dest++;
				src++;
			} while (IsNumber(*src));
			*dest = ' ';
			dest++;
		}
		else
			src++;
	}

	while (!EmptyTop()) { //기존 문자열을 다 읽었는데, 연산자 스택에 연산자가 남아있을 때
		*dest = Pop_op();
		dest++;
		*dest = ' ';
		dest++;
	}
					//10_5-_2_11_*_+_
	dest--;			//10_5-_2_11_*_+
	*dest = '\0';	//10_5-_2_11_*_+'\0'
}

int Calculate(char* c)
{
	int i;
	int temp; //뺄셈, 나눗셈을 위한 임시 공간

	InitStack(); //stack_calc(스택2) 위해 top=-1로 초기화함

	while (*c != '\0') {
		if (IsNumber(*c)) {
			i = 0;
			do {
				i = i * 10 + CHAR_TO_INT(*c);
				c++;
			} while (IsNumber(*c)); //공백 또는 연산자가 나올 때 까지 두자리 이상 수 계산
			temp = i;
			Push_num(temp); //스택2에 저장
		}
		else if (*c == '+') {
			Push_num(Pop_num() + Pop_num());
			c++;
		}
		else if (*c == '*') {
			Push_num(Pop_num() * Pop_num());
			c++;
		}
		else if (*c == '-') {
			temp = Pop_num();
            Push_num(Pop_num() - temp);
			c++;
		}
		else if (*c == '/') {
			temp = Pop_num();
            Push_num(Pop_num() / temp);
			c++;
		}
		else //분리하기 위해 넣은 공백은 건너뛰기
			c++;
	}
	
	return Pop_num(); //stack_calc에 남은 계산 결과
}