Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7" 3/2 " = 1" 3+5 / 2 " = 5

 

Note: Do not use the eval built-in library function.

1 class Solution { 2 public: 3     int calculate(string s) { 4         stack
     
       num; 5         stack
      
        symbol; 6         symbol.push('+'); 7         int n; 8         n=s.length(); 9         int right;10         if(n<1) return -1;11         int i;12         for(i=0;i
       
        ='0'&&s[i]<='9')25                      {26                          right=right*10+(s[i]-'0');27                          i++;28                      }29                      if((!symbol.empty())&&(symbol.top()=='*'||symbol.top()=='/'))30                      {31                          right=cal_helper(num.top(),right,symbol.top());32                          num.pop();33                          symbol.pop();34                      }35                      num.push(right);36                  }37         }38         int res=0;39         char sym;40         int left;41         while(!symbol.empty())42         {43             left=num.top();44             sym=symbol.top();45             if(sym=='-')46               left=-left;47             num.pop();48             symbol.pop();49             res+=left;50         }51         return res;52     }53 private:54     int cal_helper(int left, int right, char s)55     {56         57         switch(s)58         {59         case '*':return left*right;60         case '/':return left/right;61         default:return 0;62         }63         64     }65 };