今天刷刷我們學校的OJ。看到了那道我們大家都熟悉的表達式求值題目。去網上搜了下，發現沒有現成可用的好的算法。于是自己花了點時間寫了個。沒有做過多優化，先發出來再說。
1
#include<stdio.h>
2#include<string.h>
3#include<stack>
4using namespace std;
5
6char exp[1100];
7char num[100];//此數組用來把字符數字轉化為整數
8
9stack<char> cstack;
10stack<double> nstack;
11
12int n;
13
14int convert(int length)
15
{
16
int value = 0;
17 for(int i = 0;i < length;++i)
18
{
19 value = value * 10 + num[i]-'0';
20
}
21 return value;
22
}
23
24//判斷a運算符比b優先。如果是的話，那么返回1如果不是的話，返回0
25int order(char a ,char b)
26{
27 if(a == '*' || a == '/')
28 {
29 return 1;
30 }
31 if(a == '+' || a == '-')
32 {
33 if(b == '*' || b== '/')
34 return 0;
35 else
36 return 1;
37 }
38 return 0;
39}
40
41//這個函數用來判斷字符是數字還是運算符
42
43int judge(char c)
44{
45 if(c <= '9' && c >= '0')
46 return 1;
47 else
48 return 0;
49}
50
51
52double go(char c,double n1,double n2)
53{
54 if(c == '+')
55 return n1 + n2;
56 else
57 if(c == '-')
58 return n1 - n2;
59 else
60 if(c == '*')
61 return n1 * n2;
62 else
63 if(c == '/')
64 return n1 / n2;
65 return 0;
66}
67
68int ignoreKuohao(stack<char> &ccstack,stack<double>& nnstack)
69{
70 while(!ccstack.empty() && ccstack.top()!='(')
71 {
72 char c1 = ccstack.top(); ccstack.pop();
73 double n1 = nnstack.top(); nnstack.pop();
74 double n2 = nnstack.top(); nnstack.pop();
75 if(ccstack.empty())
76 {
77 nnstack.push(go(c1,n1,n2));
78 break;
79 }
80 else
81 {
82 char c2 = ccstack.top(); ccstack.pop();
83 if(order(c1,c2))
84 {
85 double k = go(c1,n1,n2);
86 ccstack.push(c2);
87 nnstack.push(k);
88 }
89 else
90 {
91 //nnstack.push(n1);
92 double n3 = nnstack.top();nnstack.pop();
93 double k = go(c2,n2,n3);
94 nnstack.push(k);
95
96 k = nnstack.top();
97 nnstack.push(n1);
98
99 k = nnstack.top();
100 ccstack.push(c1);
101 }
102 }
103 }
104 if(!ccstack.empty() && ccstack.top() == '(')
105 {
106 ccstack.pop();
107 }
108
109 return 0;
110}
111
112
113
114//事實證明，在沒有括號的情況下，應該從前往后進行計算
115void inKuohao()
116{
117 char c = cstack.top();
118 stack<char> ccstack;
119 stack<double> nnstack;
120 //把括號內的表達式逆過來
121 int n = nstack.top();
122 nnstack.push(n);
123 nstack.pop();
124 while(c != '(')
125 {
126 cstack.pop();
127 ccstack.push(c);
128
129 nnstack.push(nstack.top());
130 nstack.pop();
131 if(cstack.empty())
132 break;
133 c = cstack.top();
134 }
135 if(!cstack.empty())
136 {
137 cstack.pop();
138 }
139 ignoreKuohao(ccstack,nnstack);
140 nstack.push(nnstack.top());
141 nnstack.pop();
142}
143
144int calc(int j)
145{
146 int i = 0;
147 int length = 0;
148// stack<char> cstack;
149// stack<int> nstack;
150 for(i = 0;i <= j ;++i )
151 {
152 if(judge(exp[i]))
153 {
154 num[length ++ ] = exp[i];
155 }
156 else
157 {
158 if(judge(exp[ i - 1]))//如果上一個是數字的話，就入棧.這個判斷是為了防止出現(2 + 1 )/2。這種情況
159 {
160 int k = convert(length);
161 nstack.push(k);
162 length = 0;
163 }
164 if(exp[i] == ')')
165 {
166 inKuohao();
167 }
168 else
169 if(exp[i] == '#')
170 break;
171 else
172 cstack.push(exp[i]);
173 }
174 }
175 if(!cstack.empty())
176 {
177 inKuohao();
178 }
179 int k =(int) nstack.top();
180 printf("%d\n",k);
181 return k;
182}
183
184int main()
185{
186 scanf("%s",exp);
187 int j = strlen(exp);
188 exp[j] = '#';
189 exp[j + 1] = '\0';
190 calc(j);
191 return 0;
192}
193
posted on 2011-04-24 21:00
崔佳星 閱讀(281)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構和算法