Saturday, July 4, 2015

Basic Calculator II

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.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

A:

走2遍,第一遍算 *  / ,  然后计算  +  -

class Solution {
public:
    int calculate(string s) {
        vector<string> myList;
        int left = 0, right = 0;
        while(left<s.length() )
        {
            if(s[left] ==' ')
            {
                left++;
            }else if(s[left] == '+' || s[left] == '-' || s[left] == '*' || s[left] == '/'){
                string tmp(1,s[left]); // !!!!!!!!!!!!!!!!!!!!! this is the way from char to string
                myList.push_back(tmp);
                ++left;
            }else{ // left is digit
                right = left+1; // next probing place
                while(right<s.length() && s[right]>='0' && s[right] <='9' )
                {
                    right++;
                }
                myList.push_back(s.substr(left, right - left));
                left = right;
            }
        }
        vector<string> myList2;
        for(int i =0;i< myList.size();++i)
        {
            string tmp = myList[i];
            if(tmp == "/" || tmp == "*")
            {
                string strA = myList2.back();
                myList2.pop_back();
                string strB = myList[i+1];
                long a = stol(strA);
                long b = stol(strB);
                long aa = ( tmp=="*" )? (a*b) :(a/b);
                myList2.push_back(to_string(aa));
                i++;                    
            }else{
                myList2.push_back(tmp);
            }
        }
        // check for + and -
        long res = stol(myList2[0]);
        for(int i =1;i< myList2.size();i+=2)
        {
            string op = myList2[i];
            string ob2 = myList2[i+1];            
            if(op == "+")
            {
                res += stol(ob2);
            }else{
                res -= stol(ob2);
            }
        }
        return int(res);
    }
};


Mistakes:
1:  一开始都用int来保存,但是  "0-2147483648"   是不行的。 因此要用long类型




No comments:

Post a Comment