YZOJ P3314 计算器
时间限制：1000MS 内存限制：524288KB
出题人：zzx
难度： \(3.6\)
-
题目描述
你打算设计一个简单的计算器，支持计算简单的表达式。
为了简单起见，所有运算涉及的数均为整数（可以是负数），运算包含 +（加）、 -（减）、 *（乘）三种。计算时，按照先乘后加减的顺序计算，同级运算从左到右进行。表达式中可能有括号，应先计算括号内的结果，括号可能有嵌套。
形式化地，表达式的格式如下：（不含 <、 >）
< 表达式 > ： < 运算数 1>< 运算符 1>< 运算数 2>< 运算符 2> \(\cdots\) < 运算符 \(k-1\)>< 运算数 \(k\)>（ \(k\) 为正整数）
其中，运算数可以是整数，也可以是 (< 表达式 >) 或 -(< 表达式 >) 的形式，即包含在括号内的表达式。运算符为 +、 -、 * 之一。保证任意两个 – 不相邻。
请你编写计算器的程序，计算给定的表达式的结果。
-
输入格式
输入包含一个字符串 s，表示待计算的表达式，保证表达式符合格式，没有空格。
-
输出格式
输出一个整数，表示计算结果。当计算结果不为 0 时，要求最高位非 0。
-
样例输入
|
1 |
(314+271*99)*(100-985*211)-(-6) |
-
样例输出
|
1 |
-5638551099 |
-
数据规模与约定
因为是水题，所以没有具体的数据范围
\(1 \leq \left| s \right| \leq 10^4\)
表达式计算的本来我已经写过两篇了，这里就不多说了。
丧题，想题2s，码题2h，调题2d，达成成就：人生中第一次写高精负数！（\(Bouns -999999999\cdots\cdots\)
|
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 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define SETDIG 4 #define SETDIGN 10000 //#define _swap(_a,_b) ((_a)^=(_b)^=(_a)^=(_b)) #define _abs(_a) ((_a)<0?-(_a):(_a)) struct _bnum { int num[155],len,sgn; _bnum(){memset(num,0,sizeof(num));len=0;sgn=1;} inline int numcmp(const _bnum&a,const _bnum&b) { if(a.len>b.len) return 1; else if(a.len<b.len) return -1; for(register int i=a.len-1;i>=0;i--) if(a.num[i]>b.num[i]) return 1; else if(a.num[i]<b.num[i]) return -1; return 1; } _bnum(const char ostr[]) { const char*str=ostr+(ostr[0]=='-'); memset(num,0,sizeof(num));len=0; register int ls=strlen(str)-1; for(;ls-SETDIG>=0;ls-=SETDIG,len++) for(register int j=ls-SETDIG+1;j<=ls;j++) (num[len]*=10)+=(str[j]-'0'); for(register int j=0;j<=ls;j++) (num[len]*=10)+=(str[j]-'0'); len++; if(ostr[0]=='-') sgn=-1; else sgn=1; } _bnum(register int n) { memset(num,0,sizeof(num));len=1; num[0]=_abs(n); while(num[len-1]>SETDIGN-1) num[len]=num[len-1]/SETDIGN,num[len-1]%=SETDIGN,len++; if(n<0) sgn=-1; else sgn=1; } _bnum operator = (const _bnum&ot) { sgn=ot.sgn,len=ot.len; memcpy(&num,&ot.num,sizeof(num)); return *this; } _bnum operator += (_bnum ot) { register int osign=sgn,otsign=ot.sgn; //this->PrintNum(),ot.PrintNum(); //printf("%d %d\n",osign,otsign); if(osign*otsign<0) if(osign>0) { ot.sgn=1; (*this)-=ot; ot.sgn=otsign; return *this; } else { _bnum ans=ot; sgn=1; *this=(ans-=(*this)); //sgn=osign; return *this; } sgn=osign; register int flen=len; if(ot.len>flen) flen=ot.len; for(register int i=0;i<flen;i++) { num[i]+=ot.num[i]; num[i+1]+=num[i]/SETDIGN,num[i]%=SETDIGN; } if(num[flen]) flen++; len=flen; while(num[len-1]>SETDIGN-1) num[len]=num[len-1]/SETDIGN,num[len-1]%=SETDIGN,len++; return *this; } _bnum operator *= (const _bnum&ot) { _bnum ans; register int flen=this->len+ot.len; for(register int i=0;i<this->len;i++) for(register int j=0;j<ot.len;j++) ans.num[i+j]+=this->num[i]*ot.num[j]; for(register int i=0;i<flen;i++) ans.num[i+1]+=ans.num[i]/SETDIGN,ans.num[i]%=SETDIGN; while(ans.num[flen]) ans.num[flen+1]=ans.num[flen+1]/SETDIGN,ans.num[flen++]%=SETDIGN; while(ans.num[flen-1]==0 && len>0) flen--; if(flen==0) flen=1; ans.len=flen; ans.sgn=sgn*ot.sgn; //ans.PrintNum(); return (*this=ans); } _bnum operator -= (_bnum ot) { register int osign=sgn,otsign=ot.sgn; //printf("%d %d\n",osign,otsign); //this->PrintNum();ot.PrintNum();printf("-------\n\n"); if(osign*otsign<0) { sgn=ot.sgn=1; (*this)+=ot; sgn=osign,ot.sgn=otsign; return *this; } if(osign<0) { _bnum ans=ot; sgn=ans.sgn=1; ans-=(*this); //ans.sgn*=-1; return (*this=ans); } if(ot.len>len) len=ot.len; sgn=numcmp(*this,ot); for(register int i=0;i<len;i++) { (num[i]-=ot.num[i])*=sgn; //printf("%d: %d\n",i,num[i]); while(num[i]<0) num[i+1]-=sgn,num[i]+=SETDIGN; } while(num[len-1]==0 && len>0) len--; if(len==0) len=1; while(num[len-1]>SETDIGN-1) num[len]=num[len-1]/SETDIGN,num[len-1]%=SETDIGN,len++; return *this; } inline void PrintNum()const { if(sgn<0) printf("-"); printf("%d",num[len-1]); static char ots[8]; sprintf(ots,"%%0%dd",SETDIG); for(register int i=len-2;i>=0;i--) printf(ots,(num[i]<0 ? -num[i] : num[i])); printf("\n"); } }; inline _bnum ExpressionNumber(char*&pos) { static char s[10505]; char*spos=&s[0]; if(*pos=='-') *spos='-',spos++,pos++; while(*pos>='0' && *pos<='9') { *spos=*pos; spos++,pos++; } *spos='\0'; if(*(spos-1)=='-') { pos--,*pos='*'; return (_bnum)-1; } return (_bnum)s; } inline _bnum ExpressionAddMinus(char*&pos); inline _bnum ExpressionBracket(char*&pos) { if(*pos=='(') { pos++; _bnum ret=ExpressionAddMinus(pos); pos++; return ret; } else return ExpressionNumber(pos); } inline _bnum ExpressionTimes(char*&pos) { _bnum ret=ExpressionBracket(pos); while(1) switch(*pos) { case '*': pos++; ret*=ExpressionBracket(pos); break; default: return ret; } return ret; } inline _bnum ExpressionAddMinus(char*&pos) { _bnum ret=ExpressionTimes(pos); while(1) switch(*pos) { case '+': pos++; ret+=ExpressionTimes(pos); break; case '-': pos++; ret-=ExpressionTimes(pos); break; default: return ret; } return ret; } inline _bnum ComputeAns(char s[]) { char*begin=&s[1]; return ExpressionAddMinus(begin); } char os[10505]; int los; inline void ReadString() { memset(os,0,sizeof(os)); os[1]='('; // 数据有锅 /*los=1; char c=getchar(); while(c=='\r' || c=='\n' || c==' ') c=getchar(); while(c!='\r' && c!='\n') { os[++los]=c; c=getchar(); while(c==' ' && c!='\r' && c!='\n') c=getchar(); }*/ scanf("%s",&os[2]); los=strlen(os+2)+1; os[++los]=')'; } int main() { ReadString();//printf("%d\n",strlen(os+1)); ComputeAns(os).PrintNum(); return 0; } |