abcde-怎樣用c實現鏈棧的算術表達式運算，不得使用stl模板

怎樣用c實現鏈棧的算術表達式運算，不得使用stl模板

按照嚴蔚敏版的書上的算法，用c語言鏈棧實現，不讓使用stl模板，有沒有原代碼

最佳回答：

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"math.h"

#define true 1

#define false 0

#define OPSETSIZE 8

typedef int Status;

unsigned char Prior[8][8] =

{ // 運算符優先級表

// '+' '-' '*' '/' '(' ')' '#' '^'

/*'+'*/'>','>','<','<','<','>','>','<',

/*'-'*/'>','>','<','<','<','>','>','<',

/*'*'*/'>','>','>','>','<','>','>','<',

/*'/'*/'>','>','>','>','<','>','>','<',

/*'('*/'<','<','<','<','<','=',' ','<',

/*')'*/'>','>','>','>',' ','>','>','>',

/*'#'*/'<','<','<','<','<',' ','=','<',

/*'^'*/'>','>','>','>','<','>','>','>'

};

typedef struct StackChar

{

char c;

struct StackChar *next;

}SC; //StackChar類型的結點SC

typedef struct StackFloat

{

float f;

struct StackFloat *next;

}SF; //StackFloat類型的結點SF

SC SC_Push(SC *s,char c) //SC類型的指針Push，返回p

{

SC *p=(SC)malloc(sizeof(SC));

p->c=c;

p->next=s;

return p;

}

SF SF_Push(SF *s,float f) //SF類型的指針Push，返回p

{

SF *p=(SF)malloc(sizeof(SF));

p->f=f;

p->next=s;

return p;

}

SC *SC_Pop(SC *s) //SC類型的指針Pop

{

SC *q=s;

s=s->next;

free(q);

return s;

}

SF *SF_Pop(SF *s) //SF類型的指針Pop

{

SF *q=s;

s=s->next;

free(q);

return s;

}

float Operate(float a,unsigned char theta, float b) //計算函數Operate

{

switch(theta)

{

case '+': return a+b;

case '-': return a-b;

case '*': return a*b;

case '/': return a/b;

case '^': return powf(a,b);

default : return 0;

}

}

char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};

Status In(char Test,char *TestOp)

{

int Find=false;

for (int i=0; i< OPSETSIZE; i++)

{

if(Test == TestOp[i])

Find= true;

}

return Find;

}

Status ReturnOpOrd(char op,char *TestOp)

{

for(int i=0; i< OPSETSIZE; i++)

{

if (op == TestOp[i])

return i;

}

}

char precede(char Aop, char Bop)

{

return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];

}

float EvaluateExpression(char* MyExpression)

{

// 算術表達式求值的算符優先算法

// 設OPTR和OPND分別為運算符棧和運算數棧，OP為運算符集合

SC *OPTR=NULL; // 運算符棧，字符元素

SF *OPND=NULL; // 運算數棧，實數元素

char TempData[20];

float Data,a,b;

char theta,*c,Dr[]={'#','\0'};

OPTR=SC_Push(OPTR,'#');

c=strcat(MyExpression,Dr);

strcpy(TempData,"\0");//字符串拷貝函數

while (*c!= '#' || OPTR->c!='#')

{

if (!In(*c, OPSET))

{

Dr[0]=*c;

strcat(TempData,Dr); //字符串連接函數

c++;

if (In(*c, OPSET))

{

Data=atof(TempData); //字符串轉換函數(double)

OPND=SF_Push(OPND, Data);

strcpy(TempData,"\0");

}

}

else // 不是運算符則進棧

{

switch (precede(OPTR->c, *c))

{

case '<': // 棧頂元素優先級低

OPTR=SC_Push(OPTR, *c);

c++;

break;

case '=': // 脫括號並接收下一字符

OPTR=SC_Pop(OPTR);

c++;

break;

case '>': // 退棧並將運算結果入棧

theta=OPTR->c;OPTR=SC_Pop(OPTR);

b=OPND->f;OPND=SF_Pop(OPND);

a=OPND->f;OPND=SF_Pop(OPND);

OPND=SF_Push(OPND, Operate(a, theta, b));

break;

} //switch

}

} //while

return OPND->f;

} //EvaluateExpression

int main(void)

{

char s[128];

puts("請輸入表達式:");

gets(s);

puts("該表達式的值為:");

printf("%s\b=%g\n",s,EvaluateExpression(s));

return 0;

}