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