calc the sum的一种利用栈的解法

这道题解法很多，是递归算法的一道很典型的例题，并且用字符串来解效率也还可以（我也不知道时间复杂度多少算效率高，还没学数据结构），用栈来解效率不高内存还大，仅仅为了满足本人的好奇心而已~

不过我们可以先来复习一下什么是栈：

（以下是我对栈的理解）
栈（stack）是一种线性的表，只能在表末尾进行运算，比如push（压入）和pop（删除），可以把它想象成一种容器，下端封口，（比如杯子，只能在杯口操作）后放进去的东西可以先拿出来，先放进去的东西要最后才能拿出来。

我对栈的理解比较浅，但如果只是简单的应用的话，这些也足够了。

然后来看一下栈的用法：

#include<iostream> #include<stack>//头文件 using namespace std; int main() {     Type a;//定义一个变量    stack<Type> MyStack;//定义一个Type类型的栈    MyStack.push(a);//入栈，将变量a压入栈中，当然变量a一定要有效    MyStack.top();//访问栈顶的数据，即刚刚压进去的a，返回的是它的值    MyStack.pop();//出栈，把栈顶的数据扔掉    MyStack.empty();//看这个栈是不是空的，如果是空的，就返回1，否则返回0    MyStack.size();//返回栈中的元素个数 } 

目前会这些也就足够用了，是一些比较基本的用法

接下来我们来看题了

题目

这个题要求我们把一个数字的每一位加起来，直到结果是一位数，很显然是递归，但是有一个坑，这里的数据范围很大（我一开始就掉进坑里了），所以用int也好，long long int也好，是肯定不行的，可以参考一下它们能表示的数据范围。

所以一种比较简单的方法就是使用字符串啦。

不过我的好奇心比较强，刚好前一段时间了解到了栈，就像现学现卖，用栈解一下这个题试试。

应该是正确的，因为我在oj上是通过了的，虽然运行时间和内存很感人（暴风哭泣），不过如果有有漏洞的地方还是希望大家指出来啦~

代码

int getanswer(stack<char> n,int a) { int ans=0; //用来计算出每位相加的数字，需要进位时存入新的栈中  stack<char> mid; while (!n.empty()) {   ans += (n.top()-'0');   n.pop(); //每算一位数字，就将其从栈中删除 if (ans >= 10) //进位 { if (mid.empty()) //栈空时不存在top也无法pop，防止报错，直接放入栈中 {     mid.push(ans / 10 + '0'); } else if (mid.top() < 9 + '0') //当栈的top仍是个位数时把这一位进上去 //为什么这里是9而不是10？ //因为ans的十位上的数字一定不会超过1 //要考虑进位后超过10的情况 { int tmp = mid.top();     mid.pop();     tmp += ans / 10;     mid.push(tmp); }//这里是为了进位，而要把栈顶的元素取出来，进位后再放回去，因为无法直接对栈顶的元素操作 else //直接放在栈中 {     mid.push(ans / 10 + '0'); } //这一步ans要把十位的数字丢掉    ans = ans % 10; } }  mid.push(char(ans + '0')); //记住这里要把最后一位放在栈中 if(mid.size()>1 )a = getanswer(mid,a); //递归，如果新的栈中不止一位数字，即输入的字符串每一位数字相加的和不是个位数 //那就需要继续计算 if (mid.size()==1) return mid.top(); //直到最后的结果是个位数，这时就可以把栈中的数字返回了 return a; } 

很长的代码，效率也的确不高

上面的是用字符串解的，下面的是我的这种算法

不过我的好奇心已经满足了，这波不亏。

对了，还有输入输出：

int main() { int t; scanf("%d", &t); getchar(); for (int i = 0; i < t; ++i) {   stack<char> n; int a = 0; char x[N]; scanf("%s", x); for (int j = 0; x[j] != ''; j++) {    n.push(x[j]); }//将所输入字符串中的每个字符按顺序存在栈中 printf("%cn", getanswer(n,a)); //a是用来记录结果的 } return 0; }