|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// ?¨ò?????êy?YààDí
typedef struct _symbol elem_t;
struct _symbol
{
char symb; // 2ù×÷·?
int pri; // ó??è??
};
// ?¨ò?????ààDí
#define STACK_MAX_SIZE 50
typedef struct _stack stack_t;
struct _stack
{
elem_t data[STACK_MAX_SIZE];
int top_pt; // ???￥????
};
// 2ù×÷·?o?
enum{
S_OPERATOR,
S_DIGIT,
S_BRACKET,
};
// ′′?¨ò???????
stack_t *StackCreate(void)
{
stack_t *s;
s = (stack_t *)malloc(sizeof(stack_t));
if (s==NULL)
{
printf("could not alloc memory for s");
exit(1);
}
memset(&s->data,0,sizeof(elem_t)*STACK_MAX_SIZE);
s->top_pt = 0;
return s;
}
// êí·????°éê??μ??ú′?
void StackDelete(stack_t *s)
{
free(s);
}
// ?ì2é????ê?·??a???ò???a?ú
int StackIsEmpty(stack_t *s)
{
return !s->top_pt;
}
int StackIsFull(stack_t *s)
{
return s->top_pt == STACK_MAX_SIZE;
}
// è???
void StackPush(stack_t *s,elem_t d)
{
if(StackIsFull(s))
{
printf("stack is full");
StackDelete(s);
exit(0);
}
s->data[s->top_pt] = d;
s->top_pt++;
}
// 3???
elem_t StackPop(stack_t *s)
{
elem_t retval;
if(StackIsEmpty(s))
{
printf("stack is empty");
StackDelete(s);
exit(0);
}
retval = s->data[s->top_pt-1];
s->top_pt--;
return retval;
}
// 2é?′·μ?????￥êy?Y
elem_t StackVeiwTop(stack_t *s)
{
elem_t retval;
if(StackIsEmpty(s))
{
printf("stack is empty");
StackDelete(s);
exit(0);
}
retval = s->data[s->top_pt-1];
return retval;
}
// ?D×o±í′?ê?×a???aoó×o±í′?ê?
void Nifix2Postfix(char *ni,char *po)
{
stack_t *st;
elem_t retval;
elem_t param;
int pri;
int flag;
// éú3é·?o???
st = StackCreate();
// ·?o???μ??áê?±ê??￡?ò???×?μíó??è??μ?·?o?
param.pri = -1;
param.symb = '@';
StackPush(st,param);
// é¨?èê?è?×?·?′?￡??±μ?'\0'?a?1
while(*ni)
{
switch(*ni)
{
// 1y??μ??à??????
case ' ':
*po++=' ';
while((*ni == ' ') && (*ni != '\0'))
ni++;
break;
// +- μ?ó??è???a1
case '+':
case '-':
pri = 1;
flag = S_OPERATOR;
break;
// * / ó??è???a2
case '*':
case '/':
pri = 2;
flag = S_OPERATOR;
break;
// è?1?ê?à¨o?
case '(':
case ')':
pri = 0;
flag = S_BRACKET;
break;
// ????μ????′×?êy×?￡??ò???′?aêy±?á?
default:
// è?1????°μ?ò???·?o?ò2ê?êy×?μ??°￡????′???°ê?3?μ?
// ?????í?àóàá?￡?2ù×÷????·μ??ò???
if (flag == S_DIGIT)
po--;
flag = S_DIGIT;
break;
}
// è?1?é¨?èμ?μ?ê?2ù×÷·?
if (flag == S_OPERATOR)
{
// 2é?′????×??￥??μ?·?o?
retval = StackVeiwTop(st);
// è?1?μ±?°·?o?ó??è??D?óúμèóú????μ?×??￥??μ?
// ·?o?μ?ó??è??μ??°￡??è3???
if(pri <= retval.pri)
{
// 3???2￠?òê?3?
retval = StackPop(st);
*po++ = retval.symb;
*po++ = ' ';
}
// ??D?·?o?è???
param.pri = pri;
param.symb = *ni;
StackPush(st,param);
}
// è?1?é¨?èμ?μ?ê?à¨o?
if (flag == S_BRACKET)
{
// ×óà¨o?μ??°?±?óè???
if(*ni == '(')
{
param.pri = pri;
param.symb = *ni;
StackPush(st,param);
} // óòà¨o?μ??°??????3???
else if(*ni == ')'){
// è?2?3???￡??±μ?ó?μ?×óà¨o??a?1
while(1)
{
retval = StackPop(st);
if (retval.symb == '(')
break;
*po++ = retval.symb;
*po++ = ' ';
}
}
}
if (flag == S_DIGIT)
{
*po++ = *ni;
*po++ = ' ';
}
ni++;
}
// ??????μ?ê￡óà?úèYè?2?3???
while((retval.symb = StackPop(st).symb) != '@')
{
*po++ = retval.symb;
*po++ = ' ';
}
// ìí?ó×?·?′??áê?±ê??￡?òò?a???°?àê?3?á?ò???????￡??ùò??aà?è￥μ?
*(po-1)='\0';
// êí·?·?o?????
StackDelete(st);
}
/*****************************************************************
oó×o±í′?ê?ó?μ????? */
typedef struct _d_stack d_stack_t;
struct _d_stack
{
double data[50];
int index;
};
d_stack_t *stack_init(void)
{
d_stack_t *st;
// ?±?óéê??ò??é?ú′?×??￡?a????
st = (d_stack_t *)malloc(sizeof(d_stack_t));
st->index = 0;
return st;
}
void stack_delete(d_stack_t *st)
{
free(st);
}
void push(d_stack_t *st,double d)
{
st->data[st->index++]=d;
}
double pop(d_stack_t *st)
{
double retval;
retval = st->data[st->index-1];
st->index--;
return retval;
}
// ????oó×o±í′?ê?
// ?aà???ê??òμ￥μ??-àí2ù×÷￡?oü?à?é???1??óD?D??íê??
// Dèòaò?oóíêé?
double PostfixCalculate(char *s)
{
double retval,param;
d_stack_t *st;
char *tmp=(char*)malloc(sizeof(char)*20);
char *pt1=tmp;
char *pt2=tmp;
st = stack_init();
while(*s)
{
// 2?′|àí????
if(*s == ' ')
{
s++;
continue;
}
// è?1??a·?o??ò??DD?àó|μ?????
switch(*s)
{
case '+':
param = pop(st);
param += pop(st);
push(st,param);
break;
case '-':
param = pop(st);
param = pop(st) - param;
push(st,param);
break;
case '*':
param = pop(st);
param *= pop(st);
push(st,param);
break;
case '/':
param = pop(st);
param = pop(st) / param;
push(st,param);
break;
default:
// è?1?ê?êy×??ò×a?ˉ?a??μ?êy
// ±￡′?μ±?°????
pt1 = pt2 = tmp;
// ?áè?????êy×?×?·?′?￡?àyè?"16"
while(*s != ' ')
*pt1++ = *s++;
*pt1 = '\0'; // ??μ?21???áê?·?
// ?àò??ˉá?ò???μ??·￡??aá??￥????éùò???
s--;
// ×a??
retval = atof(pt2);
// ???á1??1è?????
push(st,retval);
break;
}
s++;
}
// ×?oóò????íê??á1?á?
retval = pop(st);
stack_delete(st);
free(tmp);
return retval;
}
int main(int argc,char *argv[])
{
char *s1 = "16-9*(4+3)";
char s2[50]={'\0'};
// translate nifix to postfix expresstion
Nifix2Postfix(s1,s2);
printf("\nnifix : %s",s1);
printf("\npostfix : %s",s2);
printf("\nPostfix calculate: %.2f\n",PostfixCalculate(s2));
return 0;
}
|
