前序表達式

前序表達式就是前綴表達式，不含括弧的算術表達式，而且它是將運算符寫在前面，運算元寫在後面的表達式，也稱為“波蘭式”。

基本介紹

別稱,概念,求值過程,作用,例子,一般算法,實例分析,運算符號,編程轉換,

別稱

前序表達式就是前綴表達式。

概念

前序表達式就是不含括弧的算術表達式，而且它是將運算符寫在前面，運算元寫在後面的表達式，也稱為“波蘭式”。例如，- 1 + 2 3，它等價於1-(2+3)。

求值過程

對於一個前序表達式的求值而言，首先要從右至左掃描表達式，從右邊第一個字元開始判斷，如果當前字元是數字則一直到數字串的末尾再記錄下來，如果是運算符，則將右邊離得最近的兩個“數字串”作相應的運算，以此作為一個新的“數字串”並記錄下來。一直掃描到表達式的最左端時，最後運算的值也就是表達式的值。例如，前序表達式“- 1 + 2 3“的求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，將+右移做相鄰兩數字串的運算符，記為2+3，結果為5，記錄下這個新數字串，並繼續向左掃描，掃描到1時，記錄下這個數字串，掃描到-時，將-右移做相鄰兩數字串的運算符，記為1-5，結果為-4，所以表達式的值為-4。

作用

前序表達式是一種十分有用的表達式，它將中序表達式轉換為可以依靠簡單的操作就能得到運算結果的表達式。例如，(a+b)*(c+d)轉換為*,+,a,b,+,c,d。它的優勢在於只用兩種簡單的操作，入棧和出棧就可以解決任何中序表達式的運算。其運算方式為：如果當前字元(或字元串)為數字或變數，則壓入棧內；如果是運算符，則將棧頂兩個元素彈出棧外並作相應運算，再將結果壓入棧內。當前序表達式掃描結束時，棧里的就是中序表達式運算的最終結果。

例子

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

編程轉換

#include<stdio.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);
}

相關詞條

熱門詞條

聯絡我們