Speed is high O(n)--n is size of string
Key: use lastnum to record the last number before current operator
calc lastnum when number
calc lastnum to sum when +-
set opt when */
opt records the most recent operator
sign plays magic here. It records +/- before the current operator. It also records +/- before */ which helps to add lastnum to get final result.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | class Solution { public: int calculate(string s) { //for loop //opt: 0=+-; 1=*; 2=/; //sign: 1=+ -1=- //when number: get num // if +- lastnum =num // if */ lastnum =lastnum*/num //when +/-: add the number before +/- (lastnum) to sum, set opt //when */: set opt //sum+=sign*lastnum int sign=1; int opt=0; int sum=0; int lastnum; for(int i = 0; i < s.size(); i++){ if(s[i] >= '0' && s[i] <= '9'){ int num = 0; while(i < s.size() && s[i] >= '0' && s[i] <= '9'){ num = num * 10 + s[i] - '0'; i++; } //i--; if(opt == 0) lastnum = num; if(opt == 1) lastnum *= num; if(opt == 2) lastnum /= num; } if(s[i] == '+') { sum += sign * lastnum; opt = 0; sign = 1; } if(s[i] == '-'){ sum += sign * lastnum; opt = 0; sign = -1; } if(s[i] == '*'){ opt = 1; } if(s[i] == '/'){ opt = 2; } } sum += sign * lastnum; return sum; } }; |
reference:
for initial codes:
http://www.wengweitao.com/leetcode-basic-calculator-ii.html
没有评论:
发表评论