释义
前缀表达式就是前序表达式。
前缀表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，为纪念其发明者波兰数学家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.
