[자료구조] 계산기 C코드 (괄호포함,스택)

오늘은 계산기를 해보곘습니다.

지금에서야 올리는 여러가지 이유가 있지만 ^^ 많이 방문해주세요 ^^

​

계산기에 없는 기능 :

2자리 이상 계산은 안됨( 사실 2탄으로 한번 더 빼먹으려고 참는중)

13/36은 안됨. but 기본 연산 됨

이런 느낌으로 보면 됩니다.

​

아마 여기까지 찾아온거면

기본적인 중위표기식 -> 후위표기식 바꾸는건 다 알것이라고 생각합니다.

stack은 C로 그냥 가볍게 구현하시면 됩니다. (나중에 포스팅해서 여기에 링크 걸 예정)

​

구현의 핵심

1. infix -> postfix로 바꿔야함

2. 연산자 우선순위 고려해야함

​

구현 방법

1. 처음에 expression을 배열로 받는다

2. 연산자 스택, postfix 배열을 만든다

3. '숫자'면 postfix 배열로 바로 보낸다

4. '괄호' 또는 '연산자' 는 스택으로 보내서 처리를 한다. (이때 연산자 우선순위를 고려한다)

​

​

연산자 우선순위

-> ex) 3*2+5

연산자만 다루는 스택내에서 *가 들어가있다가 +가 들어오면 재빨리 순서를 바꿔줘야 하는데요.

이런것을 고려해서 짜야하는데 코드 3줄이면 짤 수 있답니다!! (오우!!)

​

연산자 우선순위 생각해야할것

1. 일단 괄호 ')'가 들어오면 '(' 가 나올때까지 계속 연산자 스택에서 계속 pop을 해주어야 합니다.

-> 괄호 ')'까지 빼는 중간에 + - * / 가 나오더라도 얘네들을 다 밖으로 뺄 정도로 힘이 강해야 합니다

이 말은 ')' 의 우선순위가 제일 높아야 한다는 말입니다.

​

2. +,- 보다 *,/ 가 먼저 계산되어야 합니다

-> 연산자 스택에 +,- 가 들어가있다가 *,/ 를 만나면 순서를 바꿔주어야 합니다. (사진으로 이해해 보세요)

잘 이해가 되지 않는다면 아래 내려가서 코드 및 설명을 읽고 오면 뭔말인지 이해가 될 것입니다.

스택의 top 부분으로 갈수록 연산자 우선순위가 높아야 합니다.

이 부분을 생각해보면 왜 return값이 저렇게 됐는지 알 수 있습니다.

만약 연산자 우선순위를 고려하지 않았다면?

postfix 배열 : 3 2 5 + *

결과 = 21 (전혀 다른 답)

 

#include<cstdio>
#include<stack>
#include<string.h>
double calc(char* arr)
{
	std::stack<double> fs;
	double op1,op2;
	int len = strlen(arr);
	
	for(int i=0 ; i<len; i++)
	{
		if(arr[i]>= '0' && arr[i]<= '9')
		{
			fs.push(arr[i] - '0');
		}else if(arr[i]=='*' || arr[i]=='/' || arr[i]=='+' || arr[i]=='-')
		{
			op1 = fs.top();
			fs.pop();
			op2 = fs.top();
			fs.pop();
			//op1과 op2가 숫자가 아니라면 표현식의 오류가 됨. 
			switch(arr[i])
			{
				case '*' :
					fs.push(op2*op1);
					break;
				case '/' :
					fs.push(op2/op1);
					break;
				case '+' :
					fs.push(op2+op1);
					break;
				case '-' :
					fs.push(op2-op1);
					break;
			}	
			//op2 와 op1을 연산해야함 (순서 중요), 계산해서 다시 집어넣음. 
		}
	}
	return fs.top();
}
int rank(char c){
	if(c=='(') return 1;
	else if(c=='+' || c=='-') return 2;
	else return 3;
//반드시 1,2,3이 아니어도 됨. 500, 600 ,900만 이어도 상관없음 a<b<c 만 만족하면 됨.
}
char* inToPost(char* arr)
{
	std::stack<char> cs;
	int len = strlen(arr);
	char* res = new char[len];
	int index=0;

	for(int i=0;i<len;i++)
	{
		if(arr[i]>='0' && arr[i]<='9')
		{
			res[index++] = arr[i];
		}else if(arr[i]==')'){
			while(cs.top()!='('){
				res[index++]=cs.top();
				cs.pop();
			}
			cs.pop();//괄호 버림 
		}else{//플마 더하기 빼기
			while(!cs.empty() && arr[i]!='(' && (rank(arr[i]) <= rank(cs.top()))){
				// 부등호 < -> <= 로 수정  why : * / 로만 이루어져 있을때도 순서 지키려면 미리 빼야함. 1/3*3 이  0.11로 나왔었음(이전에) 
				res[index++] = cs.top();
				cs.pop();
			}
			cs.push(arr[i]);
		}
	} // 숫자는 배열, 연산자는 스택에 나눠담는과정 마무리
	
	while(!cs.empty())
	{
		res[index++]=cs.top();
		cs.pop();
	} 
	//배열에 다 담음. 
	printf("%s\n",res); // postfix 보여주기 싫으면 여기 지우면 됨 
	return res;
}
int main(int argc,char** argv)
{
	
	char input[101];
	char* postres;
	double res;
	int size=0;

	scanf("%s",input);
	postres = inToPost(input);
	
	res = calc(postres);
	
	
	printf("%.2lf",res);

	
	return 0;
	
}

코드 설명

else if(arr[i]==')'){

while(cs.top()!='('){

res[index++]=cs.top();

cs.pop();

}

cs.pop();//괄호 버림

​

-> ' )' 를 만났을때 '('를 만날때까지 계속 뺴주라는 말입니다. while문에서.

맨 마지막에 '('면 while문이 멈추므로 pop을 한번 더 해서 '('를 최종적으로 제거합니다.

​

while(!cs.empty() && arr[i]!='(' && (rank(arr[i]) <= rank(cs.top()))){

// 부등호 < -> <= 로 수정 why : * / 로만 이루어져 있을때도 순서 지키려면 미리 빼야함. 1/3*3 이 0.11로 나왔었음(이전에)

res[index++] = cs.top();

cs.pop();

}

cs.push(arr[i]);

​

->

1. !cs.empty()는 맨 처음 연산자가 들어올 경우에는 바로 넣어주라는 뜻입니다.

2. '(' 인 경우에는 그냥 바로 연산자 스택으로 넣어줍니다. (연산자 우선순위 함수를 보면 최하위로 지정해놨습니다)

3. rank 비교는 연산자 우선순위를 사용하는 부분입니다.

예시를 들어볼게요. 3*2+5 인 경우입니다.

​

만약 연산자 우선순위 함수가 없을경우

스택에 * , + 순서로 들어가게 되어 pop 시에 + * 로 나오게 됩니다.

즉 325+*이 되어 결과가 전혀 다른것이죠.

​

만약 연산자 우선순위가 있다면 ?

스택에 *가 있을때 rank(arr[i]) <= rank(cs.top()) 를 비교하면 rank('+') <= rank('*') 이므로

32*5+ 의 결과가 나오게 됩니다.

​

왜 <가 아닌 <= 인가??

1/3*3 을 할때 오류가 납니다.

stack에 /가 들어가있고 *를 만났을때 =이 없어서 /가 빠지지 않습니다.

따라서 postfix가 133*/ 가 나와서 1/9가 나옵니다.

​

=이 존재하면

13/3*이 멀쩡하게 되어서 1이 나온답니다.

​

감사합니다

====END

​

blog.naver.com/rbals0445/222199319406