|
#include <stdlib.h>
#include <malloc.h>
#include <ctype.h>
#include <stdio.h>
#define MAX_BUFSIZE 100
typedef struct _PLEAF pleaf;
typedef struct _PARSER parser;
struct _PLEAF
{
pleaf *lc;
pleaf *rc;
char *token;
};
struct _PARSER //파서 트리
{
size_t tcnt; //파서 트리에 토큰 수
pleaf *root; //파서 트리의 root
char **tokentable; //토큰 테이블
};
parser *ps; //파서 트리를 보관할 변수
char buf[MAX_BUFSIZE+1]; //수식을 보관할 입력 버퍼
int fnAdd(int a,int b)
{
return a+b;
}
int fnSub(int a,int b)
{
return a-b;
}
int fnMul(int a,int b)
{
return a*b;
}
int fnDiv(int a,int b)
{
if(b)
{
return a/b;
}
return 0;
}
int (*FArr[4])(int,int)={fnAdd,fnSub,fnMul,fnDiv};
pleaf *NewLeaf(char *in)
{
pleaf *t = 0;
t= (pleaf *)malloc(sizeof(pleaf));
t->token = in;
t->lc=0;
t->rc=0;
return t;
}
parser *NewParser(size_t max_token)
{
parser * t = 0;
if(max_token)
{
t = (parser *)malloc(sizeof(parser));
t->tcnt = 0;
t->root = 0;
t->tokentable = (char **)malloc(sizeof(char *)*max_token);
}
return t;
}
void KillParser(parser *in)
{
free(in->tokentable);
free(in);
}
int IsOperator(char expr) //연산자인지 확인
{
switch(expr)
{
case '+': case '-': case '*': case '/':
return 1;
}
return 0;
}
int Lexical(char *expr,parser *in) //입력 버퍼를 수식에 사용되는 토큰들로 이루어졌는지 확인하며 토큰 테이블을 구성
{
while(*expr)
{
if(isdigit(*expr)) //수식에 사용되는 토큰 중에 피연산자인 토큰인지 확인하여 토큰 테이블에 보관
{
in->tokentable[in->tcnt] = expr;
for(;isdigit(*expr);expr++);
}
else if(IsOperator(*expr)) //수식에 사용되는 토큰 중에 연산자인 토큰인지 확인하여 토큰 테이블에 보관
{
in->tokentable[in->tcnt]=expr;
expr++;
}
else //피 연산자나 연산자가 아닌 토큰이라면 수식이 될 수 없음
{
return 0;
}
in->tcnt++;
}
return 1;
}
int Syntax(parser *in)
{
size_t cnt=0;
char **base = in->tokentable;
if(isdigit(**base)) //토큰 테이블의 시작은 피연산자로 시작되어야 수식 문법에 맞음
{
for(cnt = 1,base++; cnt < in->tcnt ; cnt= cnt+2) //토큰 테이블 끝까지 다음을 충족해야 수식 문법에 맞음
{
if(IsOperator(**base) && isdigit(**(base+1))) //연산자 와 피 연산자의 쌍으로 구성되야 수식 문법에 맞음
{
base = base+2;
}
else //수식 문법에 맞지 않은 것임
{
return 0;
}
}
return 1;
}
return 0;
}
void HangOperand(pleaf *inleaf,parser *inp) //피 연산자를 파서트리에 매단다
{
pleaf *t = inp->root;
while(t->rc) //파서 트리의 우측 자식이 빈 곳을 찾음 - 피 연산자의 부모 연산자를 찾는 것임
{
t = t->rc;
}
t->rc = inleaf; //찾은 부모의 우측 자식으로 피연산자를 매단다
}
void HangOperator(pleaf *inleaf,parser *inp)//연산자를 파서트리에 매단다
{
char t = *(inleaf->token);
char r = *(inp->root->token);
if(((t=='*')||(t=='/')) && ((r== '+')||(r=='-'))) //새로 들어온 연산자가 root의 연산자보다 우선순위가 높을 때
{
inleaf->lc = inp->root->rc;
inp->root->rc = inleaf;
}
else
{
inleaf->lc = inp->root;
inp->root = inleaf;
}
}
void Parse(parser *in) //토큰 테이블을 가지고 파서 트리를 형성
{
size_t cnt = 0;
char **base=0;
pleaf *t = 0;
base = in->tokentable;
t = NewLeaf(*base);
in->root = t;
for(base++,cnt = 1;cnt<in->tcnt;base++,cnt=cnt+2)
{
t = NewLeaf(*base);
HangOperator(t,in);
base++;
t = NewLeaf(*base);
HangOperand(t,in);
}
}
int CalAll(pleaf *in) //파서 트리를 후위 순회하면서 계산하면 결과가 나옮
{
int rval = 0,lval = 0;
int ind = 0;
if(in->lc)
{
lval = CalAll(in->lc);
rval = CalAll(in->rc);
switch(*(in->token))
{
case '/':ind++;
case '*':ind++;
case '-':ind++;
}
return FArr[ind](lval,rval);
}
else
{
return atoi(in->token);
}
}
int CalCul(parser *in)
{
return CalAll(in->root);
}
void GetStr(char *in,size_t size)
{
size_t i=0;
while(i<size)
{
in[i] = getchar();
if(in[i] == '\n') break;
if((in[i] != ' ')&&(in[i]!='\t')) i++;//공백과 탭이 아닐 경우에만 i를 증가 - 즉, 공백과 탭은 제거
}
in[i]='\0';
fflush(stdin);
}
void Init()
{
ps = NewParser(MAX_BUFSIZE+1);
printf("수식을 입력하세요\n");
GetStr(buf,MAX_BUFSIZE);
}
void Run()
{
if(Lexical(buf,ps))
{
if(Syntax(ps))
{
Parse(ps);
printf("%s=%d\n",buf,CalCul(ps));
}
else
{
printf("[%s]는 문법 에러\n",buf);
}
}
else
{
printf("[%s]는 수식에 사용할 수 없는 어휘 사용\n",buf);
}
}
void Exit()
{
KillParser(ps);
}
void main()
{
Init();
Run();
Exit();
} |