Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
1 class Solution { 2 public: 3 int calculate(string s) { 4 if (s.empty()) 5 return 0; 6 int res = 0; 7 int sign = 1; 8 stack<int> stack; 9 int len = int(s.length()); 10 for (int i = 0; i < len; i++) { 11 char c = s[i]; 12 if (isdigit(c)) { 13 int cur = c - ‘0‘; 14 while (i + 1 < len && isdigit(s[i + 1])) { 15 cur = cur * 10 + s[i+1] - ‘0‘; 16 i++; 17 } 18 res += cur * sign; 19 } else if (c == ‘+‘) { 20 sign = 1; 21 } else if (c == ‘-‘) { 22 sign = -1; 23 } else if (c == ‘(‘) { 24 stack.push(res); 25 stack.push(sign); 26 res = 0; 27 sign = 1; 28 } else if (c == ‘)‘) { 29 res = stack.top() * res; 30 stack.pop(); 31 res += stack.top(); 32 stack.pop(); 33 sign = 1; 34 } 35 } 36 return res; 37 } 38 };
原文：http://www.cnblogs.com/wxquare/p/5059424.html