利用棧實現表達式樹這裡我一共有兩種思路：
part one:
首先判斷輸入表達式的每個字符，如果遇到運算符，不壓棧，
接著彈出兩個棧頂的元素，進行元素，接著把結果壓棧。
代碼：
//棧實現表達式 //思路：此程序的思路是，讀取輸入的字符串，然後判斷每個字符， //當遇到的是運算符，這時運算符不如棧，接著把棧頂的兩個元素 //出棧，然後運算，然後再將得的結果壓棧 //楊鑫 #include結果：#include typedef int SElemType; // 棧的元素類型 #define STACK_INIT_SIZE 10 // 存儲空間初始分配量 #define STACKINCREMENT 2 // 存儲空間分配增量 /* *順序棧的結構體 * */ typedef struct SqStack { SElemType *base; // 在棧構造之前和銷毀之後，base的值為NULL SElemType *top; // 棧頂指針 int stacksize; // 當前已分配的存儲空間，以元素為單位 }SqStack; /* *構造一個棧 * */ int InitStack(SqStack *S) { // 為棧底分配一個指定大小的存儲空間 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); // 存儲分配失敗 (*S).top = (*S).base; // 棧底與棧頂相同表示一個空棧 (*S).stacksize = STACK_INIT_SIZE; return 1; } /* *獲取棧頂元素 * */ int GetTop(SqStack S,SElemType *e) { if(S.top > S.base) { *e = *(S.top-1); // 棧頂指針的下一個位置為棧頂元素 return 1; } else return 0; } /* *入棧（壓棧） * */ int Push(SqStack *S, SElemType e) { if((*S).top - (*S).base >= (*S).stacksize) // 棧滿，追加存儲空間 { (*S).base = (SElemType *)realloc((*S).base, ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType)); if( !(*S).base ) exit(0); // 存儲分配失敗 (*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; } *((*S).top)++=e; // 這個等式的++ * 優先級相同，但是它們的運算方式，是自右向左 return 1; } /* *出棧 * */ int Pop(SqStack *S,SElemType *e) { if((*S).top == (*S).base) return 0; *e = *--(*S).top; // 這個等式的++ * 優先級相同，但是它們的運算方式，是自右向左 return 1; } /* *判斷優先級 * */ SElemType Precede(SElemType t1,SElemType t2) { SElemType f; switch(t2) { case '+': case '-': if(t1=='('||t1=='#') f='<'; else f='>'; break; case '*': case '/': if(t1=='*'||t1=='/'||t1==')') f='>'; else f='<'; break; case '(': if(t1==')') { printf(ERROR1 ); exit(0); } else f='<'; break; case ')': switch(t1) { case '(': f='='; break; case '#': printf(ERROR2 ); exit(0); default: f='>'; } break; case '#': switch(t1) { case '#': f='='; break; case '(': printf(ERROR3 ); exit(0); default: f='>'; } } return f; } /* *搜索運算符 * */ int In(SElemType c) { switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'#':return 1; default:return 0; } } /* *運算 * */ SElemType Operate(SElemType a,SElemType theta,SElemType b) { SElemType c; a=a-48; //ASCII值轉化為對應的十進制值 b=b-48; //ASCII值轉化為對應的十進制值 switch(theta) { case'+': c=a+b+48; break; case'-': c=a-b+48; break; case'*': c=a*b+48; break; case'/':c=a/b+48; } return c; } /* *比較運算符優先級 * */ SElemType EvaluateExpression() { SqStack OPTR,OPND; SElemType a,b,c,x,theta; InitStack(&OPTR); Push(&OPTR,'#'); InitStack(&OPND); c=getchar(); GetTop(OPTR,&x); while(c!='#'||x!='#') { if(In(c)) // 是7種運算符之一 switch(Precede(x,c)) { case'<': Push(&OPTR,c); // 棧頂元素優先權低 c=getchar(); break; case'=': Pop(&OPTR,&x); // 脫括號並接收下一字符 c=getchar(); break; case'>': Pop(&OPTR,&theta); // 退棧並將運算結果入棧 Pop(&OPND,&b); Pop(&OPND,&a); Push(&OPND,Operate(a,theta,b)); break; } else if(c>='0'&&c<='9') // c是操作數 { Push(&OPND,c); c=getchar(); } else // c是非法字符 { printf(非法字符！！ ); exit(0); } GetTop(OPTR,&x); } GetTop(OPND,&x); return x; } int main() { printf(請輸入算術表達式,並以#結束 ); printf(例如：3*(7-5)# ); printf(%c ,EvaluateExpression()); return 0; }
part two:
就是把所有輸入壓棧，分別有運算符棧和運算值棧，然後彈出一個運算符，
彈出兩個運算值，進行運算，結果再壓棧。
代碼：（C++版本）
//棧實現表達式求和 //利用棧實現表達式運算 //楊鑫 #include#include #include #include #include #include using namespace std; #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 *Push(SC *s,char c) //SC類型的指針Push，返回p { SC *p=(SC*)malloc(sizeof(SC)); p->c=c; p->next=s; return p; } SF *Push(SF *s,float f) //SF類型的指針Push，返回p { SF *p=(SF*)malloc(sizeof(SF)); p->f=f; p->next=s; return p; } SC *Pop(SC *s) //SC類型的指針Pop { SC *q=s; s=s->next; free(q); return s; } 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 pow(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[]={'#',''}; OPTR=Push(OPTR,'#'); c=strcat(MyExpression,Dr); strcpy(TempData,);//字符串拷貝函數 while (*c!= '#' || OPTR->c!='#') { if (!In(*c, OPSET)) { Dr[0]=*c; strcat(TempData,Dr); //字符串連接函數 c++; if (In(*c, OPSET)) { Data=atof(TempData); //字符串轉換函數(double) OPND=Push(OPND, Data); strcpy(TempData,); } } else // 不是運算符則進棧 { switch (precede(OPTR->c, *c)) { case '<': // 棧頂元素優先級低 OPTR=Push(OPTR, *c); c++; break; case '=': // 脫括號並接收下一字符 OPTR=Pop(OPTR); c++; break; case '>': // 退棧並將運算結果入棧 theta=OPTR->c;OPTR=Pop(OPTR); b=OPND->f;OPND=Pop(OPND); a=OPND->f;OPND=Pop(OPND); OPND=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=%g ,s,EvaluateExpression(s)); system(pause); return 0; }
