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;
    }
};