第三题
题目描述
今日头条6周年庆就要开始了. 活动主办方请你帮忙制作一个小彩蛋. 你的程序需要读取一个表达式,并输出用字符’6’拼出的计算结果. 相邻数字使用两个英文句号’.’间隔.
输入描述
第一行为一个整数n
接下来的n行,每行为一个表达式, 表达式仅包含’6’,’+’,’-‘,’*’四种字符. 1<=n<=100,表达式长度不超过100.中间计算结果在[-2^63~2^63-1]的范围内,最终结果在[0,2^-63-1]范围内.
输出描述:
对于每组数据,输出用字符’6’拼出的计算结果.
解法
个人觉得这个要分为两步.
第一步是表达式解析. 我觉得采用将中缀表达式转化为后缀表达式的办法是可以的.
第二步是将数字用’6’和’.’显示出来.主要是表达式的拼接.
备注
这个我写的,不保证正确,也不保证是好的答案.只是能实现功能.我觉得这个题太难了.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
| #include <iostream>
#include <vector>
#include <deque>
#include <stack>
#include <cmath>
using namespace std;
void number_init();
vector<vector<string>> number;
int compute_string(string s);
void print_num(int num)
{
deque<int> number_queue;
do{
number_queue.push_back(num % 10);
num /= 10;
}while(num != 0);
vector<string> result = number[number_queue.back()];
number_queue.pop_back();
while(!number_queue.empty())
{
int temp_num = number_queue.back();
number_queue.pop_back();
for(int i =0; i < 5; i++)
{
result[i] += (number[10][i] + number[temp_num][i]);
}
}
cout << result[0];
for(int i = 1; i < 5; i++)
{
cout << endl << result[i];
}
}
int compute_string(string s)
{
int result;
deque<string> postfix;
string substr;
stack<char> oper;
int n = s.size();
if(n == 0)
return -1;
int i = 0;
while(s[i] != '\0')
{
switch(s[i])
{
case '6':
substr += "6";
break;
case '+':
case '-':
if(!substr.empty())
{
postfix.push_back(substr);
substr = "";
}
while(!oper.empty())
{
substr += oper.top();
postfix.push_back(substr);
oper.pop();
substr = "";
}
oper.push(s[i]);
break;
case '*':
if(!substr.empty())
{
postfix.push_back(substr);
substr = "";
}
oper.push(s[i]);
break;
}
i += 1;
}
if(!substr.empty())
{
postfix.push_back(substr);
substr = "";
}
while(!oper.empty())
{
substr += oper.top();
postfix.push_back(substr);
oper.pop();
substr = "";
}
stack<int> num_stack;
num_stack.push(0);
while(!postfix.empty())
{
string temp;
temp = postfix.front();
postfix.pop_front();
if(temp != "+" && temp != "-" && temp != "*")
{
int num = 0;
int length = temp.size();
for(int j = 0; j < length; j++)
{
num += (temp[j] - '0') * pow(10, j);
}
num_stack.push(num);
}
else
{
int temp1, temp2;
temp1 = num_stack.top();
num_stack.pop();
temp2 = num_stack.top();
num_stack.pop();
if(temp == "+")
num_stack.push(temp1 + temp2);
if(temp == "-")
num_stack.push(temp2 - temp1);
if(temp == "*")
num_stack.push(temp1 * temp2);
}
}
result = num_stack.top();
return result;
}
int main() {
number_init();
int n;
cin >> n;
if(n <= 0)
return -1;
vector<string> temp_string_vector;
for(int i = 0; i < n; i++)
{
string temp_string;
temp_string_vector.push_back(temp_string);
cin >> temp_string_vector[i];
}
int temp_num = compute_string(temp_string_vector[0]);
print_num(temp_num);
for(int i = 1; i < n; i++ )
{
cout << endl;
temp_num = compute_string(temp_string_vector[i]);
print_num(temp_num);
}
return 0;
}
void number_init()
{
vector<string> zero;
number.push_back(zero);
number[0].emplace_back("66666");
number[0].emplace_back("6...6");
number[0].emplace_back("6...6");
number[0].emplace_back("6...6");
number[0].emplace_back("66666");
vector<string> one;
number.push_back(one);
number[1].emplace_back("....6");
number[1].emplace_back("....6");
number[1].emplace_back("....6");
number[1].emplace_back("....6");
number[1].emplace_back("....6");
vector<string> two;
number.push_back(two);
number[2].emplace_back("66666");
number[2].emplace_back("....6");
number[2].emplace_back("66666");
number[2].emplace_back("6....");
number[2].emplace_back("66666");
vector<string> three;
number.push_back(three);
number[3].emplace_back("66666");
number[3].emplace_back("....6");
number[3].emplace_back("66666");
number[3].emplace_back("....6");
number[3].emplace_back("66666");
vector<string> four;
number.push_back(four);
number[4].emplace_back("6...6");
number[4].emplace_back("6...6");
number[4].emplace_back("66666");
number[4].emplace_back("....6");
number[4].emplace_back("....6");
vector<string> five;
number.push_back(five);
number[5].emplace_back("66666");
number[5].emplace_back("6....");
number[5].emplace_back("66666");
number[5].emplace_back("....6");
number[5].emplace_back("66666");
vector<string> six;
number.push_back(six);
number[6].emplace_back("66666");
number[6].emplace_back("6....");
number[6].emplace_back("66666");
number[6].emplace_back("6...6");
number[6].emplace_back("66666");
vector<string> seven;
number.push_back(seven);
number[7].emplace_back("66666");
number[7].emplace_back("....6");
number[7].emplace_back("....6");
number[7].emplace_back("....6");
number[7].emplace_back("....6");
vector<string> eight;
number.push_back(eight);
number[8].emplace_back("66666");
number[8].emplace_back("6...6");
number[8].emplace_back("66666");
number[8].emplace_back("6...6");
number[8].emplace_back("66666");
vector<string> nine;
number.push_back(nine);
number[9].emplace_back("66666");
number[9].emplace_back("6...6");
number[9].emplace_back("66666");
number[9].emplace_back("....6");
number[9].emplace_back("66666");
vector<string> blank;
number.push_back(blank);
number[10].emplace_back("..");
number[10].emplace_back("..");
number[10].emplace_back("..");
number[10].emplace_back("..");
number[10].emplace_back("..");
}
|