Basic Calculator II
Desicription
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:
1 2
| Input: "3+2*2" Output: 7
|
Example 2:
1 2
| Input: " 3/2 " Output: 1
|
Example 3:
1 2
| 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.
Solution
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
| class Solution { public: long long calculate(string s) { stack<long long> numbers; long long number = 0; char sign = '+'; for(int i = 0; s[i]; i++) { if(s[i] >= '0' && s[i] <= '9') { number = number * 10 + s[i] - '0'; } if(!(s[i] >= '0' && s[i] <= '9') && s[i] != ' ' || i == s.size() - 1) { if(sign == '+') { numbers.push(number); } else if(sign == '-') { numbers.push(-number); } else if(sign == '*') { long long top_number = numbers.top(); numbers.pop(); numbers.push(top_number * number); } else if(sign == '/') { long long top_number = numbers.top(); numbers.pop(); numbers.push(top_number / number); } sign = s[i]; number = 0; } } long long result = 0; while(!numbers.empty()) { result += numbers.top(); numbers.pop(); } return result; } };
|