LGOJ P1175 | 表达式的转换

Portal

很水的模拟题。先 stack 转后缀,不过似乎没有人用 list 去维护。本来可以跑得很快,但是一不小心优化过头是我的坏毛病,所以勉强忍住了。写法比较像 C++,是这次唯一的特点(笑)。用了几个很小的数代表运算符,很容易被 hack 吧。(满口 ZUN 语

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
#include <list>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
std::list<int> l;
std::stack<char> s;
int p[128],f[128];
int qpow(int a,int b) {
int res=1;
while(b) {if(b&1) res*=a; a*=a;b>>=1;}
return res;
}
char flect(int opt) {
if(opt==f['+']) return '+';
if(opt==f['-']) return '-';
if(opt==f['*']) return '*';
if(opt==f['/']) return '/';
if(opt==f['^']) return '^';
return 0;
}
int func(int a,int b,int opt) {
if(opt==f['+']) return a+b;
if(opt==f['-']) return a-b;
if(opt==f['*']) return a*b;
if(opt==f['/']) return a/b;
if(opt==f['^']) return qpow(a,b);
return -1;
}
void write(int x) {
if(x>f['^']) std::cout<<x;
else std::cout<<flect(x);
std::cout<<' ';
}
void suffix(const std::string& str) {
for(int i=0;i<str.size();++i)
if(str[i]>47&&str[i]<58) l.push_back(str[i]-48);
else {
if(str[i]!='(') while(s.size()&&p[s.top()]>=p[str[i]])
l.push_back(f[s.top()]),s.pop();
if(str[i]==')') s.pop(); else s.push(str[i]);
}
while(s.size()) l.push_back(f[s.top()]),s.pop();
}
void calc() {
int opt,t;
std::list<int>::iterator fp=l.begin();
while(fp!=l.end()) {
if(*fp<=f['^']) {
opt=*fp;t=*--fp;--fp;
*fp=func(*fp,t,opt);
fp=l.erase(++fp);fp=l.erase(fp);
std::for_each(l.begin(),l.end(),write);
std::cout<<"\n";
}
else ++fp;
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
p['(']=1;p[')']=2;
p['+']=p['-']=3;
p['*']=p['/']=4;
p['^']=5;
f['+']=0x80000000;
f['-']=f['+']+1;
f['*']=f['-']+1;
f['/']=f['*']+1;
f['^']=f['/']+1;
std::string str;
std::cin>>str;
suffix(str);
std::for_each(l.begin(),l.end(),write);std::cout<<"\n";
calc();
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。