stack을 익히기 위하여 미니 프로젝트로 계산기를 구현해 보았습니다.
중위 표기식의 입력을 후위 표기로 변환, 계산 합니다.
삼각함수 연산도 가능합니다.
/*=====================================================================*/
/* ☆★ 미니 프로젝트 : calculator. ☆★ */
/* 목적 : 중위 표기식을 후위 표기식으로 변환해서 계산. */
/* 기능 :-삼각함수 연산 가능.
ex)-10*-cos(--sin(--45--45)/2-sin(40))
-10 -1 45 45 + sin 2 / 40 sin - cos * * =10.0
radian = (PI*first)/180;
/* -에러처리 가능.
ex)-10*-(-9.1(--0.8--0.1))
=error
/*=====================================================================*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<math.h>
#define MAX_STACK_SIZE 100 //스택 최대 크기.
#define MAX_EXPR_SIZE 100 //수식의 최대 크기.
#define PI 3.14159 //파이 3.14159
typedef enum {lparen, rparen, plus, minus, times, divide, mod, s, c, t, eos, operand} precedence;
// ( ) + - * / % s c t 0 default
// 0 1 2 3 4 5 6 7 8 9 10 11
int stack[MAX_STACK_SIZE]; //전역 배열.
char expr[MAX_EXPR_SIZE]; //입력 문자열.
char bexpr[MAX_EXPR_SIZE]; //후위 표기법으로 저장되는 배열.
double result[MAX_STACK_SIZE]; //연산해주는 스택.
int cnt=0;
precedence stack[MAX_STACK_SIZE]; //연산자가 푸쉬&팝 되는 스택.
static int isp[] = {0, 19, 12, 12, 13, 13, 13, 14, 14, 14, 0}; //in-stack precredence.
// 0 1 2 3 4 5 6 7 8 9 10
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 14, 14, 14, 0}; //incoming precedence.
/*********** 함수 ************/
void postfix(void); // 중위 표기법을 후위 표기법으로 바꿔주는 함수.
void push(int* top,precedence token); // 스택에 입력하는 함수.
int pop(int* top); // 스택에서 출력 함수.
precedence get_token(char* symbol , int* n); // precedence type으로 바꿔주는 함수.
void print_token(int opt); // precedence를 기호로 바꾸어 출력.
double Opop(int* top); // 연산해줄 탑 출력하는 함수. (main에서 계산시 사용.)
void Opush(int* top,double i); // 탑에 연산해줄 값을 입력하는 함수. (main에서 계산시 사용.)
double operation(int* top,char i); // 두수를 팝하여 연산해주는 계산기. (main에서 계산시 사용.)
/*****************************************************************/
/* 메인 함수. */
/*****************************************************************/
int main(void){
char bag[MAX_STACK_SIZE]; // bexpr에서 더블형으로 바꿔 result[]에 옮겨주는 배열.
char* bp=bexpr; // bag에 넣을 입력 문자열의 포인터.
int top = -1; // top 다음에 수가 저장.
int n = 0; // for문의 카운터. 인덱스.
int i = 0; // bag의 카운터.
double sol; // 팝된 값들의 연산후 저장될 변수. 푸쉬됨.
printf("중위 표기법으로 입력하시오.\n중위표기법 =>\t");
scanf("%s",expr);
printf("후위표기법 => \t");
postfix();
for(; n<(int)strlen(bexpr); n++,*bp++)
{
if((bexpr[n]=='-' && isdigit(bexpr[n+1])!=0)||(isdigit(bexpr[n]) != 0))
{
i=0;
while(bexpr[n] !=' '){ // *bp 즉 bexpr[n]의 값이 띄어쓰기가 나오기 전까지 bag에 입력.
bag[i++]=*(bp++);
n++;
}
bag[i]='\0';
Opush(&top,atof(bag)); //result스택의 top에 bag숫자열을 float형으로 변환하여 넣어줌.
}
else if(isdigit(bexpr[n])==0 && bexpr[n]!=' ') // 연산자가 나오면!
{
sol = operation(&top,bexpr[n]); // 두 수를 팝하여 연산하고 그 리턴형을 sol에 저장.
Opush(&top, sol); // sol을 푸쉬!.
}
// printf("\nbag= %s\n",bag);
// printf("result= %f\n",result[top]);
}
printf("\n결과는 => \t%lf \n",Opop(&top)); //마지막 탑. 즉, 결과를 출력.
return 0;
}
/****************************************************************/
/* (계산기)두수를 팝하여 연산해주는 계산기 함수. */
/* operation */
/****************************************************************/
double operation(int* top,char i)
{
double first,second,radian;
if(i=='s') //sin
{
first=Opop(top);
radian=(PI*first)/180;
return sin(radian);
}
else if(i=='c') //cos
{
first=Opop(top);
radian=(PI*first)/180;
return cos(radian);
}
else if(i=='t') //tan
{
first=Opop(top);
radian=(PI*first)/180;
return tan(radian);
}
else //연산자
{
second=Opop(top);
first=Opop(top);
switch(i) {
case '+' : return (first+second);
case '-' : return (first-second);
case '/' : return (first/second);
case '*' : return (first*second);
case '%' : return (first*second);
default : return 0 ;
}
}
}
/****************************************************************/
/* (계산기) 탑에 연산해줄 값을 입력하는 함수. */
/* Opush */
/****************************************************************/
void Opush(int* top,double i)
{
result[++(*top)] = i;
}
/****************************************************************/
/* (계산기) 연산해줄 탑을 출력해주는 Operation_pop함수. */
/* Opop */
/****************************************************************/
double Opop(int* top)
{
double temp = result[*top];
(*top)--;
return temp;
}
/****************************************************************/
/* 중위표기법을 후위표기법으로 바꿔주는 함수. */
/* - 수식 문자열, 스택, top은 전역적 */
/* postfix */
/****************************************************************/
void postfix(void)
{
char symbol;
precedence token; // 인덱스다. 결국은 정수.
int n = 0; //스택 인덱스.
int top = 0; //top의 초기값. (최초의 연산자와 비교해줄 eos의 인덱스)
int mcnt = 1; // '-'의 갯수를 측정하는 카운트.
int on = 0; // n의 상수값.
char tri ; // 삼각 함수 한글자를 저장할 값.
stack[0] = eos; //최초의 연산자와 비교해줄 최초의 top.(eos)
for(token = get_token(&symbol, &n); token != eos; token = get_token(&symbol, &n)) //token이 eos를 가리킬때까지 get_token.
{
/* 1. token이 마이너스 일때. */
if(token == minus)
{
on = n; //n의 최초 값.
for(; expr[n] == '-'; n++) //mcnt 카운트로 '-'갯수 측정. n의 값이 증가하는것에 유의.
mcnt++;
/* "-(" 가 나온 경우① "-1*("로 바꿔주는 문. "-(" 앞이 숫자가 아닐경우. */
if(expr[n] == '('&& expr[n-2] != '-' && isdigit(expr[n-2]) ==0){
//expr[n-4] = '(';
expr[n-3] = '-';
expr[n-2] = '1';
expr[n-1] = '*';
n-=3;
}
/* "-(" 가 나온 경우② "-(" 앞이 숫자일 경우. '+'연산자가 필요하게 됨. */
else if(expr[n] == '('&& expr[n-2] != '-' && isdigit(expr[n-2]) !=0){
expr[n-4] = '+';
expr[n-3] = '-';
expr[n-2] = '1';
expr[n-1] = '*';
n-=4;
}
/* 삼각함수가 나온 경우①. 위의 괄호의 경우처럼 둘로 나누어 연산.*/
else if((expr[n] == 's'||expr[n] == 'c'||expr[n] == 't')&& expr[n-2] != '-' && isdigit(expr[n-2]) ==0){
tri=expr[n];
// expr[n-2] = '(';
expr[n-1] = '-';
expr[n] = '1';
expr[n+1] = '*';
expr[n+2] = tri;
n--;
}
/* 삼각함수가 나온 경우②.*/
else if((expr[n] == 's'||expr[n] == 'c'||expr[n] == 't')&& expr[n-2] != '-' && isdigit(expr[n-2]) !=0){
tri=expr[n];
expr[n-2] = '+';
expr[n-1] = '-';
expr[n] = '1';
expr[n+1] = '*';
expr[n+2] = tri;
n-=2;
}
/* '-'의 앞이 괄호나 숫자가 아니고 뒤에 숫자가 나왔을때 음수기호로 만들어주는 경우.*/
else if((isdigit(expr[on-2]) ==0) && (mcnt%2==1) && expr[on-2] !=')' ){
printf("-");
bexpr[cnt++]='-';
}
else if(mcnt%2==0){ // '-'가 짝수개.
if(isdigit(expr[on-2])==0) // --앞에 숫자 아니면..없어져라..
;
else{
token = plus;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
}
else if(mcnt%2==1){ // '-'가 홀수개. mcnt != 1
token = minus;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
mcnt=1;
//printf("%s\n",expr);
}
else if(token == s || token == c || token == t){
//tri=token;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
while(expr[n]!='(')
n++;
}
/* 2. token이 숫자 일때. */
else if(token == operand)
{
printf("%c",symbol);
bexpr[cnt++]=symbol;
while(get_token (&symbol, &n) == operand){
if(expr[n] == '('){
printf("????? -_-\n\nERROR : 연산자를 미입력 하셨습니다.\n\n");
return;
}
printf("%c",symbol);
bexpr[cnt++]=symbol;
}
printf(" ");
bexpr[cnt++]=' ';
n--;
}
/* 3. token에 괄호(')')가 들어간다면... */
else if(token == rparen)
{
while(stack[top] != lparen)
print_token(pop(&top));
pop(&top); //좌 괄호를 버린다.
}
/* 4. token이 연산자 일때. */
else //symbol의 isp가 token의 icp보다 크거나 같으면 symbol을 제거하고 출력 시킴.
{
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
}
/* 결과물 출력. */
while((token = pop(&top)) != eos)
print_token (token);
}
/****************************************************************/
/* push함수 */
/* - 스택에 push 해주는 함수. */
/****************************************************************/
void push(int* top,precedence token){
stack[++(*top)] = token;
}
/****************************************************************/
/* pop함수 */
/****************************************************************/
int pop(int* top){
int temp =stack[*top];
(*top)--;
return temp;
}
/****************************************************************/
/* get_token */
/* 입력 문자열로부터 토큰을 얻기위한 함수. */
/* - 토큰이 연산자이면 명칭으로 반환.(return) */
/* - symbol은 expr의 n++번째 요소 를 보고 인식. */
/* - call by reference. */
/****************************************************************/
precedence get_token(char* symbol , int* n)
{
*symbol = expr[(*n)++]; //symbol은 문자표현.
switch (*symbol){
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
case 's' : return s;
case 'c' : return c;
case 't' : return t;
case '\0' : return eos;
default : return operand; //오류 검사는 하지 않고 기본값은 피연산자.
}
}
/****************************************************************/
/* precedence상태인 토큰을 연산자로 바꾸어 출력해주는 함수. */
/* print_token */
/****************************************************************/
void print_token(int opt)
{
// char* copt = opt;
// switch (*copt){
char copt;
switch (opt){
case plus : copt = '+' ;
break;
case minus : copt = '-' ;
break;
case divide : copt = '/' ;
break;
case times : copt = '*' ;
break;
case mod : copt = '%' ;
break;
case s : copt = 's' ;
break;
case c : copt = 'c' ;
break;
case t : copt = 't' ;
break;
default : return ;
}
bexpr[cnt++]=copt;
bexpr[cnt++]=' ';
printf("%c ",copt);
}
/*=====================================================================*/
/* ☆★ 미니 프로젝트 : calculator. ☆★ */
/* 목적 : 중위 표기식을 후위 표기식으로 변환해서 계산. */
/* 기능 :-삼각함수 연산 가능.
ex)-10*-cos(--sin(--45--45)/2-sin(40))
-10 -1 45 45 + sin 2 / 40 sin - cos * * =10.0
radian = (PI*first)/180;
/* -에러처리 가능.
ex)-10*-(-9.1(--0.8--0.1))
=error
/*=====================================================================*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<math.h>
#define MAX_STACK_SIZE 100 //스택 최대 크기.
#define MAX_EXPR_SIZE 100 //수식의 최대 크기.
#define PI 3.14159 //파이 3.14159
typedef enum {lparen, rparen, plus, minus, times, divide, mod, s, c, t, eos, operand} precedence;
// ( ) + - * / % s c t 0 default
// 0 1 2 3 4 5 6 7 8 9 10 11
int stack[MAX_STACK_SIZE]; //전역 배열.
char expr[MAX_EXPR_SIZE]; //입력 문자열.
char bexpr[MAX_EXPR_SIZE]; //후위 표기법으로 저장되는 배열.
double result[MAX_STACK_SIZE]; //연산해주는 스택.
int cnt=0;
precedence stack[MAX_STACK_SIZE]; //연산자가 푸쉬&팝 되는 스택.
static int isp[] = {0, 19, 12, 12, 13, 13, 13, 14, 14, 14, 0}; //in-stack precredence.
// 0 1 2 3 4 5 6 7 8 9 10
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 14, 14, 14, 0}; //incoming precedence.
/*********** 함수 ************/
void postfix(void); // 중위 표기법을 후위 표기법으로 바꿔주는 함수.
void push(int* top,precedence token); // 스택에 입력하는 함수.
int pop(int* top); // 스택에서 출력 함수.
precedence get_token(char* symbol , int* n); // precedence type으로 바꿔주는 함수.
void print_token(int opt); // precedence를 기호로 바꾸어 출력.
double Opop(int* top); // 연산해줄 탑 출력하는 함수. (main에서 계산시 사용.)
void Opush(int* top,double i); // 탑에 연산해줄 값을 입력하는 함수. (main에서 계산시 사용.)
double operation(int* top,char i); // 두수를 팝하여 연산해주는 계산기. (main에서 계산시 사용.)
/*****************************************************************/
/* 메인 함수. */
/*****************************************************************/
int main(void){
char bag[MAX_STACK_SIZE]; // bexpr에서 더블형으로 바꿔 result[]에 옮겨주는 배열.
char* bp=bexpr; // bag에 넣을 입력 문자열의 포인터.
int top = -1; // top 다음에 수가 저장.
int n = 0; // for문의 카운터. 인덱스.
int i = 0; // bag의 카운터.
double sol; // 팝된 값들의 연산후 저장될 변수. 푸쉬됨.
printf("중위 표기법으로 입력하시오.\n중위표기법 =>\t");
scanf("%s",expr);
printf("후위표기법 => \t");
postfix();
for(; n<(int)strlen(bexpr); n++,*bp++)
{
if((bexpr[n]=='-' && isdigit(bexpr[n+1])!=0)||(isdigit(bexpr[n]) != 0))
{
i=0;
while(bexpr[n] !=' '){ // *bp 즉 bexpr[n]의 값이 띄어쓰기가 나오기 전까지 bag에 입력.
bag[i++]=*(bp++);
n++;
}
bag[i]='\0';
Opush(&top,atof(bag)); //result스택의 top에 bag숫자열을 float형으로 변환하여 넣어줌.
}
else if(isdigit(bexpr[n])==0 && bexpr[n]!=' ') // 연산자가 나오면!
{
sol = operation(&top,bexpr[n]); // 두 수를 팝하여 연산하고 그 리턴형을 sol에 저장.
Opush(&top, sol); // sol을 푸쉬!.
}
// printf("\nbag= %s\n",bag);
// printf("result= %f\n",result[top]);
}
printf("\n결과는 => \t%lf \n",Opop(&top)); //마지막 탑. 즉, 결과를 출력.
return 0;
}
/****************************************************************/
/* (계산기)두수를 팝하여 연산해주는 계산기 함수. */
/* operation */
/****************************************************************/
double operation(int* top,char i)
{
double first,second,radian;
if(i=='s') //sin
{
first=Opop(top);
radian=(PI*first)/180;
return sin(radian);
}
else if(i=='c') //cos
{
first=Opop(top);
radian=(PI*first)/180;
return cos(radian);
}
else if(i=='t') //tan
{
first=Opop(top);
radian=(PI*first)/180;
return tan(radian);
}
else //연산자
{
second=Opop(top);
first=Opop(top);
switch(i) {
case '+' : return (first+second);
case '-' : return (first-second);
case '/' : return (first/second);
case '*' : return (first*second);
case '%' : return (first*second);
default : return 0 ;
}
}
}
/****************************************************************/
/* (계산기) 탑에 연산해줄 값을 입력하는 함수. */
/* Opush */
/****************************************************************/
void Opush(int* top,double i)
{
result[++(*top)] = i;
}
/****************************************************************/
/* (계산기) 연산해줄 탑을 출력해주는 Operation_pop함수. */
/* Opop */
/****************************************************************/
double Opop(int* top)
{
double temp = result[*top];
(*top)--;
return temp;
}
/****************************************************************/
/* 중위표기법을 후위표기법으로 바꿔주는 함수. */
/* - 수식 문자열, 스택, top은 전역적 */
/* postfix */
/****************************************************************/
void postfix(void)
{
char symbol;
precedence token; // 인덱스다. 결국은 정수.
int n = 0; //스택 인덱스.
int top = 0; //top의 초기값. (최초의 연산자와 비교해줄 eos의 인덱스)
int mcnt = 1; // '-'의 갯수를 측정하는 카운트.
int on = 0; // n의 상수값.
char tri ; // 삼각 함수 한글자를 저장할 값.
stack[0] = eos; //최초의 연산자와 비교해줄 최초의 top.(eos)
for(token = get_token(&symbol, &n); token != eos; token = get_token(&symbol, &n)) //token이 eos를 가리킬때까지 get_token.
{
/* 1. token이 마이너스 일때. */
if(token == minus)
{
on = n; //n의 최초 값.
for(; expr[n] == '-'; n++) //mcnt 카운트로 '-'갯수 측정. n의 값이 증가하는것에 유의.
mcnt++;
/* "-(" 가 나온 경우① "-1*("로 바꿔주는 문. "-(" 앞이 숫자가 아닐경우. */
if(expr[n] == '('&& expr[n-2] != '-' && isdigit(expr[n-2]) ==0){
//expr[n-4] = '(';
expr[n-3] = '-';
expr[n-2] = '1';
expr[n-1] = '*';
n-=3;
}
/* "-(" 가 나온 경우② "-(" 앞이 숫자일 경우. '+'연산자가 필요하게 됨. */
else if(expr[n] == '('&& expr[n-2] != '-' && isdigit(expr[n-2]) !=0){
expr[n-4] = '+';
expr[n-3] = '-';
expr[n-2] = '1';
expr[n-1] = '*';
n-=4;
}
/* 삼각함수가 나온 경우①. 위의 괄호의 경우처럼 둘로 나누어 연산.*/
else if((expr[n] == 's'||expr[n] == 'c'||expr[n] == 't')&& expr[n-2] != '-' && isdigit(expr[n-2]) ==0){
tri=expr[n];
// expr[n-2] = '(';
expr[n-1] = '-';
expr[n] = '1';
expr[n+1] = '*';
expr[n+2] = tri;
n--;
}
/* 삼각함수가 나온 경우②.*/
else if((expr[n] == 's'||expr[n] == 'c'||expr[n] == 't')&& expr[n-2] != '-' && isdigit(expr[n-2]) !=0){
tri=expr[n];
expr[n-2] = '+';
expr[n-1] = '-';
expr[n] = '1';
expr[n+1] = '*';
expr[n+2] = tri;
n-=2;
}
/* '-'의 앞이 괄호나 숫자가 아니고 뒤에 숫자가 나왔을때 음수기호로 만들어주는 경우.*/
else if((isdigit(expr[on-2]) ==0) && (mcnt%2==1) && expr[on-2] !=')' ){
printf("-");
bexpr[cnt++]='-';
}
else if(mcnt%2==0){ // '-'가 짝수개.
if(isdigit(expr[on-2])==0) // --앞에 숫자 아니면..없어져라..
;
else{
token = plus;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
}
else if(mcnt%2==1){ // '-'가 홀수개. mcnt != 1
token = minus;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
mcnt=1;
//printf("%s\n",expr);
}
else if(token == s || token == c || token == t){
//tri=token;
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
while(expr[n]!='(')
n++;
}
/* 2. token이 숫자 일때. */
else if(token == operand)
{
printf("%c",symbol);
bexpr[cnt++]=symbol;
while(get_token (&symbol, &n) == operand){
if(expr[n] == '('){
printf("????? -_-\n\nERROR : 연산자를 미입력 하셨습니다.\n\n");
return;
}
printf("%c",symbol);
bexpr[cnt++]=symbol;
}
printf(" ");
bexpr[cnt++]=' ';
n--;
}
/* 3. token에 괄호(')')가 들어간다면... */
else if(token == rparen)
{
while(stack[top] != lparen)
print_token(pop(&top));
pop(&top); //좌 괄호를 버린다.
}
/* 4. token이 연산자 일때. */
else //symbol의 isp가 token의 icp보다 크거나 같으면 symbol을 제거하고 출력 시킴.
{
while(isp[stack[top]] >= icp[token])
print_token(pop(&top));
push(&top, token);
}
}
/* 결과물 출력. */
while((token = pop(&top)) != eos)
print_token (token);
}
/****************************************************************/
/* push함수 */
/* - 스택에 push 해주는 함수. */
/****************************************************************/
void push(int* top,precedence token){
stack[++(*top)] = token;
}
/****************************************************************/
/* pop함수 */
/****************************************************************/
int pop(int* top){
int temp =stack[*top];
(*top)--;
return temp;
}
/****************************************************************/
/* get_token */
/* 입력 문자열로부터 토큰을 얻기위한 함수. */
/* - 토큰이 연산자이면 명칭으로 반환.(return) */
/* - symbol은 expr의 n++번째 요소 를 보고 인식. */
/* - call by reference. */
/****************************************************************/
precedence get_token(char* symbol , int* n)
{
*symbol = expr[(*n)++]; //symbol은 문자표현.
switch (*symbol){
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
case 's' : return s;
case 'c' : return c;
case 't' : return t;
case '\0' : return eos;
default : return operand; //오류 검사는 하지 않고 기본값은 피연산자.
}
}
/****************************************************************/
/* precedence상태인 토큰을 연산자로 바꾸어 출력해주는 함수. */
/* print_token */
/****************************************************************/
void print_token(int opt)
{
// char* copt = opt;
// switch (*copt){
char copt;
switch (opt){
case plus : copt = '+' ;
break;
case minus : copt = '-' ;
break;
case divide : copt = '/' ;
break;
case times : copt = '*' ;
break;
case mod : copt = '%' ;
break;
case s : copt = 's' ;
break;
case c : copt = 'c' ;
break;
case t : copt = 't' ;
break;
default : return ;
}
bexpr[cnt++]=copt;
bexpr[cnt++]=' ';
printf("%c ",copt);
}
이 글은 스프링노트에서 작성되었습니다.
'Programming Language > C' 카테고리의 다른 글
| C Tutorial (L_list 역순출력) (0) | 2010.10.14 |
|---|---|
| C Tutorial (트리 문자 읽기) (0) | 2010.10.14 |
| C Tutorial (strcmp+numcmp) (0) | 2010.10.14 |
| C Tutorial ([C.L.A]. 문자열중간읽기) (0) | 2010.10.14 |
| C Tutorial (역순화 문자열) (0) | 2010.10.14 |
