1. 全栈程序员必看首页

templete_表达式树

全栈程序员-站长 • • 未分类 • 阅读 1

templete_表达式树include include include include include 这个问题是我独自想清楚的 当然也是看了别人的思想 其实只要自己动脑筋 其实许多问题都是可以解决的 下一步需要解决的就是大于 10 位数的 四则运算 这个运算只能解决一位数的四则运算还是比较不方便的 一会就得自己学着解决大数问题的四则运算 usingnamespa

#include 
  
    #include 
   
     #include 
    
      #include 
      #include 
      
        /* *这个问题是我独自想清楚的，(当然也是看了别人的思想)其实只要自己动脑筋，其实许多问题都是可以解决的，下一步需要解决的就是大于10位数的 *四则运算，这个运算只能解决一位数的四则运算还是比较不方便的。一会就得自己学着解决大数问题的四则运算。 */ using namespace std; const int MAXN = 1000; const int MAXLEN = 100 + 11; const int cps = 10000; int lch[MAXN]; int rch[MAXN]; char op[MAXN]; int nc; map 
       
         M; struct bigint { int len; //大数的长度 int num[MAXLEN]; //大数所能计算的最大长度 void init(); //如果用默认的构造方法的话，就默认把所有的数字都置成0，len = 1； void init(char *s); //如果用字符串来构造bigint的话，就直接把char数组转成int数组了 void print(); //打印出此bigint void fixlen(); operator int*() { return num; } }; void bigint::init() { len = 1; memset(num, 0, sizeof(num)); } void bigint::init(char *s) //此bigint采用的是4位作为一个单位存入一位数组当中。 { int l = strlen(s); len = 0; memset(num, 0, sizeof(num)); for(int i = l - 1; i >= 0; ) { if(i >= 0)num[len] += (s[i--] - '0'); if(i >= 0)num[len] += (s[i--] - '0') * 10; if(i >= 0)num[len] += (s[i--] - '0') * 100; if(i >= 0)num[len] += (s[i--] - '0') * 1000; len++; } if(!len) len = 1; } void bigint::print() { printf("%d", num[len - 1]); for(int i = len - 1; i ;i--) printf("%04d",num[i - 1]); } void bigint::fixlen() { len = MAXLEN; while(num[len - 1] == 0 && (len - 1) ) len--; } bigint operator + (bigint x,int y) { int i=0; x[i] += y; while(x[i] >= cps) { x[i+1] += x[i] / cps; x[i] %= cps; } x.fixlen(); return x; } bigint operator+(bigint x,bigint y) { int l=max(x.len, y.len),t = 0; for(int i = 0; i < l; i++) { x[i] += y[i] + t; t = x[i] / cps; x[i] %= cps; } while(t) { x[l++] = t % cps; t /= cps; } x.len = l; return x; } bigint operator -(bigint x,int y) { int l = x.len,t; x[0] -= y; for(int i = 0;i < l;i++) if(x[i] < 0) { t = (-x[i])/ cps + 1; x[i] += cps * t; x[i+1] -= t; } x.fixlen(); return x; } bigint operator - (bigint x,bigint y) { int l = x.len; for(int i = 0; i < l; i++) { x[i] -= y[i]; if(x[i] < 0) { x[i] += cps; x[i+1]--; } } x.fixlen(); return x; } bigint operator * (bigint x,int y) { int t = 0,p = x.len; for(int i = 0; i < p; i++) { x[i] = x[i]*y + t; t = x[i] / cps; x[i] %= cps; } while(t) { x[p++] = t % cps; t /= cps; } x.fixlen(); return x; } bigint operator*(bigint x,bigint y) { int lx = x.len,ly = y.len,t; bigint ans; ans.init(); for(int i = 0; i < lx; i++) for(int j = 0; j < ly; j++) { t=i+j; ans[t] += x[i]*y[j]; while(ans[t] >= cps) { ans[t+1] += ans[t] / cps; ans[t] %= cps; } } ans.fixlen(); return ans; } bigint operator/(bigint x,int y) { int i,t=0,p=x.len; for(i=p-1;i>=0;i--) { t=t*cps+x[i]; x[i]=t/y; t%=y; } x.fixlen(); // return t;//mod return x; } bool operator <= (bigint x,bigint y) { if(x.len != y.len)return x.len < y.len; for(int i = x.len-1; i >= 0; i--) if(x[i] != y[i])return x[i] < y[i]; return 1; } bigint operator / (bigint x,bigint y) { int lx = x.len,ly = y.len; bigint p; p.init(); for(int i = lx-1; i >= 0; i--) { p = p*cps + x[i]; x[i] = 0; for(int j = 13;j >= 0; j--) if(y * (1< 
        
          = '9' || s[i] <= '0') { cnt++; } temp[t++] = s[i]; switch (s[i]) { case '(' : p++; break; case ')' : p--; break; case '+' : case '-' : if (!p) c1 = i; break; //c1表示最右边的+ -的标号， case '*' : case '/' : if (!p) c2 = i; break; //c2表示最右边的* /的标号。 } } temp[t] = '\0'; if (cnt == 0) { int u = nc++; lch[u] = 0; rch[u] = 0; op[u] = s[x]; M[u] = temp; return u; } if (c1 < 0) //如果右边没有+ -的话，那就得取* /; { c1 = c2; } if (c1 < 0) //如果也没有* /的话，而且并不是一个简单的数字，那就说明肯定有括号。 { return buildTree(s, x + 1, y - 1); } int u = nc++; lch[u] = buildTree(s, x, c1 - 1); rch[u] = buildTree(s, c1 + 1, y); op[u] = s[c1]; return u; } void init() { nc = 0; } bigint BFS(int root) // BFS求解BFS的结果（仔细想，问题非常的奇妙） { switch (op[root]) { case '+' : return BFS(lch[root]) + BFS(rch[root]); break; case '-' : return BFS(lch[root]) - BFS(rch[root]); break; case '*' : return BFS(lch[root]) * BFS(rch[root]); break; case '/' : return BFS(lch[root]) / BFS(rch[root]); break; } bigint a; string str = M[root]; char temp[111]; strcpy(temp, str.c_str()); a.init(temp); return a; } int main() { char str[123]; while (scanf("%s", str) != EOF) { init(); int len = strlen(str); int root = buildTree(str, 0, len - 1); bigint ans = BFS(root); ans.print(); cout << endl; } system("pause"); return 0; }

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224668.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 上午11:25
下一篇 2026年3月17日 上午11:25


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号