-
前綴表達式
鎖定
- 中文名
- 前綴表達式
- 外文名
- Polish notation
- 例 如
- - 1 + 2 3
- 紀 念
- Jan Lukasiewicz
- 轉換算法
- 構造一個運算符棧
- 運算符
- 直接入棧
- 作 用
- 簡化複雜運算為出棧入棧兩種運算
前綴表達式基本釋義
例如，- 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)從右至左掃描中綴表達式，從右邊第一個字符開始判斷：
如果當前字符是數字，則分析到數字串的結尾並將數字串直接輸出。
如果是運算符，則比較優先級。如果當前運算符的優先級大於等於棧頂運算符的優先級(當棧頂是括號時，直接入棧)，則將運算符直接入棧；否則將棧頂運算符出棧並輸出，直到當前運算符的優先級大於等於棧頂運算符的優先級(當棧頂是括號時，直接入棧)，再將當前運算符入棧。
如果是括號，則根據括號的方向進行處理。如果是右的括號，則直接入棧；否則，遇左括號前將所有的運算符全部出棧並輸出，遇右括號後將左、向右的兩括號一起出棧(並不輸出)。
前綴表達式實例分析
將中綴表達式“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 99
char 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代碼
var
a:array[1..1000] of string;
s:string;
i,j,k,l,v:longint;
begin
readln(s);
j:=0; l:=length(s);
for i:=1 to l do
begin
if not(s[i]in['+','-','*','/']) then
begin
j:=j+1;
a[j]:=s[i];
end
else
begin
if (j>1)and(s[i]in['/'])and(s[i-1]in['*','/']) then
a[j]:='('+a[j]+')';
j:=j-1;
a[j]:=a[j]+s[i]+a[j+1];
if (i<l)and(s[i]in['+','-']) then
begin
k:=i;
v:=0;
repeat
k:=k+1;
if s[k]in['+','-','*','/'] then v:=v-1
else 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.
