问题地址：https://leetcode.com/problems/basic-calculator/
问题简述：给定一个含有空格、加减运算符、括号与数字的算式，对其求值。
问题分析：站在一个熟悉数据结构的人，或者是竞赛党和大牛的角度来看，当然可以利用栈和简单的运算符优先级把表达式转化为后缀表达式，然后再利用另一个栈对转化好的表达式进行求值。然而，笔者本人是算法渣。然而对于算法渣就没有什么简单直观的方法吗？其实是有的，且听我娓娓道来。
解法思路：分析这个Basic Calculator可知，首先应该去除空格。然后，由于只存在加减两种操作，故不需要考虑运算符优先级，从而可以顺序求值。这里顺序求值指的是，把单个的数或者括号连同其前面的符号视作一个整体进行求值，比如3+5-(2-1)当中，就可以认为分别存在+3,+5,-(2-1)三个需要进行求值的部分。对于单个数求值过程显然是简单的，对于符号后是一个括号的情况，就取出括号内部的表达式递归求值。为了识别括号内的表达式，需要一个辅助栈，每当检测到左括号就执行入栈，识别到右括号就出栈，如果空栈时检测到右括号，说明括号内的子表达式结束了。在下面的代码中，栈被简化为了一个初始化为0的计数器，入栈等价于加1而出栈等价于减1。
运行效果：在自己简单的用例下，运行结果都十分完美。不过在LeetCode上，对于超长表达式，求值就会超时，间接证明了这个直观方法复杂度不容乐观的事实。但是，谢天谢地，程序没有出现过运行错误的情况。
复杂度分析：设字符串的长度为m，首先去除空格的操作复杂度为O(m)。然后求值部分的复杂度，个人感觉是难于计算的，因为括号的位置、括号中间子表达式的长度等都不确定，加之程序递归执行，目前为止感觉难以分析（也许是可以的，只不过我太渣了）。
最后附上代码吧：
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 5 //Calculate program 6 int calc(string exp) 7 { 8 exp = "+" + exp; 9 unsigned int i = 0; 10 int result = 0; 11 12 while (i<exp.size()) 13 { 14 bool oper = (exp[i] == ‘+‘); 15 int num = 0; 16 i++; 17 18 //Number 19 if (exp[i] != ‘(‘) 20 { 21 while ((exp[i] >= ‘0‘) && (exp[i] <= ‘9‘) && (i<exp.size())) 22 { 23 num = num * 10 + (exp[i] - ‘0‘); 24 i++; 25 } 26 } 27 //"(", recursively calculate sub-expression 28 else 29 { 30 string sub_exp; 31 unsigned int se_level = 0; 32 33 i++; 34 while (true) 35 { 36 //"(" 37 if (exp[i] == ‘(‘) 38 se_level++; 39 //")" 40 else if (exp[i] == ‘)‘) 41 { 42 if (se_level == 0) 43 break; 44 else 45 se_level--; 46 } 47 48 sub_exp += exp[i]; 49 i++; 50 } 51 num = calc(sub_exp); 52 i++; 53 } 54 55 result = oper ? (result + num) : (result - num); 56 } 57 58 return result; 59 } 60 61 //Main program 62 int main() 63 { 64 string _exp, exp; 65 unsigned int i; 66 67 //Trim spaces 68 getline(cin, _exp); 69 for (i = 0; i<_exp.size(); i++) 70 if (_exp[i] != ‘ ‘) 71 exp += _exp[i]; 72 //Calculate expression 73 cout << calc(exp) << endl; 74 return 0; 75 }
（看完大牛们的博客之后，感觉到了自己实力的捉急。哎，还是老老实实做个工程党吧）
原文：http://www.cnblogs.com/lqf-96/p/basic-calculator.html