釋義
前綴表達式就是前序表達式。
前綴表達式就是不含括号的算術表達式，而且它是将運算符寫在前面，操作數寫在後面的表達式，為紀念其發明者波蘭數學家jan Lukasiewicz也稱為“波蘭式”。例如，- 1 + 2 3，它等價于1-(2+3)。
求值方法
對于一個前綴表達式的求值而言，首先要從右至左掃描表達式，從右邊第一個字符開始判斷，如果當前字符是數字則一直到數字串的末尾再記錄下來，如果是運算符，則将右邊離得最近的兩個“數字串”作相應的運算，以此作為一個新的“數字串”并記錄下來。一直掃描到表達式的最左端時，最後運算的值也就是表達式的值。例如，前綴表達式“- 1 + 2 3“的求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，将+右移做相鄰兩數字串的運算符，記為2+3，結果為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
用編程實現中綴表達式向前綴表達式的轉換
#include
#include
#include
#include
#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
{
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
{
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("前綴表達式：%sn",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("運算結果為：%gn",Num.data);
printf("Continue(y/n)?");
ch=getch();
switch(ch)
{
case 'y':{system("cls");goto loop1;}
case 'n':
default :exit(0);
}
getch();
return(0);
}
後綴表達式轉前綴表達式
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
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
end;
end;
end;
writeln(a);
end.
