前綴表達式

前綴表達式是一種沒有括弧的算術表達式，與中綴表達式不同的是，其將運算符寫在前面，運算元寫在後面。為紀念其發明者波蘭數學家Jan Lukasiewicz，前綴表達式也稱為“波蘭式”。例如，- 1 + 2 3，它等價於1-(2+3)。

基本介紹

• 中文名：前綴表達式
• 外文名：Polish notation
• 例如：- 1 + 2 3
• 紀念：Jan Lukasiewicz
• 轉換算法：構造一個運算符棧
• 運算符：直接入棧
• 作用：簡化複雜運算為出棧入棧兩種運算

基本釋義

前綴表達式就是前序表達式，是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式。

例如，- 1 + 2 3，它等價於1-(2+3)。

注意事項

後綴表達式源自於前綴表達式，為了區分前綴和後綴表示，通常將後綴表示稱為逆波蘭表示；因前綴表示並不常用，所以有時也將後綴表示稱為波蘭表示。

運算優勢

前綴表達式是一種十分有用的表達式，將中綴表達式轉換為前綴表達式後，就可以只依靠出棧、入棧兩種簡單操作完全解決中綴表達式的全部運算。

例如，(a+b)*(c+d)轉換為*,+,a,b,+,c,d。

後面的前綴表達式的運算方式為：如果當前字元(或字元串)為數字或變數，則壓入棧內；如果是運算符，則將棧頂兩個元素彈出棧外並作相應運算，再將結果壓入棧內。當前綴表達式掃描結束時，棧里的就是中綴表達式運算的最終結果。對比中綴運算的步驟，不難發現前綴運算在計算機上的優勢。

求值方法

對前綴表達式求值，要從右至左掃描表達式，首先從右邊第一個字元開始判斷，若當前字元是數字則一直到數字串的末尾再記錄下來，若為運算符，則將右邊離得最近的兩個“數字串”作相應運算，然後以此作為一個新的“數字串”並記錄下來；掃描到表達式最左端時掃描結束，最後運算的值即為表達式的值。

例如：對前綴表達式“- 1 + 2 3”求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，將+右移做相鄰兩數字串的運算符，記為2+3，結果為5，記錄下5這個新數字串，然後繼續向左掃描，掃描到1時，記錄下這個數字串，掃描到-時，將-右移做相鄰兩數字串的運算符，記為1-5，結果為-4，此時關於這個表達式的全部運算已完成，故表達式的值為-4。

表達對照

中綴表達式轉化為前綴表達式的例子:

a+b ---> +,a,b

a+(b-c) ---> +,a,-,b,c

a+(b-c)*d ---> +,a,*,-,b,c,d

a+1+3 ---> +,+,a,1,3

轉換算法

(1) 首先構造一個運算符棧(也可放置括弧)，運算符(以括弧為分界點)在棧內遵循越往棧頂優先權不降低的原則進行排列。

(2)從右至左掃描中綴表達式，從右邊第一個字元開始判斷：

如果當前字元是數字，則分析到數字串的結尾並將數字串直接輸出。

如果是運算符，則比較優先權。如果當前運算符的優先權大於等於棧頂運算符的優先權(當棧頂是括弧時，直接入棧)，則將運算符直接入棧；否則將棧頂運算符出棧並輸出，直到當前運算符的優先權大於等於棧頂運算符的優先權(當棧頂是括弧時，直接入棧)，再將當前運算符入棧。

如果是括弧，則根據括弧的方向進行處理。如果是向右的括弧，則直接入棧；否則，遇向左的括弧前將所有的運算符全部出棧並輸出，遇右括弧後將向左、向右的兩括弧一起出棧(並不輸出)。

(3) 重複上述操作(2)直至掃描結束，將棧內剩餘運算符全部出棧並輸出，再逆綴輸出字元串。中綴表達式也就轉換為前綴表達式了。

實例分析

將中綴表達式“1+((2+3)*4)-5”轉換為前綴表達式。

中綴表達式	前綴表達式	（棧尾）運算符棧（棧頂）	說明
5	5	空	5，是數字串直接輸出
-	5	-	-，棧內無運算符，直接入棧
）	5	-）	)，直接入棧
4	5 4	-）	4，是數字串直接輸出
*	5 4	-）*	*，棧頂是括弧，直接入棧
)	5 4	- ) * )	)，直接入棧
3	5 4 3	- ) * )	3，是數字串直接輸出
+	5 4 3	- ) * ) +	+，棧頂是括弧，直接入棧
2	5 4 3 2	- ) * )+	2，是數字串直接輸出
(	5 4 3 2+	- ) *	(，與棧里最後一個）抵消，並釋放它們之間的+
(	5 4 3 2+*	-	(，方法與上類同，請參考下一目錄
+	5 4 3 2+*	-+	+，優先權大於等於棧頂運算符，直接入棧
1	5 4 3 2+*1	-+	1，是數字串直接輸出
空	5 4 3 2+*1+-	空	掃描結束，將棧內剩餘運算符全部出棧並輸出
空	- + 1 * + 2 3 4 5	空	逆綴輸出字元串

符號處理

對運算符的具體處理方法如下:

)：直接入棧

(：遇)前，將運算符全部出棧並輸出；遇)後，將兩括弧一起刪除①

+、-：1

*、/、%：2

^：3

編程轉換

C++代碼

#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<math.h>#include<string.h>#define MaxSize 99char calc[MaxSize],expr[MaxSize];int i,t;struct{char data[MaxSize];int top;}Sym;struct{double data[MaxSize];int top;}Num;double ston(char x[],int *p){int j=*p-1,i;double n=0,m=0;while(x[j]>='0'&&x[j]<='9'){j--;}if(x[j]!='.'){for(i=j+1;i<=*p;i++){n=10*n+(x[i]-'0');}}else{for(i=j+1;i<=*p;i++){m=m+pow(0.1,i-j)*(x[i]-'0');}if(x[j]=='.'){*p=--j;while(x[j]>='0'&&x[j]<='9'){j--;}for(i=j+1;i<=*p;i++){n=10*n+(x[i]-'0');}}}*p=j;if(x[*p]=='-') return(-(n+m));return(n+m);}void InitStack(){Sym.top=Num.top=-1;}void SymPush(){if(Sym.top<MaxSize-1){Sym.data[++Sym.top]=calc[i--];}else{printf("Sym棧滿\n");return;}}void SymPop(){if(Sym.top>=0){expr[++t]=Sym.data[Sym.top--];}else{printf("Sym棧空\n");return;}}void NumPush(){if(Num.top<MaxSize-1){Num.data[++Num.top]=ston(expr,&i);}else{printf("Num棧滿\n");return;}}void NumPop(){if(Num.top>=0){if(expr[i]!=' '){switch(expr[i]){case '+':Num.data[Num.top-1]=Num.data[Num.top]+Num.data[Num.top-1];break;case '-':Num.data[Num.top-1]=Num.data[Num.top]-Num.data[Num.top-1];break;case '*':Num.data[Num.top-1]=Num.data[Num.top]*Num.data[Num.top-1];break;case '/':Num.data[Num.top-1]=Num.data[Num.top]/Num.data[Num.top-1];break;case '^':Num.data[Num.top-1]=pow(Num.data[Num.top],Num.data[Num.top-1]);break;}Num.top--;}}else{printf("Num棧空\n");return;}}int main(void){char ch;loop1:i=0,t=-1;system("cls");printf("中綴表達式：");InitStack(),gets(calc);while(calc[i]!='\0'){i++;}while(i>=0){if(calc[i]>='0'&&calc[i]<='9'){while((i>=0)&&((calc[i]>='0'&&calc[i]<='9')||(calc[i]=='.'))){loop2:expr[++t]=calc[i--];}if((i>=0)&&((i==0&&calc[i]!='(')||(calc[i]=='+'||calc[i]=='-')&&!(calc[i-1]>='0'&&calc[i-1]<='9')&&calc[i-1]!=')')) goto loop2;expr[++t]=' ';}else if(calc[i]==')'){SymPush();}else if(calc[i]=='('){while(Sym.data[Sym.top]!=')'){SymPop();expr[++t]=' ';}Sym.data[Sym.top--]='\0';i--;}else if(calc[i]=='+'||calc[i]=='-'){while(Sym.top>=0&&Sym.data[Sym.top]!=')'&&Sym.data[Sym.top]!='+'&&Sym.data[Sym.top]!='-'){SymPop();expr[++t]=' ';}SymPush();}else if(calc[i]=='*'||calc[i]=='/'){while(Sym.top>=0&&Sym.data[Sym.top]=='^'){SymPop();expr[++t]=' ';}SymPush();}else if(calc[i]=='^'){SymPush();}else{i--;}}while(Sym.top>=0){SymPop();expr[++t]=' ';}expr[++t]=Sym.data[++Sym.top]='\0';for(i=0;i<=(t-2)/2;i++){ch=expr[i];expr[i]=expr[(t-2)-i];expr[(t-2)-i]=ch;}printf("前綴表達式：%s\n",expr);for(i=t-2;i>=0;i--){if((expr[i]>='0'&&expr[i]<='9')||((expr[i]=='+'||expr[i]=='-')&&(expr[i+1]>='0'&&expr[i+1]<='9'))){NumPush();}else{NumPop();}}printf("運算結果為：%g\n",Num.data[0]);printf("Continue(y/n)?");ch=getch();switch(ch){case 'y':{system("cls");goto loop1;}case 'n':default :exit(0);}getch();return(0);}

公式轉換

pascal代碼

vara:array[1..1000] of string;s:string;i,j,k,l,v:longint;beginreadln(s);j:=0; l:=length(s);for i:=1 to l dobeginif not(s[i]in['+','-','*','/']) thenbeginj:=j+1;a[j]:=s[i];endelsebeginif (j>1)and(s[i]in['/'])and(s[i-1]in['*','/']) thena[j]:='('+a[j]+')';j:=j-1;a[j]:=a[j]+s[i]+a[j+1];if (i<l)and(s[i]in['+','-']) thenbegink:=i;v:=0;repeatk:=k+1;if s[k]in['+','-','*','/'] then v:=v-1else v:=v+1;until (k=l)or(v<1);if (k<l)and(s[k]in['*','/']) then a[j]:='('+a[j]+')';end;end;end;writeln(a[1]);end.