idea：刚开始是打算分类讨论，建立了数字栈和字符栈，按照传入字符当时两个栈的基本情况分类，结果讨论完之后分类太麻烦，导致分析完了之后漏洞不少。我觉得这道题难点在于括号和负号的处理，一开始将导致计算机出错的情况当成了重点，所以思路错了。
idea：下面的题解是遇到一个数处理一个数，无论该数是在括号里边还是外边，都将其按照括号展开后的情况直接加或减进行处理。在这里编者运用了sign记录了每一个数前边的符号情况，并且考虑了连续数字在字符串中的处理，如12+14实际上是五个字符
题解：
class Solution {
public:
int calculate(string s) {
stack<int> ops; //建立栈，仅用来储存当前位置的数字在括号展开后的实际符号情况
ops.push(1); //基础符号默认为+
int sign = 1; //默认为+
int ret = 0; //当前得数
int n = s.length();
int i = 0;
while (i < n) {
if (s[i] == ‘ ‘) {
i++;
} else if (s[i] == ‘+’) {
sign = ops.top(); //“+”对sign值不产生影响
i++;
} else if (s[i] == ‘-‘) {
sign = -ops.top(); //“-”要变号
i++;
} else if (s[i] == ‘(‘) {
ops.push(sign); //遇到左括号将当前基础符号压入栈，即如果括号前是“-”，将“-1”入栈，在括号里边遇到“-”时sign为“+1”，遇到“+”是sign为“-1”。括号前是“+”，则与主式基础符号相同
i++;
} else if (s[i] == ‘)’) { //遇到右括号说明括号结束，将括号中的基础符号弹出栈
ops.pop();
i++;
} else { //遇到数字则开始计算
long num = 0; //计算当前遇到的数字实际大小，例如连续遇到字符’3’和’5’，实际上为35，则num记为int值35
while (i < n && s[i] >= ‘0’ && s[i] <= ‘9’) { //考虑遇到连续字符的情况，即参与运算的不一定都是个位数，在这里用一个循环继续遍历后续的数字字符
num = num * 10 + s[i] – ‘0’; //百位*100,十位*10，个位*1
i++;
}
ret += sign * num; //根据sign值判断是加上当前数还是减去
}
}
return ret;
}
};
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 为字符串 ss 的长度。需要遍历字符串 ss 一次，计算表达式的值。
空间复杂度：O(n)O(n)，其中 nn 为字符串 ss 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 nn。
明天再看其他的题解，没想到一道题做到半夜两点，结果连答案都分析了好半天才看懂
——————————————————————————————————————————————————————————–
原文地址：http://www.cnblogs.com/Ting-LOVE/p/16793448.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
