前綴表達式

前綴表達式

前綴表達式是一種沒有括弧的算術表達式,與中綴表達式不同的是,其將運算符寫在前面,運算元寫在後面。為紀念其發明者波蘭數學家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.

相關詞條

熱門詞條

聯絡我們