前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是,其将运算符写在前面,操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz,前缀表达式也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。
![](https://qnimg.zhaibian.com/upload/2023013010/7e41afdcc2445692520d0cd60669d6b0.jpg)
前缀表达式
Jan Lukasiewicz
构造一个运算符栈
直接入栈
基本释义
前缀表达式就是前序表达式,是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式。
例如,- 1 + 2 3,它等价于1-(2+3)。
注意事项
后缀表达式源自于前缀表达式,为了区分前缀和后缀表示,通常将后缀表示称为逆波兰表示;因前缀表示并不常用,所以有时也将后缀表示称为波兰表示。
运算优势
前缀表达式是一种十分有用的表达式,将中缀表达式转换为前缀表达式后,就可以只依靠出栈、入栈两种简单操作完全解决中缀表达式的全部运算。
例如,(a+b)*(c+d)转换为*,+,a,b,+,c,d。
后面的前缀表达式的运算方式为:如果当前字符(或字符串)为数字或变量,则压入栈内;如果是运算符,则将栈顶两个元素弹出栈外并作相应运算,再将结果压入栈内。当前缀表达式扫描结束时,栈里的就是中缀表达式运算的最终结果。对比中缀运算的步骤,不难发现前缀运算在计算机上的优势。
求值方法
对于一个前缀表达式的求值而言,首先要从右至左扫描表达式,从右边第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再记录下来,如果是运算符,则将右边离得最近的两个“数字串”作相应的运算,以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时,最后运算的值也就是表达式的值。例如,前缀表达式“- 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
转换算法
(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
编程转换
1 | #include<stdio.h> |
2 | #include<stdlib.h> |
3 | #include<conio.h> |
4 | #include<math.h> |
5 | #include<string.h> |
6 | #define MaxSize 99 |
7 | char calc[MaxSize],expr[MaxSize]; |
8 | int i,t; |
9 | struct { |
10 | char data[MaxSize]; |
11 | int top; |
12 | } Sym; |
13 | struct { |
14 | double data[MaxSize]; |
15 | int top; |
16 | } Num; |
17 | double ston(char x[],int *p) { |
18 | int j=*p-1,i; |
19 | double n=0,m=0; |
20 | while(x[j]>='0'&&x[j]<='9') { |
21 | j--; |
22 | } |
23 | if(x[j]!='.') { |
24 | for(i=j+1; i<=*p; i++) { |
25 | n=10*n+(x[i]-'0'); |
26 | } |
27 | } else { |
28 | for(i=j+1; i<=*p; i++) { |
29 | m=m+pow(0.1,i-j)*(x[i]-'0'); |
30 | } |
31 | if(x[j]=='.') { |
32 | *p=--j; |
33 | while(x[j]>='0'&&x[j]<='9') { |
34 | j--; |
35 | } |
36 | for(i=j+1; i<=*p; i++) { |
37 | n=10*n+(x[i]-'0'); |
38 | } |
39 | } |
40 | } |
41 | *p=j; |
42 | if(x[*p]=='-') return(-(n+m)); |
43 | return(n+m); |
44 | } |
45 | void InitStack() { |
46 | Sym.top=Num.top=-1; |
47 | } |
48 | void SymPush() { |
49 | if(Sym.top<MaxSize-1) { |
50 | Sym.data[++Sym.top]=calc[i--]; |
51 | } else { |
52 | printf("Sym栈满 "); |
53 | return; |
54 | } |
55 | } |
56 | void SymPop() { |
57 | if(Sym.top>=0) { |
58 | expr[++t]=Sym.data[Sym.top--]; |
59 | } else { |
60 | printf("Sym栈空 "); |
61 | return |
62 | } |
63 | } |
64 | void NumPush() { |
65 | if(Num.top<MaxSize-1) { |
66 | Num.data[++Num.top]=ston(expr,&i); |
67 | } else { |
68 | printf("Num栈满 "); |
69 | return; |
70 | } |
71 | } |
72 | void NumPop() { |
73 | if(Num.top>=0) { |
74 | f(expr[i]!=' ') { |
75 | switch(expr[i |
76 | case '+': |
77 | Num.data[Num.top- |
78 | 1]=Num.data[Num.top]+Num.data[Num.top-1]; |
79 | break; |
80 | case '-': |
81 | Num.data[Num.top-1]=Num.data[Num.top]- |
82 | Num.data[Num.top-1]; |
83 | break; |
84 | case '*': |
85 | Num.data[Num.top- |
86 | 1]=Num.data[Num.top]*Num.data[Num.top-1]; |
87 | break; |
88 | case '/': |
89 | Num.data[Num.top- |
90 | 1]=Num.data[Num.top]/Num.data[Num.top-1]; |
91 | break; |
92 | case '^': |
93 | Num.data[Num.top- |
94 | 1]=pow(Num.data[Num.top],Num.data[Num.top-1]); |
95 | break; |
96 | } |
97 | Num.top--; |
98 | } |
99 | } else { |
100 | printf("Num栈空 "); |
101 | return; |
102 | } |
103 | } |
104 | int main(void) { |
105 | char ch; |
106 | loop1: |
107 | i=0,t=-1; |
108 | system("cls"); |
109 | printf("中缀表达式:"); |
110 | InitStack(),gets(calc); |
111 | while(calc[i]!=' |