# The Basic Calculator in C/C++

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. You may assume that the given expression is always valid.

Some examples:

`"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5`
`"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5`

### O(n) time, O(1) space

The operator * and / have higher priority over + and -. However, we might consider using + and – as a group separator. For example,

1 + 2 – 3 * 5 can be grouped as +1, +2, -(3*5). The answer would be to add the group values along the scan. At first, the sign is + by default, if we meet an operator, we store it, if we meet numbers, we store it as an intermediate number. We add the number to the final value if the current oper is + or -. Otherwise, we need to multiply/divide it with the previous value.

`class Solution { public:     int calculate(string s) {         int r = 0;         char oper = '+';         int tmp = 0;         int i = 0;         while (i < s.length()) {             if (s[i] != ' ') {                 if (s[i] >= '0' && s[i] <= '9') {                     int num = 0;                     while (i < s.length() && s[i] >= '0' && s[i] <= '9') {                         num = num * 10 + s[i] - '0';                         i ++;                     }                     if (oper == '+' || oper == '-') {                         r += tmp;                         tmp = num * (44 - oper); // 43 = +, 45 = -                     } else if (oper == '*') {                         tmp *= num;                     } else {                         tmp /= num;                     }                     continue;                 } else {                     oper = s[i];                 }             }             i ++;         }         return r + tmp;     } };`
`class Solution { public:     int calculate(string s) {         int r = 0;         char oper = '+';         int tmp = 0;         int i = 0;         while (i < s.length()) {             if (s[i] != ' ') {                 if (s[i] >= '0' && s[i] <= '9') {                     int num = 0;                     while (i < s.length() && s[i] >= '0' && s[i] <= '9') {                         num = num * 10 + s[i] - '0';                         i ++;                     }                     if (oper == '+' || oper == '-') {                         r += tmp;                         tmp = num * (44 - oper); // 43 = +, 45 = -                     } else if (oper == '*') {                         tmp *= num;                     } else {                         tmp /= num;                     }                     continue;                 } else {                     oper = s[i];                 }             }             i ++;         }         return r + tmp;     } };`

You can also build the reverse polish expression , which is a more generalized solution that can be used to evaluate the expression containing () brackets.

–EOF–

GD Star Rating