本题中,我使用了我写单链表/双链表两题留下的格式来存储数据,即用数组存储内容和上一个、下一个的位置。在这过程中遇到了这些问题:
1. 数组位置不够。题目中指出最大的数据有10^5个字符,意味着我定义的数组几乎刚好用完。计算过程中,对于每个运算符,它和它左、右边的两个数字运算完毕,如果直接废除把运算结果往后面存,怕114514个不够它用。于是我改成了每次运算中,运算符左侧将成为结果的储存位置,不流失,不蒸发,零浪费。
2. 运算先后关系。代码写完提交运行出现Floating Point Exception,查半天发现是运算过程中出现了/0,导致程序直接寄了。但又怎么会给出/0的数据呢? 后面我发现由于我的第一版代码是以乘除->加减->去除多余小括号(如把(114)变为114)的顺序运算的。在乘除、加减中,如果遇到运算符左、右边有一边是括号时会跳过这里等下一轮,导致某一个数据中,它是这么算的: (3-2+2)/3*2/2/2/3 = (3-2+2)/6/2/2/3 = (3-2+2)/3/2/3 = (3-2+2)/1/3 = (3-2+2)/0 = 3/0,然后就寄了。而且还有一个致命点:没有遵守同级从左往右算。如果不是这个我还发现不了。解:既然整除按不同顺序会出现多解,按数学运算规则,每次只算最高级小括号内的东西,算出来后就可以消掉一层,然后就能正常算了。
编写耗时: ~100min
运行耗时: 1024ms
n=输入长度,m=小括号最高层数
复杂度: O((4m+1)n) = O(n)~O(n^2) (谁知道有没有可能基本全是小括号呢)
上代码。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int EMPTY=-2147483600;
const int ADD=-2147483648,SUB=-2147483647,MUL=-2147483646,DIV=-2147483645;
const int LP=-2147483644,RP=-2147483643;
string str;
int a[114514],prv[114514],nxt[114514],p=0,head=0,tail=0;
int type(char ch){
if (ch>='0' and ch<='9') return 0;
if (ch=='+') return ADD;
if (ch=='-') return SUB;
if (ch=='*') return MUL;
if (ch=='/') return DIV;
if (ch=='(') return LP;
if (ch==')') return RP;
return EMPTY;
}
/*void print(){
int n=head;
while (true){
if (a[n]==ADD) cout<<"+";
else if (a[n]==SUB) cout<<"-";
else if (a[n]==MUL) cout<<"*";
else if (a[n]==DIV) cout<<"/";
else if (a[n]==LP) cout<<"(";
else if (a[n]==RP) cout<<")";
else if (a[n]==EMPTY) cout<<"EMPTY";
else if (a[n]<0) cout<<"["<<a[n]<<"]";
else cout<<a[n];
if (n==tail) break;
n=nxt[n];
}
cout<<endl;
}
string fhtostr(int x){
if (x==ADD) return "+";
else if (x==SUB) return "-";
else if (x==MUL) return "*";
else if (x==DIV) return "/";
else if (x==LP) return "(";
else if (x==RP) return ")";
else if (x==EMPTY) return " EMPTY ";
return " NUMBER ";
}*/
bool isNum(int x){
if (x==EMPTY) return false;
if (x==ADD) return false;
if (x==SUB) return false;
if (x==MUL) return false;
if (x==DIV) return false;
if (x==LP) return false;
if (x==RP) return false;
return true;
}
void dealWithMulDiv(int h){
int th=0;
int n=head;
while (true){
if (a[n]==LP) th++;
if (a[n]==RP) th--;
if ((a[n]==MUL or a[n]==DIV) and th==h){
int t0=prv[n],t1=nxt[n];
if (isNum(a[t0]) and isNum(a[t1])){
//cout<<a[t0]<<fhtostr(a[n])<<a[t1]<<endl;
int b;
if (a[n]==MUL) b=a[t0]*a[t1];
else b=a[t0]/a[t1];
a[n]=EMPTY;
a[t1]=EMPTY;
a[t0]=b;
//t0, n, t1, (t2)
if (tail==t1){
nxt[t0]=0;
prv[n]=0;
nxt[n]=0;
prv[t1]=0;
nxt[t1]=0;
tail=t0;
n=t0;
}
else{
int t2=nxt[t1];
nxt[t0]=t2;
prv[t2]=t0;
nxt[n]=0;
prv[n]=0;
nxt[t1]=0;
prv[t1]=0;
n=t0;
}
}
}
if (n==tail) break;
n=nxt[n];
}
}
void dealWithAddSub(int h){
int th=0;
int n=head;
while (true){
if (a[n]==LP) th++;
if (a[n]==RP) th--;
if ((a[n]==ADD or a[n]==SUB) and (th==h)){
int t0=prv[n],t1=nxt[n];
if (isNum(a[t0]) and isNum(a[t1])){
bool flag=true;
if (t1!=tail){
if (a[nxt[t1]]==MUL or a[nxt[t1]]==DIV) flag=false;
}
if (t0!=head){
if (a[prv[t0]]==MUL or a[prv[t0]]==DIV) flag=false;
}
if (flag){
int b;
if (a[n]==ADD) b=a[t0]+a[t1];
else b=a[t0]-a[t1];
a[n]=EMPTY;
a[t1]=EMPTY;
a[t0]=b;
//t0, n, t1, (t2)
if (tail==t1){
nxt[t0]=0;
prv[n]=0;
nxt[n]=0;
prv[t1]=0;
nxt[t1]=0;
tail=t0;
n=t0;
}
else{
int t2=nxt[t1];
nxt[t0]=t2;
prv[t2]=t0;
nxt[n]=0;
prv[n]=0;
nxt[t1]=0;
prv[t1]=0;
n=t0;
}
}
}
}
if (n==tail) break;
n=nxt[n];
}
}
void dealWithParentheses(){
int n=head;
while (true){
if (isNum(a[n])){
int t0=prv[n],t1=nxt[n];
if (a[t0]==LP and a[t1]==RP){
int b=a[n];
a[n]=EMPTY;
a[t1]=EMPTY;
a[t0]=b;
//t0, n, t1, (t2)
if (tail==t1){
nxt[t0]=0;
prv[n]=0;
nxt[n]=0;
prv[t1]=0;
nxt[t1]=0;
tail=t0;
n=t0;
}
else{
int t2=nxt[t1];
nxt[t0]=t2;
prv[t2]=t0;
nxt[n]=0;
prv[n]=0;
nxt[t1]=0;
prv[t1]=0;
n=t0;
}
}
}
if (n==tail) break;
n=nxt[n];
}
}
int main(){
cin>>str;
int temp=EMPTY;
for (int i=0; i<str.length(); i++){
if (type(str[i])==EMPTY) continue;
if (type(str[i])==0){
if (temp==EMPTY) temp=0;
temp=temp*10+int(str[i]-'0');
}
else{
if (temp!=EMPTY){
p++;
a[p]=temp;
if (head==0){
head=p;
tail=p;
prv[p]=0;
nxt[p]=0;
}
else{
prv[p]=tail;
nxt[tail]=p;
tail=p;
}
temp=EMPTY;
}
p++;
a[p]=type(str[i]);
if (head==0){
head=p;
tail=p;
prv[p]=0;
nxt[p]=0;
}
else{
prv[p]=tail;
nxt[tail]=p;
tail=p;
}
}
}
if (temp!=EMPTY){
p++;
a[p]=temp;
if (head==0){
head=p;
tail=p;
prv[p]=0;
nxt[p]=0;
}
else{
prv[p]=tail;
nxt[tail]=p;
tail=p;
}
temp=EMPTY;
}
int lst=-1,pos;
do{
int h=0,th=0,n=head;
while (true){
if (a[n]==LP) th++;
if (a[n]==RP) th--;
if (th>h){
pos=n;
h=th;
}
if (n==tail) break;
n=nxt[n];
}
dealWithMulDiv(h);
dealWithAddSub(h);
dealWithParentheses();
}
while (head!=tail);
cout<<a[1]<<endl;
return 0;
}