《数据结构和算法》——逆波兰表达式

luciferzf

对于所求的中缀表达式，我们首先需要将其转换为后缀表达式，即将运算符写在作用的两个数的后面，然后将中缀表达式的输出作为后缀表达式计算程序的输入。
在一个中缀表达式，我们首先需要用栈来储存级别较高的运算符，如*，（等。在栈中只允许级别较高的运算符在级别较低的运算符上面，所以当读取到级别最低级别最低的“+”和“-”时就将栈中的运算符弹出至“（”或栈为空，“（”可以在任何运算符下面，一旦检测到“）”立刻将栈中的运算符弹出，至“（”的位置。当检测到“*”和“/”时则压入栈中。当输入完毕后将栈中所有符号弹出。


附上计算中缀表达式的算法：

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<math.h>
   
4. #include<iostream>
   
5. using namespace std;
   
6. 
   
7. typedef double elem;
   
8. 
   
9. class stack1
   
10. {
    
11. public:
    
12.         elem *top, *base;
    
13.         int stack_size;
    
14. };
    
15. 
    
16. class stack2
    
17. {
    
18. public:
    
19.         char *top, *base;
    
20.         int stack_size;
    
21. };
    
22. 
    
23. void Initial(stack1 *s)
    
24. {
    
25.         s->base = new elem[1000];
    
26.         s->top = s->base;
    
27.         s->stack_size = 0;
    
28. }
    
29. void Initial(stack2 *s)
    
30. {
    
31.         s->base = new char[1000];
    
32.         s->top = s->base;
    
33.         s->stack_size = 0;
    
34. }
    
35. 
    
36. 
    
37. void Push(stack1 *s,elem e)
    
38. {
    
39.         *(s->base) = e;
    
40.         s->base++;
    
41.         s->stack_size++;
    
42. }
    
43. void Push(stack2 *s, char e)
    
44. {
    
45.         *(s->base) = e;
    
46.         s->base++;
    
47.         s->stack_size++;
    
48. }
    
49. 
    
50. void Pop(stack1 *s,double *e)
    
51. {
    
52.         s->stack_size--;
    
53.         s->base--;
    
54.         *e = *(s->base);
    
55. }
    
56. void Pop(stack2 *s,char *e)
    
57. {
    
58.         s->base--;
    
59.         s->stack_size--;
    
60.         *e = *(s->base);
    
61. }
    
62. 
    
63. 
    
64. int main()
    
65. {
    
66.         stack1 s;
    
67.         stack2 r;
    
68.         char c;
    
69.         char str[20];
    
70.         elem d;
    
71.         Initial(&s);
    
72.         Initial(&r);
    
73. 
    
74.         printf("输入要计算的中缀表达式(以#结束，数字与符号之间用空格隔开)：");
    
75.         scanf_s("%c", &c);
    
76. 
    
77.         while (c!= '#')
    
78.         {
    
79.                 int i = 0;
    
80.                 while (isdigit(c) || c == '.')
    
81.                 {
    
82.                         str[i++] = c;
    
83.                         str[i] = 0;
    
84.                         scanf_s("%c", &c);
    
85.                         if (i >= 20)printf("wrong,out of the limit!");
    
86.                         if (c == ' ')
    
87.                         {
    
88.                                 d = atof(str);
    
89.                                 Push(&s, d);
    
90.                         }
    
91.                 }
    
92.                 if (')' == c)
    
93.                 {
    
94.                         char e;
    
95.                         do
    
96.                         {
    
97.                                 Pop(&r, &e);
    
98.                                 double a, b;
    
99.                                 switch (e)
    
100.                                 {
     
101.                                 case '+':
     
102.                                         Pop(&s,&b);
     
103.                                         Pop(&s,&a);
     
104.                                         Push(&s, a + b);
     
105.                                         break;
     
106.                                 case '-':
     
107.                                         Pop(&s, &b);
     
108.                                         Pop(&s, &a);
     
109.                                         Push(&s, a - b);
     
110.                                         break;
     
111.                                 case '*':
     
112.                                         Pop(&s, &b);
     
113.                                         Pop(&s, &a);
     
114.                                         Push(&s, a * b);
     
115.                                         break;
     
116.                                 case '/':
     
117.                                         Pop(&s, &b);
     
118.                                         Pop(&s, &a);
     
119.                                         Push(&s, a / b);
     
120.                                         break;
     
121.                                 }
     
122.                         } while (r.stack_size&&'(' != e);
     
123.                 }
     
124.                 else if (c == '+' || c == '-')
     
125.                 {
     
126.                         if (r.stack_size != 0)
     
127.                         {
     
128.                                 char e;
     
129.                                 do
     
130.                                 {
     
131.                                         Pop(&r, &e);
     
132.                                         if ('(' == e)
     
133.                                         {
     
134.                                                 Push(&r, e);
     
135.                                                 break;
     
136.                                         }
     
137.                                         double a, b;
     
138.                                         switch (e)
     
139.                                         {
     
140.                                         case '+':
     
141.                                                 Pop(&s, &b);
     
142.                                                 Pop(&s, &a);
     
143.                                                 Push(&s, a + b);
     
144.                                                 break;
     
145.                                         case '-':
     
146.                                                 Pop(&s, &b);
     
147.                                                 Pop(&s, &a);
     
148.                                                 Push(&s, a - b);
     
149.                                                 break;
     
150.                                         case '*':
     
151.                                                 Pop(&s, &b);
     
152.                                                 Pop(&s, &a);
     
153.                                                 Push(&s, a * b);
     
154.                                                 break;
     
155.                                         case '/':
     
156.                                                 Pop(&s, &b);
     
157.                                                 Pop(&s, &a);
     
158.                                                 Push(&s, a / b);
     
159.                                                 break;
     
160.                                         }
     
161.                                 } while (r.stack_size != 0 && e != '(');
     
162.                                 Push(&r, c);
     
163.                         }
     
164.                         else if (r.stack_size == 0)
     
165.                         {
     
166.                                 Push(&r, c);
     
167.                         }
     
168.                 }
     
169.                 else if ('*' == c || '/' == c||'('==c)
     
170.                 {
     
171.                         Push(&r, c);
     
172.                 }
     
173.                 scanf_s("%c", &c);
     
174.         }
     
175.         while (r.stack_size != 0)
     
176.         {
     
177.                 char e;
     
178.                 double a, b;
     
179.                 Pop(&r, &e);
     
180.                 switch (e)
     
181.                 {
     
182.                 case '+':
     
183.                         Pop(&s, &b);
     
184.                         Pop(&s, &a);
     
185.                         Push(&s, a + b);
     
186.                         break;
     
187.                 case '-':
     
188.                         Pop(&s, &b);
     
189.                         Pop(&s, &a);
     
190.                         Push(&s, a - b);
     
191.                         break;
     
192.                 case '*':
     
193.                         Pop(&s, &b);
     
194.                         Pop(&s, &a);
     
195.                         Push(&s, a * b);
     
196.                         break;
     
197.                 case '/':
     
198.                         Pop(&s, &b);
     
199.                         Pop(&s, &a);
     
200.                         Push(&s, a / b);
     
201.                         break;
     
202.                 }
     
203.         }
     
204.         Pop(&s,&d);
     
205.         printf("answer is %.2f\n", d);
     
206.         system("PAUSE");
     
207. }

复制代码