逆波蘭表達式：
逆波蘭表達式又叫後綴表達式。它是由相應的語法樹的後序遍歷的結果得到的。
例：5 - 8*(6 + 7) + 9 / 4：
其中綴表達式為：5 - 8 * 6 + 7 + 9 / 4
其語法樹如下：
因此根據語法樹可以得出他後序遍歷（後綴表達式）為：
5 8 6 7 + * - 9 4 / +
這樣就實現了中綴表達式到後綴表達式的轉換。
同樣的也可以得出他的前序遍歷（前綴表達式也稱波蘭表達式）：
+ - 5 * 8 + 6 7 / 9 4
逆波蘭表達式計算實現原理：
1.首先當遇到運算操作數時將其進行push操作；
2.當遇到操作符是將此時的棧pop兩次，先取出的棧頂為右操作數；
3.執行此方法到整個數組遍歷完。
實現算法如下：
void
CalFunction(SqStack *S,char str[]) {/*實現浮點型數據後綴表達式的加減乘除*/ Elemtype
number,e,d; char arr[MAXBUFFER]; int i=0,j=0; InitStack(S);
while(str[i]!='�') { while(isdigit(str[i])||str[i]=='.') //過濾數字 {
arr[j++]=str[i++]; arr[j]='�'; if( j >= MAXBUFFER ) {
printf("輸入單個數據過大！
"); return ; } if(str[i]==' ') {
number=atof(arr); //利用atof函數將數字字符串轉化為double型數據 PushStack(S,number);
//將轉換的數進行壓棧 j=0; //這裡不要忘記將j重新初始化進行下個數據的轉化 break; } }
/*如果遇到操作運算符則，彈出兩個數據進行運算，然後將得出的結果重新入棧*/ switch(str[i]) { case '+':
PopStack(S,&e); PopStack(S,&d); PushStack(S,d+e); break; case
'-': PopStack(S,&e); PopStack(S,&d); PushStack(S,d-e); break;
case '*': PopStack(S,&e); PopStack(S,&d); PushStack(S,d*e);
break; case '/': PopStack(S,&e); PopStack(S,&d); if(e == 0) {
printf("輸入出錯，分母為零！
"); return ; } PushStack(S,d/e); break; } i++; //繼續遍歷直到遍歷字符串結束 } PopStack(S,&e); printf("計算結果為：%lf",e); }
完整代碼如下：
#include
#include#include#include#define
INITSIZE 20 #define INCREMENT 10 #define MAXBUFFER 10 #define LEN
sizeof(Elemtype) /*棧的動態分配順序存儲結構*/ typedef double Elemtype; typedef
struct{ Elemtype *base; Elemtype *top; int StackSize; }SqStack; void
InitStack(SqStack *S) { S->base=(Elemtype*)malloc(LEN*INITSIZE);
assert(S->base != NULL); S->top=S->base;
S->StackSize=INITSIZE; } void PushStack(SqStack *S,Elemtype e) {
if(S->top - S->base >= S->StackSize) {
S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*LEN);
assert(S->base !=NULL); S->top=S->base+S->StackSize;
S->StackSize+=INCREMENT; } *S->top =e; S->top++; } void
PopStack(SqStack *S,Elemtype *e) { *e=*--S->top; } void
CalFunction(SqStack *S,char str[]) { Elemtype number,e,d; char
arr[MAXBUFFER]; int i=0,j=0; InitStack(S); while(str[i]!='�') {
while(isdigit(str[i])||str[i]=='.') //過濾數字 { arr[j++]=str[i++];
arr[j]='�'; if( j >= MAXBUFFER ) { printf("輸入單個數據過大！
");
return ; } if(str[i]==' ') { number=atof(arr);
//利用atof函數將數字字符轉化為double型數據 PushStack(S,number); //將轉換的數進行壓棧 j=0; break;
} } switch(str[i]) { case '+': PopStack(S,&e); PopStack(S,&d);
PushStack(S,d+e); break; case '-': PopStack(S,&e);
PopStack(S,&d); PushStack(S,d-e); break; case '*':
PopStack(S,&e); PopStack(S,&d); PushStack(S,d*e); break; case
'/': PopStack(S,&e); PopStack(S,&d); if(e == 0) {
printf("輸入出錯，分母為零！
"); return ; } PushStack(S,d/e); break; } i++;
} PopStack(S,&e); printf("計算結果為：%lf",e); } int main() { char
str[100]; SqStack S; printf("請按逆波蘭表達式輸入數據,每個數據之間用空格隔開:"); gets(str);
CalFunction(&S,str); return 0; } // 檢測用例 5 - (6 + 7) * 8 + 9 / 4 //
輸入：5 8 6 7 + * - 9 4 / + # // 輸出： - 96.750000
