1、# include <stdio.h># include <malloc.h># include <conio.h># define maxsize 100 typedef double datatype1; typedef char datatype2;typedef struct stack1datatype1 data1maxsize;int top1; /* 棧頂元素 */ seqstack1,*pseqstack1; /* 順序棧 */ typedef struct stack2 datatype2 data2maxsize;int top2; /

2、* 棧頂元素 */ seqstack2,*pseqstack2; /* 順序棧 */* 棧的初始化 */ pseqstack1 init_seqstack1(void) pseqstack1 S;S=(pseqstack1)malloc(sizeof(pseqstack1); if(S)S->top1=-1;return S; pseqstack2 init_seqstack2(void) pseqstack2 S;S=(pseqstack2)malloc(sizeof(pseqstack2); if(S)S->top2=-1;return S;/* 判斷?？?*/int empt

3、y_seqstack1(pseqstack1 S)if(S->top1=-1)return 1;int empty_seqstack2(pseqstack2 S) if(S->top2=-1) return 1; else return 0;/*X 入棧 */int push_seqstack1(pseqstack1 S,datatype1 X)if(S->top1=maxsize-1)printf(" 棧滿，無法入棧！ n"); return 0;elseS->top1+;S->data1S->top1=X; return 1;int

4、push_seqstack2(pseqstack2 S,datatype2 X) if(S->top2=maxsize-1) printf(" 棧滿，無法入棧！ n"); return 0;elseS->top2+;S->data2S->top2=X; return 1;/*X 出棧 */int pop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0;else *X=S->data1S->top1; S->top1-; return 1;int

5、pop_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0;else *X=S->data2S->top2; S->top2-; return 1;/* 求棧頂元素 */int gettop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0;else *X=S->data1S->top1; return 1;int gettop_seqstack2(pseqstack2 S,datatype2 *

6、X) if(empty_seqstack2(S) return 0;else *X=S->data2S->top2; return 1;/* 判斷字符是否為操作數。若是返回1，否則返回 0*/int isnum(char c)if(c>='0' && c<='9') return 1;/* 求后綴表達式的值 */ double postfix_exp(char *A) pseqstack1 S; /* 定義棧 S*/ double operand=0;double result; /* 存放棧頂元素 */ double a

7、; /* 運算符 ch 前的操作數出棧存入a*/double b; /* 運算符 ch 后的操作數出棧存入b*/double c; /*c=a ch b*/char ch; /*存放讀取到的表達式(A)的字符*/ ch=*A+; /* 讀表達式字符 =>A*/S=init_seqstack1(); /* 初始化棧 */ while(ch!='#')/* 遇到元素 !='#' 時*/ if(isnum(ch)/* 判斷 ch 是否為數字字符 ,計算出操作數 */ operand=operand*10+(ch-'0');else /* 否則 *

8、/if(operand) push_seqstack1(S,operand);/* 當前字符不是數字 ,操作數結束 ,要入棧 */ operand=0;if(ch!='' && ch!=' ')pop_seqstack1(S,&b);/* 運算符 ch 后的操作數出棧存入 b*/pop_seqstack1(S,&a);/* 運算符 ch 前的操作數出棧存入 a*/switch(ch) /* 求 a ch b=? ,將結果賦給 c */ case '+' :c=a+b; break;case '-'

9、:c=a-b; break;case '*' :c=a*b; break;case '/' : if(b!=0)c=a/b;printf(" 分母為零 !"); push_seqstack1(S,c); /* 將 c 壓入棧中 */ ch=*A+; /* 指針向下移動一位 */* 遇到 '#'循環結束 */ gettop_seqstack1(S,&result);/* 此時棧頂元素即為計算結果 result*/ return result;/* 優先級判斷函數 */ int priority(char op) swit

10、ch(op)case '#': return 1;case ')': return 2; case '+':case '-': return 3; case '*':case '/': return 4; case '(': return 5; default : return 0; /* 將指針 infixexp 指向的中綴表達式轉換為指針 postfixexp 指向的后綴表達式 */int infix_exp_value(char *infixexp,char *postfixe

11、xp) pseqstack2 S; /* 定義棧 S*/ int count=0;char w; /* 存放讀取到的表達式 (infixexp) 的字符 */char c; /* 存放棧頂元素 */char topelement;/* 存出棧元素 */S=init_seqstack2(); /* 初始化棧 */ if(!S) /* 棧的初始化判斷 */printf(" 棧初始化失敗 !");return 0;push_seqstack2(S,'#'); /* 將結束符 '# '加入運算符棧 S 中*/ w=*infixexp; /* 讀表達式

12、字符 =>w*/while(gettop_seqstack2(S,&c),c)!='#'|w!='#')/*<3> 棧頂元素不等于 '#' 或 w 不等于 '#' 時循環*/if(isnum(w)/*判斷w是否為操作數，若是直接輸出,讀下一個字符=>w，轉<3>*/if(count)*postfixexp='' postfixexp+; count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else /*w 若是運算符分類如下

13、*/count=1;if( (gettop_seqstack2(S,&c),c)='(' && w=')' )/* 如果棧頂為'('并且 w 為')'則'('出棧不輸出，讀下一個字符=>w,轉<3>*/pop_seqstack2(S,&topelement); /* 將'('出棧存入 topelement*/ w=*(+infixexp);else if(gettop_seqstack2(S,&c),c)='('|priori

14、ty(gettop_seqstack2(S,&c),c) )<priority(w) )/*如果棧頂為'('或者棧頂優先級小于w優先級，則w入棧,讀下一個字符=>w，轉<3>*/push_seqstack2(S,w); w=*(+infixexp);else/* 否則 */* 從運算符棧中出棧并輸出,轉<3>*/pop_seqstack2(S,&topelement); *postfixexp=topelement; postfixexp+;*postfixexp='#'/* 在指針 postfixexp 指向的后綴表達式結尾追加字符 '#'*/ *(+postfixexp)='0'/* 在指針 postfixexp 指向的后綴表達式最后追加結束符 '0'*/ return 1;/*主函數*/int mai n()int i=0;char Amaxsize;char Bmaxsize;printf(”請輸入表達式，如:20+13#,必須以#號結尾!n"); /* 1+2*(9+7)-4 /2#23+(12*3-2)/4+34*5/7)