'연산자우선순위'에 해당되는 글 1건

컴퓨터를 정리하다보니, 또 재미난 소스가 있어서 올려본다.


바로 이전 포스트 다항식 연산은 아주 간단한 과제였는데, 지금 보니 계산기를 만들어라는 과제도 있었던 것 같아서 찾아보니 역시나 있다.


내 기억에 이 과제를 하면서, "아! 계산기가 이렇게 복잡하게 동작하는거였어???" 하면서 힘들어했던 10년전의 내모습이 떠오른다 ㅎㅎㅎ


저 깨알 같은 주석들..., 주석이 코드보다 더 많다 ㅎㅎㅎㅎ



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 제작기간 : 2002.10.9 ~ 2002.10.13                                                                          
// 사용가능 연산자 : {"!","&&","||","==","!=","<",">","<=",">=","^","*","/","%","+","-","@"},(,)   
// 지원가능한 수식의 길이 : 80으로 설정됨(수정가능)                                                   
// 특이사항: 수식 오류 검사                                                                                     
// 지원 operand : -9에서 9까지(수정가능)                                                                 
// 입력 : c:\data 파일                                                                              
// 사용언어 및 컴파일러 : Visual C++ Enterprise,(C언어 구조 사용)                                                       
// 테스트 환경 : Intel Pentium3 866MHz                                                                                 
//               512MB Memory                                                                                           
// Test 내용 : Report파일 첨부                                                                                         
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>  //기본 입출력 함수사용을 위해
#include <string.h> //스트링 조작 함수사용을 위해
#include <stdlib.h> //atoi() 입력받은 문자를 정수로 변환하기 위한 함수사용을 위해
#include <math.h>   //pow()사용을 위해

#define MAX_EQS_SIZE 80  //입력받는 수식의 최대길이를 80으로 설정한다.
                         //예를 들어 9*1-8+1*(-1)은 12가 된다.
#define DATAFILE "C:\\data" //입력 파일을 정의
#define OPERATOR 1   //OPERATOR 라는 값을 1로 설정(스택 연산시에 쓰기 위해 )
#define OPERAND 0    //OPERAND 라는 값을 0으로 설정(스택 연산시에 쓰기 위해)

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//전역변수 변수선언부

static char operator_priority_table[16][3]={"!","&&","||","==","!=","<",">","<=",">=","^","*","/","%","+","-","@"};
 //메모리의 낭비가 있더라도 ,길이가 2인 연산자가 있어서 배열로 선언 했음.
 //15개의 연산자 우선순위 선언(@:연산자우선순위끝)
 //논리,비교,산술연산자들의 우선순위대로 배열에 저장(비주얼씨 도움말참조)
 //부정부호 (-) 따로 처리
 //지수연산은 연산 방향 right --> left 을 고려해서 처리할것
 //나중에 새로운 연산자를 추가 할경우에는 우선순위를 고려하여서 추가하고, 배열의 1차원 크기를 조정해줄것.
static char can_be_first[3]={'(','-','!'}; //수식의 처음에 올수 있는 operator들을 정의, '-'가 제일 처음오면 부호로 처리
static char can_be_last[1]={')'};          //수식의 마지막에 올수 있는 operator를 정의
static char can_be_after_operator[2]={'(','!'};   //operator 뒤에 올수 있는 operator 정의,
                                                  //그리고 이들은 operand뒤에는 올수없다.

char output[MAX_EQS_SIZE];             //변환된 수식 저장
int output_flag=0; //결과 식을 출력할지 안할지 셋팅 0:출력안함 ,1:출력(마지막 스텝에서 1로 셋팅)

char eqs[MAX_EQS_SIZE];                //수식을 저장하기 위한 문자열변수를 선언한다.
char operator_stack[MAX_EQS_SIZE][3];  //operator의 스택을 선언
int operand_stack[MAX_EQS_SIZE];       //operand의 스택을 선언
int top_of_operator_stack=-1;          //operator스택의 top선언
int top_of_operand_stack=-1;           //operand스택의 top선언
int top_operand=0;                     //top_operand 선언
int temp_operand=0;                    //오퍼랜드 임시 저장을 위해
char top_operator[3]={""};             //top_operator 선언
char top_new_operand[6]={""};          //계산된 결과 값을 새로운 오퍼랜드함수에 저장하기 위해서.	
int pairs_Gualho=0;            //괄호의 짝이 맞아야 한다.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//함수 선언부

void process(); //operand 두개를 operator로 계산하는 함수
int is_next_correct_operator(char,char) ; //operand 다음에 오는 연산자가 올바른 것인지 검사 
void correct_operator(char,char); //operator뒤에 다른 operator가 올때 바른 연산자인지 검사 (can_be_after_operator참조
int is_operand(char);             //operand인지 검사 1:true 0:false
int is_operator(char *);          //operator인지 검사 1:true 0:false
int empty(int);                 //스택이 비었는지 검사    입력:operator_stack은 1,operand_stack은 0 : empty=1
int full(int);                  //스택이 가득 찾는지 검사 입력:operator_stack은 1,operand_stack은 0 : full=1
void scan_eqs();                //수식을 스캔하는 루틴
void error_eqs(int);                       // 수식의 오류메세지 출력 입력이 1이면 오류 없음,무시, 그렇지 않으면 오류 있음
int compare_operator(char *isp,char *icp); //  2 isp,icp우선순위가 같다.
                                           //  0: isp가 우선순위가 높다.
                                           //  1: icp가 우선순위가 높다.
void compute(int sign,char *token);//토큰을 가지고 계산하는 함수. sign에는 토큰이 '-'일때 부호인지 연산자인지 지정.
                                   //process호출
                                   //특별한 경우 를 검사 ('^','(',')','!')이런 경우에는 다른 조치를 취한후 process호출
int pop_operand();     //operand를 팝하는 함수
char *pop_operator();  //operator를 팝하는 함수
void push(char *token,int type); //푸시 함수 type는 operand인지 operator인지 지정
void print_status(int);          //스택의 상태, 결과값, postfix output을 출력하는 함수
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////                                       
//main()의 시작
//파일을 열어서 수식을 입력받아서 배열에 저장한다.
//수식의 끝을 알려주는 '#'를 만듬.
//scan_eqs함수 호출

void main()
{
	int i=0;                 //수식의 배열 위치를 가리키기 위한 변수선언
	FILE *data;              //파일으로 부터 입력을 받기 위해서 파일 포인터 선언.

	if((data=fopen(DATAFILE,"r"))==NULL){      //지정 위치의 파일을 열지 못 할 경우에 에러 메세지 출력
		printf("\n파일을 열수가 없습니다.\n");  
		exit(0);
	}
    
	while(!(feof(data))) //파일로 부터 수식을 입력받는다.
	{
	    
		eqs[i]=fgetc(data);//파일의 수식들을 문자 하나 하나씩 입력받아서 배열에 저장한다.
	    if(eqs[i]==' ') //공백이 있을경우에는 i의 값을 하나 줄여주는 트릭을 사용해서 공백을 제거한다.
			i--;
		i++;
	}
	fclose(data);//파일을 닫는다.이제는 파일이 더이상 필요없으므로.
	eqs[i-1]='#'; //End of String의 값을 #로 셋팅함
	eqs[i]=NULL;  //문자열의 끝에 널문자를 추가해준다.
	printf("\n입력받은 수식은 %s 입니다.\n",eqs);//입력받은 수식을 확인하기 위해서.
	scan_eqs();  //infix수식을 postfix로 변화하고 계산한후 결과를 출력함수를 호출한다.	
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//scan_eqs()정의
//토큰을 분리해서 compute()함수
//처음에 올수 있는 연산자인지 검사하고,마지막에 올수 있는 함수 인지 검사
//올바른 연산자인지 검사
//올바른 operand 인지 검사
void scan_eqs()//한번의 스캔으로 ibfix->postfix변환,연산 수행
{
	char token[3]={""};//토큰을 저장할 공간 마련 길이가 3인 문자열 변수
	int i=0,j=0,flag=0;//i는 배열에 저장된 수식을 읽어오기 위한것, flag는 수식의 오류를 검사 1:오류 없음,0:오류 있음
    

	token[0]=eqs[0]; //수식의 처음에 올수 있는 수식을 확인해서 오류 확인을 위해서.처음 토큰을 검사한다.
	j=0;
	while(j!=(sizeof(can_be_first)/sizeof(can_be_first[0])))//처음에 올수있는 연산자갯수만큼 루트
	{
		if(token[0]==can_be_first[j])//처음에 올수 있는 연산자일경우는 오류없음
		{
			flag=1;
		}
		else if(is_operand(token[0]))//operand일경우도 오류 없음
		{
			flag=1;
		}
		j++;
    }
	
	error_eqs(flag);//에러 있는지 없는지 확인후 에러메세지 출력
    
	while(flag&&(!(eqs[i]=='#')))//토큰 분리 루프
	{	
		int sign=0;    //토큰이 '-'가 왔을때 부호표시 인지 연산자인지 구분
		switch(eqs[i]) //Operator를 만드는 과정 오페레이터들의 길이가 1이 아닌것도 있으므로 스트링으로 통일해서 만든다.
                       //Str_Operand를 만드는 과정도 같이 포함 		
		               //오류 체크 과정도 포함 
					   //연산자가 올수 있는 규칙에따라서 오류를 검사한다.
			{
			     case '!'://!연산자의 경우 두가지가 있다 NOT(!),!= 그러므로 바로 뒤의 입력값도 확인 해볼것
					 {
						 token[0]='!';
						 if((eqs[i+1])=='=')
						 {
							 token[1]='=';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 token[1]=0;
							 token[2]=0;
						 }
						 correct_operator(eqs[i],eqs[i+1]);
						 break;			
						 
					 }
				 
				 case '&'://&&연산자 분리
					 {
						 token[0]='&';
						 if((eqs[i+1])=='&')
						 {
							 token[1]='&';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 error_eqs(0); 
						 }
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }
					 
				 case '|'://'||'연산자 분리
					 {
						 token[0]='|';
						 if((eqs[i+1])=='|')
						 {
							 token[1]='|';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 error_eqs(0); 
						 }
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }


				 case '='://'=='연산자 분리
					 {
						 token[0]='=';
						 if((eqs[i+1])=='=')
						 {
							 token[1]='=';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 error_eqs(0); 
						 }
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '>'://'>','>='연산자 구분 및 분리
					 {
						 token[0]='>';
						 if((eqs[i+1])=='=')
						 {
							 token[1]='=';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 token[1]=0;
							 token[2]=0;
						 }
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '<'://'<','<='연산자 구분 및 분리
					 {
						 token[0]='<';
						 if((eqs[i+1])=='=')
						 {
							 token[1]='=';
							 token[2]=0;
							 i++;
						 }
						 else
						 { 
							 token[1]=0;
							 token[2]=0;
						 }			
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '+'://'+'연산자 분리
					 {
						 token[0]='+';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '-'://'-'연산자 분리
					 {
						 token[0]='-';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 
						 if(((i==0)&&(is_operand(eqs[i+1])))||((i>0)&&(eqs[i-1]=='(')))
							 //'-'가 수식의 제일 처음에 오거나 괄호안에 오게 되면 음수로 표현
							 //다음의 나오는 토큰은 operand일때 token을 합쳐서 음수로 만듬 
						 {
							 token[1]=eqs[i+1];
							 token[2]=0;
							 sign=1;
							 i++;
						 }						 
						 break;
					 }

				 case '*'://'*'연산자 분리
					 {
						 token[0]='*';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '/'://'/'연산자 분리
					 {
						 token[0]='/';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '%'://'%'연산자 분리
					 {
						 token[0]='%';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '^'://'^'연산자 분리
					 {
						 token[0]='^';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case '('://'('연산자 분리
					 {
						 token[0]='(';
						 token[1]=0;
						 token[2]=0;
						 correct_operator(eqs[i],eqs[i+1]);
						 break;
					 }

				 case ')'://')'연산자 분리
					 {
						 token[0]=')';
						 token[1]=0;
						 token[2]=0;
						 
						 break;
					 }//of case
				 default://operand 분리
					 {
						 if(is_operand(eqs[i]))//operand가 들어오면
						 {
							 token[0]=eqs[i];
							 token[1]=0;
							 token[2]=0;
							 
							 if((is_operand(eqs[i+1]))||(!(is_next_correct_operator(eqs[i+1],eqs[i+2]))))
								 //operand는 두개가 연달아서 들어 올수 없으므로
								 //operand 다음에는 '('연산자와 '!'연산자만 올수 있다.
							 {
								 error_eqs(0);			 
							 }							 
						 }//of if						 
					 }//of default

	

			}//of switch

	        compute(sign,token);//연산 수행(sign은 음수 일경우를 나타내는 플래그이다.)
			printf("\nTOKEN STEP %d : %s ",i+1,token);//토큰 스텝을 출력
			print_status(i);//상태 출력			
			i++;
	}//of while
	
	token[0]=eqs[i-1]; //수식의 마지막에 올수 있는 수식을 확인해서 오류 확인을 위해서.마지막 토큰을 검사한다.
	j=0;
	flag=0;
	while(j!=(sizeof(can_be_last)/sizeof(can_be_last[0])))//마지막에 올수 있는 연산자의 갯수만큼 루프
	{
		if(token[0]==can_be_last[j])//마지막에 올수 있는 연산자의 경우에는 오류 없음
		{
			flag=1;
		}

		else if((token[0]<='9')&&(token[0]>='0'))//마지막에 operand가 와도 오류 없음
		{
			flag=1;
		}
		j++;
    }
	error_eqs(flag);//이상유무플래그 확인 후 에러 메세지 출력

	compute(0,"#");//마지막 eos토큰을 넣어 준다
	printf("\nTOKEN STEP %d : %s ",i+1,"#");//마지막에 나오는 결과 값은 다르게 표현함으로
	output_flag=1;//아웃풋의 내용을 출력하기 위한 플래그를 킨다.
	print_status(i);//마지막 상태 즉,결과 값과 변환 된 식을 출력한다.	    
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//process()정의

void process() //operand 두개를 operator로 계산하는 함수(compute함수에 의해서 호출 됨)
{
	int result=0;//연산 결과 값이 저장될 변수
	
	if(!empty(OPERAND))//operand가 있을때만 연산 수행
	{			
		top_operand=pop_operand();//연산을 하기 위해서 최소 하나의 operand가 필요하므로

		switch(top_operator[0])  //연산자가 선택
		{
			case '>': //>=연산자,>연산자
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					if(top_operator[1]=='=')
						result=(temp_operand>=top_operand);
					else						
						result=(temp_operand>top_operand);
					break;
				}

			case '<'://<=연산자,<연산자
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					if(top_operator[1]=='=')
						result=(temp_operand<=top_operand);
					else
						result=(temp_operand<top_operand);
					break;
				}
			case '!': //!=연산자,!연산자
				{
					if(top_operator[1]=='=')
					{
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand!=top_operand);
					}
					else
					{						
						result=(!top_operand);
					}
					break;
				}
			case '=': //==연산자
				{
					
					if(top_operator[1]=='=')
					{
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand==top_operand);
					}
					else
						result=0;
					break;
				}
			
			case '&': //&&연산자
				{
					if(top_operator[1]=='&')
					{
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand&&top_operand);
					}
					else
						result=0;
					break;
				}
				
			case '|': //||연산자
				{
					if(top_operator[1]=='|')
					{
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand||top_operand);
					}
					else
						result=0;
					break;
				}

			case '^'://지수연산
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					result=(int )pow(temp_operand,top_operand);
					break;
				}
			
			case '+'://더하기
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					result=(temp_operand+top_operand);
					break;				
				}
            
			case '-'://빼기
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					result=(temp_operand,top_operand);
					break;
				}
			case '*'://곱하기
				{
					temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
					result=(temp_operand*top_operand);
					break;
				}
			case '/'://나누기				
				{
					if(top_operand==0)//0으로 나눌수 없으므로
					{
						printf("\n0으로 나눌수 없습니다.");
						exit(0);
					}
					else
					{
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand/top_operand);						
					}
					break;
				}
			case '%'://나머지 연산
				{
					if(top_operand==0)//0으로 나눌수 없으므로
					{
						printf("\n0으로 나눌수 없습니다.");
						exit(0);
					}
					else
					{			
						temp_operand=pop_operand();//두개의 operand가 필요한 연산자는 하나 더 뽑아 낸다.
						result=(temp_operand%top_operand);						
					}
					break;				
				}
			default://아무것도 아니면 그냥 0을 리턴한다.(결과 값이 이상하게 나옴)
				result=0;				
		}//of switch
		itoa(result,top_new_operand,10);//정수를 문자열로 변환후 푸시한다.
		                                //푸시함수는 인자를 문자열(포인터)만 받을수 있기때문)
		push(top_new_operand,OPERAND);  //결과 값을 푸시
	}	

	else//operand가 없을경우에는 다시 top_roperator를 푸시 한다.
	{
		push(top_operator,OPERATOR);
	}
	
	
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//compute()정의

void compute(int sign,char *token)//push,pop를 결정,process함수 호출
{
	if(token[0]=='#')//EOS가 들어 오면 operand스택에 이있는 값을 모두 꺼내서 연산 수행한다.
	{
		if(pairs_Gualho!=0)//괄호의 짝이 맞지 않으면 오류.
		{
			error_eqs(0);
		}	
		
		else
		{
			while(!empty(OPERATOR))//operator스택이 비지 않을때까지
			{
				strcpy(top_operator,pop_operator());//operator를 뽑아 낸다.
				strcat(output,top_operator);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
				process();//연산수행
			}
		}

	}	

	else if(sign==1)//음수일경우에는
	{
		push(token,OPERAND);//음수를 스택에 저장
	}
	
	else if('('==token[0])//'('가 오면 스택에 저장,괄호의 짝이 잘 이루어 졌나 확인하기 괄호의 카운트를 증가
	{
		strcat(output,token);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
		push(token,OPERATOR);//operator스택에 저장
		pairs_Gualho++;//괄호의 갯수 1증가
	}

	else if(is_operand(token[0]))//operand가 들어 올 경우
	{
		push(token,OPERAND);//operand를 스택에 저장한다.
		strcat(output,token);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
	}
	
	else if(is_operator(token))//operator의경우
	{
		
		if((empty(OPERATOR))||(empty(OPERAND)))//operator 스택이 비어있으면,제일 처음 오는 연산자 이므로 저장한다.
		{
			push(token,OPERATOR);//operator 스택에 삽입			
		}
		
		else
		{
			strcpy(top_operator,pop_operator());//operator 하나 뽑아 낸다.			
			if((token[0]!=')')&&(top_operator[0]=='('))	//토큰이 ')'가 아니고,operator이 '(' 일때는	
			{
				push(top_operator,OPERATOR);//operator을 푸시
				push(token,OPERATOR);//토큰을 푸시
			}			
			
			else if('^'==token[0])//'^'연산자일경우(연산 방향이 다름)
			{
				if(((compare_operator(top_operator,token))==2)||((compare_operator(top_operator,token))==1))
					//'^"의 우선순위가 같거나 높을때
				{
					push(top_operator,OPERATOR);
					push(token,OPERATOR);
				}
				
				else if((compare_operator(top_operator,token))==0)//토큰 우선순위가 낮을때
				{
					while((compare_operator(top_operator,token))==0)//토큰과 operator의 우선순위가 같을때까지만
					{						
						if(top_operator[0]=='(')//'('이 top_operator 일경우에는
						{
							break;//루프 종료
						}
							
						strcat(output,top_operator);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
						process();//연산 수행
						
						if(!empty(OPERATOR))//operator 스택이 비지 않았앗다면
						{
							strcpy(top_operator,pop_operator());//연산자 하나를 또 뽑아낸다
						}
						else
						{
							break;//루프 종료
						}
					}					
					push(top_operator,OPERATOR);//뽑아 내었던 연산자를 다시 푸시하고.
					push(token,OPERATOR);//토큰도 푸시한다.
				}					
				
			}

			else if(')'==token[0])//')'일경우
			{
				pairs_Gualho--;	//괄호의 갯수를 하나 줄인다.짝이 하나 들어 왔으므로
				
			
				while(!(top_operator[0]=='('))//'('를 만날때까지
				{
					if((top_operator[0]=='!')&&(top_operator[1]==0))//!연산자 일경우 !연산 수행
					{
						strcat(output,top_operator);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
						process();//연산 수행
						push(token,OPERATOR);//토큰을 푸시한다
					}//아니면 그냥 무시하고 지나감.					
					
					else
					{
						strcat(output,top_operator);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
						process();//연산 수행					
					}
					
					strcpy(top_operator,pop_operator());//연산자 하나를 뽑아 낸다			
				}
				strcat(output,token);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
				
			}
			
			else//위에서 정의 된 특별한 경우가 아닐경우에는
			{
				if(((compare_operator(top_operator,token))==0)||((compare_operator(top_operator,token))==2))
					//우선순위가 isp가 높거나, 같을때
				{   
					while((!empty(OPERAND))&&(compare_operator(top_operator,token))!=1)
						//operand가 있고,토큰의 우선순위가 낮지 않을때까지
					{	
						strcat(output,top_operator);//output에 저장한다.최종 변환된 연산 식을 만들기 위해서
						if((compare_operator(top_operator,token))==1)//우선순위가 icp가 높을때(루프문이므로)
						{
							push(top_operator,OPERATOR);//연산자를 다시 푸시							
							break;
						}

						process();//연산 수행
						
						if(empty(OPERATOR))//연산자가 없으면 루프 종료
						{							
							break;
						}
						else 
						{	
							strcpy(top_operator,pop_operator());//연산자를 하나 뽑아 낸다
							if(top_operator[0]=='(')//연산자가 '('인 경우에는
							{
								push(top_operator,OPERATOR);//다시 넣고 루프 종료								
								break;
							}
							
						}						
					}				
					push(token,OPERATOR);//토큰 삽입
				}
				else if((compare_operator(top_operator,token))==1)//우선순위가 icp(토큰)가 높을때
				{
					push(top_operator,OPERATOR);//뽑아내었던 연산자를 넣고
					push(token,OPERATOR);//토큰도 넣는다
				}
				
			}
			
		}
		
	}
	
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//is_next_correct_operator()정의
//리턴값 : 1: 올바름
//         0:올바르지 않음
int is_next_correct_operator(char next_token,char next_token_2)
{
	int j=0;
	while(j!=(sizeof(can_be_after_operator)/sizeof(can_be_after_operator[0])))
		//operand 다음에 올수없는 operator갯수만큼 루프
	{
		if((next_token=='!')&&(next_token_2=='='))//operand 다음에 "!="연산자는 올수 있으므로
			return 1;		
		else if(next_token==can_be_after_operator[j])//operand 다름에 올수 없는 operator일경우는 오류
			return 0;
		j++;
    }
	
	return 1;



}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//compare_operator()정의
//리턴값 : 0:isp우선순쉬가 높다.
//         1:isp 우선순위가 낮다.
//         2:isp 우선순위와 icp우선순위가 같다.
//         3:오류
int compare_operator(char *isp,char *icp)
{
	int result=0;
	int i=0;
	int pri_isp=0,pri_icp=0;
	
	if((isp[0]==icp[0])&&(isp[1]==icp[1]))//같은 연산자일경우(모든 연산자가 고유의 우선순위를 가지고 있다.)
		return 2;
	else
	{
		while((operator_priority_table[i][0])!='@')//연산자 우선순위 테이블을 참조해서 두 연산자의 우선순위 를 정함
		{
			if(isp[0]==operator_priority_table[i][0])
			{
				if(isp[1]==operator_priority_table[i][1])
				{
					pri_isp=i;
				}
			}
			else if(icp[0]==operator_priority_table[i][0])
			{
				if(icp[1]==operator_priority_table[i][1])
				{
					pri_icp=i;
				}
			}
			i++;
			
		}
	}
	//숫자가 작은것이 우선 순위가 높다.
	if(pri_isp<pri_icp)
		result=0;
	else if(pri_isp>pri_icp)
		result=1;
	else
	{
		result=3;
		error_eqs(1);
	}

	return result;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//correct_operator()정의
//리턴값 : 없음
//플래그 사용으로 올바른 연산자이면 오류 없음,그렇지 않으면 에러 메세지 출력후 종료

void correct_operator(char oper,char next_token)
{
	int j=0,flag=0;
	if((oper=='(')&&(next_token=='-'))//다음에 오는 연산자를 비교하기 위해서
		flag=1;

	else 
	{
		while(j!=(sizeof(can_be_after_operator)/sizeof(can_be_after_operator[0])))
			//operator 다음에 올수있는 operator갯수만큼 루프
		{
			if(next_token==can_be_after_operator[j])//operator 다름에 올수 있는 operator일경우는 오류없음
			{
				flag=1;
			}

			else if(is_operand(next_token))//operand일경우도 오류 없음
			{
				flag=1;
			}			
			j++;
		}
	}
	error_eqs(flag);

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//is_operator()정의
//리턴값 : 0:연산자 아님
//         1:연산자
int is_operator(char token[])
{
	int i=0;
	while((operator_priority_table[i][0])!='@') //operator배열에서 끝까지
	{
		if((token[0]==operator_priority_table[i][0])||token[0])
		{
			return 1;
		}
		i++;
	}
	return 0;
		

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//is_operand()정의
//리턴값 : 0:operand 아님
//         1:operand
int is_operand(char token)
{
	if((token<='9')&&(token>='0'))
		return 1;
	else
		return 0;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//error_eqs()정의
//에러메세지 출력후 종료
void error_eqs(int flag)
{
	if(!flag)//플래그가 0이면 에러
	{
    	 printf("\n잘못된 표현식입니다.");
	     exit(0);
	}
}
	

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//empty()정의
//리턴값 : 0:비었음
//         1:안비었음
int empty(int stack)//stack값에 따라 operand스택인지,operator 스택인지 구분
{
	if((stack==OPERATOR)&&(top_of_operator_stack==(-1)))
		return 1;
    else if((stack==OPERAND)&&(top_of_operand_stack==(-1)))
		return 1;
	else return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//full()정의
//리턴값 : 0:가득참
//         1:가득차지 않음

int full(int stack)//stack값에 따라 operand스택인지,operator 스택인지 구분
{
	if((stack==OPERATOR)&&(top_of_operator_stack==(MAX_EQS_SIZE)))
		return 1;
    else if((stack==OPERAND)&&(top_of_operand_stack==(MAX_EQS_SIZE)))
		return 1;
	else return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//pop_operand()정의
//리턴값 : top_operand

int pop_operand()
{
    int i=0;
	if(!empty(OPERAND))
	{
		i=operand_stack[top_of_operand_stack];
		top_of_operand_stack--;
	    return	i;
	}
    else
	{
		printf("\n operand 스택이 비었습니다.");
		exit(0);
		return -1;
	}
	
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//pop_operator()정의
//리턴값 : top_operator 
char *pop_operator()
{
	char *top=(char *)malloc(3*sizeof(char));
	if(!empty(OPERATOR))
	{
		strcpy(top,operator_stack[top_of_operator_stack]);
	    top_of_operator_stack--;
		return top;
	}
	else
	{
		printf("\n operator 스택이 비었습니다.");
		exit(0);
		return "ept";
	}


}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//push()정의
//스택의 타입에 따라 푸시 실행

void push(char *token,int type)
{
	if(type==OPERAND)//operand일경우에는
		{
			
			if(!full(OPERAND))//operand스택이 가득차지 않았으면 
			{
				int operand=0;
				operand=atoi(token);//토큰을 정수형 operand로 바꾸고 
				top_of_operand_stack++;//operand스택의 top을 중가 시켜줌
				operand_stack[top_of_operand_stack]=operand;//스택에 저장
				
			}
			else 
			{
				printf("\n operand 스택이 가득 찾습니다.");
				exit(0);
			}
		}
	if(type==OPERATOR)//operator일 경우에는
		{
			if(!full(OPERATOR))//operator스택이 가득차지 않았으면
			{
				top_of_operator_stack++;//operator스택의 top을 증가시켜줌
				strcpy(operator_stack[top_of_operator_stack],token);//스택에 저장
			}
			else 
			{
				printf("\n operator 스택이 가득 찾습니다.");
				exit(0);
			}
		}

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//print_status()정의
//각 스탭의 상태 출력
void print_status(int j)
{
	int i=0,temp=0;
	if(output_flag==0)//마지막 단계가 아니라면 지금 스텝의 각 스택의 상태를 출력 
	{
		temp=top_of_operand_stack;//임시 변수에 top을 저장한다
		printf("\n   : operand  stack: ",j+1);
		while(temp!=(-1))//스택의 모두를 읽어 들여서 출력(top의 값의 변화를 주지 않기 위해 임시 변수 사용
		{
			printf("  %d",operand_stack[i]);
			temp--;
			i++;
		}
		
		printf("\n");
		
		temp=top_of_operator_stack;//임시 변수에 top을 저장한다
		i=0;		
		printf("   : operator stack: ");
		while(temp!=(-1))//스택의 모두를 읽어 들여서 출력(top의 값의 변화를 주지 않기 위해 임시 변수 사용
		{
			printf("  %s",operator_stack[i]);
			temp--;
			i++;
		}
	}
	else//마지막 단계일때는 출력 형식을 바꿔야 되기때문에
	{
		printf("\n   : RESULT: ");
		printf("  %d\n",operand_stack[i]);//결과값 출력				
		printf("   : OUTPUT: ");
		printf("  %s\n",output);//변환된 수식출력
			
	}
}
// 소스 코드 끝
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

'코딩하고 > C,C++' 카테고리의 다른 글

cocosdx 사용해서 게임 개발하기 -1-  (0) 2012.11.19
OS - Page Fault Simulation(FIFO,LRU,Optimal)  (0) 2012.10.21
C언어로 만든 객체  (0) 2012.10.11
자료구조 - 다항식 연산하기  (2) 2012.10.10
ls 명령어 구현하기.  (2) 2012.10.09
블로그 이미지

커뉴

이 세상에서 꿈 이상으로 확실한 것을, 인간은 가지고 있는 것일까?

,