逆波兰表达式

一、将中缀表达式转换成后缀表达式算法：

1、从左至右扫描中缀表达式。

2、若读取的是操作数（数字），则判断该操作数的类型，并将该操作数存入操作数堆栈

3、若读取的是运算符

(1) 该运算符为左括号"("，则直接存入运算符堆栈。

(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。

(3) 该运算符为非括号运算符：

(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。

(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。

4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

二、逆波兰表达式求值算法：

1、循环扫描语法单元的项目。

2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。

3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。

4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。

5、将运算结果重新压入堆栈。

6、重复步骤2-5，全部运算完后，最后堆栈中数即为结果值。

链接：逆波兰表达式求值

 1 #include<stdio.h>  
 2 #include<stdlib.h>  
 3 typedef struct stu  
 4 {  
 5     char s;  
 6     struct stu *next;  
 7 }stack;  
 8 void push(stack **top,char c)  
 9 {  
10     stack *p;  
11     p=(stack *)malloc(sizeof(stack));  
12     p->s=c;  
13     p->next=(*top);  
14     *top=p;  
15 }  
16 void pop(stack **top)  
17 {  
18     *top=(*top)->next;  
19 }  
20 int yxj(char a,char b)  
21 {  
22     if((a=='+'||a=='-')&&(b=='*'||b=='\'))  
23         return 0;  
24     return 1;  
25 }  
26 int main()  
27 {  
28     stack *top=NULL;  
29     int m[110];  
30     char s[110],c[110]={0};  
31     int i,j=0,t=1;  
32     gets(s);  
33     for(i=0;s[i]!='@';i++){  
34         if(s[i]>='0'&&s[i]<='9'){  
35             c[j++]=s[i];  
36             t=0;  
37         }  
38         else{  
39             if(t==0){  
40                 c[j++]=' ';  
41                 t=1;  
42             }  
43             if(top==NULL||s[i]=='('||(s[i]!=')'&&yxj(s[i],top->s)))  
44                 push(&top,s[i]);  
45             else{  
46                 if(s[i]==')'){  
47                     while(top->s!='('){  
48                         c[j++]=top->s;  
49                         pop(&top);  
50                     }  
51                     pop(&top);  
52                 }  
53                 else{  
54                     while(top!=NULL&&(!yxj(s[i],top->s))){  
55                         c[j++]=top->s;  
56                         pop(&top);  
57                     }  
58                     push(&top,s[i]);  
59                 }  
60             }  
61         }  
62     }  
63     if(t==0)  
64         c[j++]=' ';  
65     while(top!=NULL){  
66         c[j++]=top->s;  
67         pop(&top);  
68     }  
69     c[j]=0;  
70     j=0;  
71     for(i=0;c[i]!='';i++){  
72         if(c[i]>='0'&&c[i]<='9'){  
73             t=0;  
74             for(;c[i]!=' ';i++)  
75                 t=t*10+c[i]-48;  
76             m[j++]=t;  
77         }  
78         else{  
79             if(c[i]=='+')  
80                 m[j-2]=m[j-2]+m[j-1];  
81             else if(c[i]=='-')  
82                 m[j-2]=m[j-2]-m[j-1];  
83             else if(c[i]=='*')  
84                 m[j-2]=m[j-2]*m[j-1];  
85             else if(c[i]=='/')  
86                 m[j-2]=m[j-2]/m[j-1];  
87             j--;  
88         }  
89     }  
90     printf("%d
",m[0]);  
91     return 0;  
92 }

View Code