중위 표기법 -> 후위표기법으로 변경후 계산

// calc.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
/*****************************************************************************
*                                                                         *
* 프로젝트 : _CALC4Console                                                 *
*                                                                         *
* 제목 : 계산기                                                             *
* 설명 : 스택을 이용한 중위표기를 후위표기로 바꾼 후의 연산                 *
* 동작환경 : 콘솔(WINDOWS/LINUX)                                            *
*                                                                         *
* 컴파일러 : GCC 3.3.3 (Debian Kernel 2.4.23 #3)                            *
*                                                                         *
* 개발날짜 : 2004/03/14 (일단은 되게끔 만듬)                                *
*                                                                         *
*****************************************************************************/

#include <stdio.h> // 리눅스는 이 하나만 있어도 됩니다.
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define MAX 512
#define RES_SIZE 16

double calc( char *exp, int *calc_ok ); // 후위표기법 계산
int preproc( char *dest, char *src); // 중위표기법을 후위표기법으로..

void init_stack( void );
double pop( void );
double push( double d );

double atolf( const char *nptr); // 문자열을 double 형으로
int is_digit( char c );
int is_operator( char c );

double store_res( double *res_list, double res, int *pos ); // 결과값 저장
int is_intkey( char *key ); // 키입력
int confirm_key( char *key, char c); // 키확인
void proc_intkey( char *key, double *res_list, int *pos ); // 키입력 처리

/* STACK */
double stack[MAX];
int top;

int main(void)
{
char dest[MAX], src[MAX];
double res, res_list[RES_SIZE];
int calc_ok, pos;

memset( (double *)res_list, 0, sizeof(res_list) );
calc_ok = 0;
pos = 0;

printf( "====================== Calculator =====================\n" );
printf( "종료(Q) 이전결과(P)/결과목록출력(L)/결과목록지우기(E)\n" );
printf( "-------------------------------------------------------\n" );

while( TRUE )
{
printf("수식입력 : ");
fgets( src, MAX - 1, stdin );
src[ strlen( src ) - 1 ] = '\0';

if( is_intkey( src ) )
proc_intkey( src, res_list, &pos );

/* 중위표기법을 후위표기법으로 바꿈 */
if( !preproc( dest, src ) )
continue;

/* 후위표기법을 계산 */
res = calc( dest, &calc_ok );
if( !calc_ok )
continue;

printf( "결과값 : %lf\n\n", res );

/* 결과값 저장 */
store_res( res_list, res, &pos );
}

return 0;
}

/* 키입력을 받았는지 */
int is_intkey( char *key )
{
if( confirm_key( key, 'Q') )
return TRUE;

if( confirm_key( key, 'L') )
return TRUE;

if( confirm_key( key, 'P') )
return TRUE;

if( confirm_key( key, 'E') )
return TRUE;

return FALSE;
}

/* 키값 검사 */
int confirm_key( char *key, char c )
{
if( toupper( *key ) == c && *( key + 1 ) == '\0' )
return TRUE;

return FALSE;
}

/* 키값 처리 */
void proc_intkey( char *key, double *res_list, int *pos )
{
int i;

/* 종료 */
if( toupper(*key) == 'Q' )
{
printf( "종료합니다.\n" );
exit(0);
}

/* 전체결과목록 출력 */
if( toupper(*key) == 'L' )
{
if( *pos == 0 )
{
printf( "전체 결과 목록이 없습니다.\n\n" );
return;
}

printf( "전체결과목록 : \n" );

for( i = 0; i < *pos; i++ )
{
printf( "%lf ", res_list[i] );

if( !( ( i + 1 ) % 5 ) )
    fputc( '\n', stdout );
}

fputc( '\n', stdout );

return;
}

/* 바로 전 결과 출력 */
if( toupper(*key) == 'P' )
{
if(*pos == 0)
{
printf( "이전결과가 없습니다.\n\n" );

return;
}

printf( "이전결과 : %lf\n\n", res_list[*pos - 1] );

return;
}

/* 모든 결과 목록 초기화 */
if( toupper(*key) == 'E' )
{
printf("모든 결과 목록을 지웁니다.\n\n");
*pos = 0;

return;
}

return;
}

/* 결과값 저장 */
double store_res( double *res_list, double res, int *pos )
{
int i;
double tmp;

/* 꽉차면 한칸식 이전으로 이전 */
if( *pos >= RES_SIZE )
{
for( i = 1; i < *pos; i++ )
{
tmp = res_list[i];
res_list[i] = res_list[i - 1];
res_list[i - 1] = tmp;
}

(*pos)--;
}

res_list[(*pos)++] = res;

return res;
}

/* 스택 초기화 */
void init_stack( void )
{
top = -1;
}

/* 스택 POP */
double pop( void )
{
if( top < 0 )
{
perror("STACK underflow");
exit(1);
}

return stack[top--];
}

/* 스택 PUSH */
double push( double d )
{
if( top >= MAX )
{
perror("STACK overflow");
exit(1);
}

stack[++top] = d;

return d;
}

/* 문자열을 double 로 바꿔 준다 */
double atolf( const char *nptr )
{
int point, power;
int loop, sign;

double res;

res = 0.0;
point = 0;
sign = FALSE;

/* 음수인지 확인 */
if( *nptr == '-' )
sign = TRUE;

/* 정수부와 소수부 나눔 */
for( point = sign; nptr[point] != '.' && \
nptr[point] >= '0' && nptr[point] <= '9'; point++ );

/* 정수부 처리 */
for( loop = point - 1, power = 1; loop >= sign; loop--, power *= 10 )
{
if( sign )
res += (double)( ~(( nptr[loop] - '0' ) * power) + 1 );
else
res += (double)(( nptr[loop] - '0' ) * power);
}

/* 소수점이 없으면 반환 */
if( !nptr[point] )
return res;

/* 소수점 아래 처리 */
for( loop = point + 1, power = 10; \
nptr[loop] >= '0' && nptr[loop] <= '9'; \
loop++, power *= 10 )
{
if( sign )
res -= (double)(( nptr[loop] - '0' ) / (double)power );
else
res += (double)(( nptr[loop] - '0' ) / (double)power );
}

return res;
}

/* 중위표기법을 후위표기법으로 */
int preproc( char *dest, char *src )
{
char *start_pos;
int r_bracket;
int num_digit, num_oper;
int i;

/* 변수들 초기화 */
start_pos = src;
num_digit = 0;
num_oper = 0;
i = 0;
r_bracket = FALSE;

if( !*src )
return 0;

init_stack();

while( *src )
{
if( *src == '(' )
{
/* 괄호의 시작 표시 */
r_bracket = TRUE;

push( *src );
src++;
}

else if( *src == ')')
{
/* 괄호의 끝 표시 */
r_bracket = FALSE;

while( stack[top] != '(' )
{
    /* 123) 과 같은 입력값의 예외처리 */
    if( top < 0 )
     return 0;
    
    *dest++ = (char)pop();
    *dest++ = ' ';
}

pop();
src++;
}

/* 연산자 */
else if( is_operator( *src ) )
{
/* 연산자의 개수 증가*/
num_oper++;

/* 이전 문자의 위치 */
for( i = 1; *(src - i) == ' '; i++);

/* 숫자앞의 부호 처리( 1 + -2 같은..) */
if( is_operator( *src ) == 1 && !is_digit(*(src - i)) \
     || src == start_pos )
{
    *dest++ = *src++;
    num_oper--; // 연산자가 아니므로 다시 감소
}

else
{
    /* 연산자 우선 순위에 의한 pop */
    if( is_operator( *src ) <= is_operator( (char)stack[top] ) )
    {
     *dest++ = (char)pop();
     *dest++ = ' ';
    }
    
    push( *src );
    src++;
}
}

/* 실수일 경우 */
else if( *src >= '0' && *src <= '9' )
{
while( is_digit( *src ) || *src == '.' )
    *dest++ = *src++;

/* the end of number is space */
*dest++ = ' ';
num_digit++;
}

/* skip */
else if( *src == ' ' )
src++;

/* 다른 문자가 오면 실패 */
else
return 0;
}

/* 올바르게 괄호가 쓰였는지 확인 */
if(r_bracket)
return 0;

/* 실수의 개수와 연산자의 개수가 올바른지 확인 */
if(num_digit != num_oper + 1)
return 0;

/* flush STACK */
while( top > -1 )
{
*dest++ = (char)pop();
*dest++ = ' ';
}

/* make string */
*dest = '\0';

return 1;
}

/* 후위표시법의 계산 */
double calc( char *exp, int *calc_ok )
{
double res, operand;
char buf[MAX];
int i;

/* 계산이 올바르게 됐다고 초기화 */
*calc_ok = TRUE;

init_stack();

while( *exp )
{
/* sign 처리, 순서 중요함 '-' 처리 뒤로 가면 안됨 */
if( is_operator( *exp ) == 1 && is_digit( *( exp + 1 ) ) )
{
for( i = 0; *exp != ' '; i++ )
    buf[i] = *exp++;
buf[i] = '\0';
push( atolf( buf ) );
exp++;
}

else if( *exp == '*' )
{
push( pop() * pop() );
exp++;
}

else if( *exp == '/' )
{
operand = pop();
if(operand == 0)
{
    *calc_ok = FALSE;
    break;
}

push( pop() / operand );
exp++;
}

else if( *exp == '+' )
{
push( pop() + pop() );
exp++;
}

else if( *exp == '-' )
{
operand = pop();

push( pop() - operand );
exp++;
}

else if( is_digit( *exp ) )
{
/* 스페이스로 구분 */
for( i = 0; *exp != ' '; i++ )
    buf[i] = *exp++;
buf[i] = '\0';

/* 문자열을 실수로 */
push( atolf( buf ) );
exp++;
}

/* skip */
else if( *exp == ' ' )
exp++;

/* 다른 문자가 온 경우.. 99.9% 일어나지 않을 것이다.*/
else
{
*calc_ok = FALSE;
break;
}
}

/* 에러처리 부분 */
if( top != 0 )
*calc_ok = FALSE;

if( !*calc_ok )
return 0;

res = pop();

return res;
}

/* 연산자인지를 확인하면서 우선 순위까지 포함 */
int is_operator( char op )
{
switch( op )
{
case '+' :
return 1;

case '-' :
return 1;

case '*' :
return 2;

case '/' :
return 2;

default :
return 0;
}
}

/* 숫자인지 확인 */
int is_digit( char ch )
{
if( ch >= '0' && ch <= '9' )
return TRUE;

return FALSE;
}