前序表达式

前序表达式就是前缀表达式，不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，也称为“波兰式”。

前序表达式别称

前序表达式就是前缀表达式。

前序表达式概念

前序表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，也称为“波兰式”。例如，- 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

#include

#include

#include

#define MaxSize 99

char calc,expr;

int i,t;

struct

{

char data;

int top;

}Sym;

struct

{

double data;

int top;

}Num;

double ston(char x[],int *p)

{

int j=*p-1,i;

double n=0,m=0;

while(x>='0'&&x<='9')

{

j--;

}

if(x!='.')

{

for(i=j+1;i<=*p;i++)

{

n=10*n+(x-'0');

}

}

else

{

for(i=j+1;i<=*p;i++)

{

m=m+pow(0.1,i-j)*(x-'0');

}

if(x=='.')

{

*p=--j;

while(x>='0'&&x<='9')

{

j--;

}

for(i=j+1;i<=*p;i++)

{

n=10*n+(x-'0');

}

}

}

*p=j;

if(x=='-') return(-(n+m));

return(n+m);

}

void InitStack()

{

Sym.top=Num.top=-1;

}

void SymPush()

{

if(Sym.top

{

Sym.data=calc;

}

else

{

printf("Sym栈满\n");

return;

}

}

void SymPop()

{

if(Sym.top>=0)

{

expr=Sym.data;

}

else

{

printf("Sym栈空\n");

return;

}

}

void NumPush()

{

if(Num.top

{

Num.data=ston(expr,&i);

}

else

{

printf("Num栈满\n");

return;

}

}

void NumPop()

{

if(Num.top>=0)

{

if(expr!=' ')

{

switch(expr)

{

case '+':Num.data=Num.data+Num.data;break;

case '-':Num.data=Num.data-Num.data;break;

case '*':Num.data=Num.data*Num.data;break;

case '/':Num.data=Num.data/Num.data;break;

case '^':Num.data=pow(Num.data,Num.data);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!='\0')

{

i++;

}

while(i>=0)

{

if(calc>='0'&&calc<='9')

{

while((i>=0)&&((calc>='0'&&calc<='9')||(calc=='.')))

{

loop2:

expr=calc;

}

if((i>=0)&&((i==0&&calc!='(')||(calc=='+'||calc=='-')&&!(calc>='0'&&calc<='9')&&calc!=')')) goto loop2;

expr=' ';

}

else if(calc==')')

{

SymPush();

}

else if(calc=='(')

{

while(Sym.data!=')')

{

SymPop();

expr=' ';

}

Sym.data='\0';

i--;

}

else if(calc=='+'||calc=='-')

{

while(Sym.top>=0&&Sym.data!=')'&&Sym.data!='+'&&Sym.data!='-')

{

SymPop();

expr=' ';

}

SymPush();

}

else if(calc=='*'||calc=='/')

{

while(Sym.top>=0&&Sym.data=='^')

{

SymPop();

expr=' ';

}

SymPush();

}

else if(calc=='^')

{

SymPush();

}

else

{

i--;

}

}

while(Sym.top>=0)

{

SymPop();

expr=' ';

}

expr=Sym.data='\0';

for(i=0;i<=(t-2)/2;i++)

{

ch=expr;

expr=expr;

expr=ch;

}

printf("前序表达式：%s\n",expr);

for(i=t-2;i>=0;i--)

{

if((expr>='0'&&expr<='9')||((expr=='+'||expr=='-')&&(expr>='0'&&expr<='9')))

{

NumPush();

}

else

{

NumPop();

}

}

printf("运算结果为：%g\n",Num.data);

printf("Continue(y/n)?");

ch=getch();

switch(ch)

{

case 'y':{system("cls");goto loop1;}

case 'n':

default :exit(0);

}

getch();

return(0);

}