[LeetCode]Basic Calculator

Basic Calculator

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.

用到stack，如果遇到左括号'('将之前的值和1.-1表示运算符号压入stack中，遇到右括号')'，将运算符号和值去除做运算。

 1 class Solution {
 2 public:
 3     int calculate(string s) {
 4         if(s.length()==0) return 0;
 5         stack<int> mystack;
 6         int result=0;
 7         int op=1;
 8         for(int i=0;i<s.length();i++)
 9         {
10             if(s[i]>='0' && s[i]<='9')
11             {
12                 int number=s[i]-'0';
13                 while((i+1)<s.length() && s[i+1]>='0' && s[i+1]<='9')
14                 {
15                     i++;
16                     number=number*10+s[i]-'0';
17                 }
18                 result+=op*number;
19             }
20             if(s[i]==' ')
21             {
22                 continue;
23             }
24             if(s[i]=='+')
25             {
26                 op=1;
27             }
28             if(s[i]=='-')
29             {
30                 op=-1;
31             }
32             if(s[i]=='(')
33             {
34                 mystack.push(result);
35                 result=0;
36                 mystack.push(op);
37                 op=1;
38             }
39             if(s[i]==')')
40             {
41                 op=mystack.top();
42                 mystack.pop();
43                 result=op*result+mystack.top();
44                 mystack.pop();
45                 op=1;
46             }
47         }
48         return result;
49     }
50 };