题解 P1797 【克鲁斯的加减法_NOI导刊2010提高（05）】
这可能是最长的一片题解，但思路应该是很清晰的 首先这道题可以模拟或者重载 因为重载看着太丑了，我选择了模拟大法 首先思路如下 考虑这串字符可能有几种形式
- +++++数字
- +（数字）数字
- +数字
- 只有数字
- ----数字
- -（数字）数字
- -数字
因为要考虑正负号所以不能直接加或减 正加正直接加；正加负变成正减正；负加负，改为正加正，标记不变；负减负变成正减负； 但如果每次操作都考虑正负号会非常的繁琐 所以我们用两个数组 一个记录加的操作的总和 一个记录减的操作的总和 这样只需要在输出答案的时候判断一下正负号即可 另外还有读入时数是从高位开始存的 所以每次读入后我们都翻转一下数组 让最低位在数组开始的位置 这样进位的操作会很好实现 还要处理好两个答案数组的长度
接下来就放出我的巨长的代码 ————————>
# include <iostream>
# include <string>
# include <cstring>
# include <algorithm>
# include <cstdio>
# define ll long long
using namespace std;
char s[1000100];
int len,tot,ans_l = 1,cnt,ans_r = 1,ans_len;
int st[1000100],a[1000100],ans1[1000100],que[1000000],mu[1000100],ans2[1000100],ans[1000100];
void change(){
for (int i = 1 ; i <= tot; i ++) a[i] = st[i];
for (int i = 1 ; i <= tot ; i++) st[i] = a[tot-i+1];
}
void tchange(){
for (int i = 1 ; i <= cnt ; i++) a[i] = que[i];
for (int i= 1 ; i <= cnt ; i++) que[i] = a[cnt-i+1];
}
void mul(int sum){
int jin = 0;
for (int i = 1 ; i <= tot ;i++){
st[i] = st[i] * sum + jin;
jin = st[i] / 10;
st[i] %= 10;
}
if(jin){tot++; st[tot] += jin;}
}
void add(){
int r = max(ans_l,tot); int jin = 0;
for (int i = 1 ; i <= r ; i++){
ans1[i] = ans1[i] + st[i] + jin;
jin = ans1[i] / 10;
ans1[i] %= 10;
}
ans_l = r;
while(ans1[ans_l] == 0) ans_l--;
}
void Add(){
int r = max(ans_r,tot); int jin = 0;
for (int i = 1 ; i <= r ; i++){
ans2[i] = ans2[i] + st[i] + jin;
jin = ans2[i] / 10;
ans2[i] %= 10;
}
ans_r = r;
while(ans2[ans_r] == 0) ans_r--;
}
void Mmul(){
memset(mu,0,sizeof(mu));
int jin = 0; int lenn = 1;
for (int i = 1 ; i <= tot ; i++){
for (int j = 1 ; j <= cnt ; j++){
mu[i+j-1] += st[i] * que[j];
mu[i+j] += mu[i+j-1] / 10;
mu[i+j-1] %= 10;
}
}
lenn = tot+cnt;
while(mu[lenn] == 0) lenn--;
memset(st,0,sizeof(st));
for (int i = 1 ; i <= lenn ; i++) st[i] = mu[i];
tot = lenn;
}
void jian1(){
int r = max(ans_l,ans_r); int jin = 0;
for (int i = 1 ; i <= r ; i++){
ans[i] = ans2[i] - ans1[i];
if(ans[i] < 0) ans[i] += 10,ans2[i+1] -= 1;
}
while(ans[r] == 0) r--;
ans_len = r;
}
void jian2(){
int r = max(ans_l,ans_r); int jin = 0;
for (int i = 1 ; i <= r ; i++){
ans[i] = ans1[i] - ans2[i];
if(ans[i] < 0) ans[i] += 10, ans1[i+1] -= 1;
}
while(ans[r] == 0) r--;
ans_len = r;
}
bool check(){
if(ans_l < ans_r) return 1;
if(ans_l > ans_r) return 0;
if(ans_l == ans_r){
for (int i = ans_l ; i >= 1 ; i--){
if(ans1[i] < ans2[i]) return 1;
if(ans1[i] > ans2[i]) return 0;
if(ans1[i] == ans2[i]) continue;
}
}
return 0;
}
int main(){
cin >> s+1;
len = strlen(s+1) ;
for (int i = 1 ; i <= len ; i++){
if(s[i] == '+' && s[i+1] == '+'){
memset(st,0,sizeof(st));
int x = i; cnt = 0; tot = 0;
while(s[x] <'0' || s[x] >'9') x++,cnt++;
while(s[x] >= '0' && s[x] <= '9') st[++tot] = s[x++] - '0';
change(); mul(cnt); add();
i = x - 1; continue;
}
if(s[i] == '+' && s[i+1] == '('){
memset(st,0,sizeof(st)); memset(que,0,sizeof(que));
int x = i + 2; tot = 0; cnt = 0;
while(s[x] >='0' && s[x] <='9') que[++cnt] = s[x++] - '0';
tchange();
if(s[x] == ')'){
x ++;
while(s[x] >='0' && s[x] <='9') st[++tot] = s[x++] - '0';
change();
}
Mmul(); add();
i = x - 1;
continue; }
if(s[i] == '+'){
if(s[i+1] >= '0' && s[i+1] <= '9'){
memset(st,0,sizeof(st));
int x = i + 1; tot = 0;
while(s[x] >= '0' && s[x] <= '9') st[++tot] = s[x++] - '0';
change(); add();
i = x - 1; continue;
}
}
if(s[i] >= '0' && s[i] <= '9'){
memset(st,0,sizeof(st));
int x= i; tot = 0;
while(s[x] >= '0' && s[x] <= '9' ) st[++tot] = s[x++] - '0';
change(); add();
i = x - 1;
continue;
}
if(s[i] == '-' && s[i+1] == '-'){
memset(st,0,sizeof(st));
int x = i; cnt = 0; tot = 0;
while(s[x] <'0' || s[x] >'9') x++,cnt++;
while(s[x] >= '0' && s[x] <= '9') st[++tot] = s[x++] - '0';
change(); mul(cnt); Add();
i = x - 1;
continue;
}
if(s[i] == '-' && s[i+1] == '('){
memset(st,0,sizeof(st)); memset(que,0,sizeof(que));
int x = i + 2; tot = 0; cnt = 0;
while(s[x] >='0' && s[x] <='9') que[++cnt] = s[x++] - '0'; tchange();
if(s[x] == ')'){
x ++;
while(s[x] >='0' && s[x] <='9') st[++tot] = s[x++] - '0';
change();
}
Mmul(); Add();
i = x - 1; continue;
}
if(s[i] == '-'){
if(s[i+1] >= '0' && s[i+1] <= '9'){
memset(st,0,sizeof(st));
int x = i + 1; tot = 0;
while(s[x] >= '0' && s[x] <= '9') st[++tot] = s[x++] - '0';
change(); Add();
i = x - 1; continue;
}
}
}
if(check()){ cout<<"-"; jian1();}
else jian2();
for (int i = ans_len ; i >= 1 ; i --) cout<<ans[i];
if(ans_len <= 0) cout<<0<<endl;
return 0;
}
/*
+(255)10---3-(23)100
*/