[LeetCode] 227. Basic Calculator II

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

Note: Do not use the eval built-in library function.

Thought process:

Iterate through the string. There are three cases:

1. Number: keep track of number in a variable.
2. Space: do nothing.
3. Operand: look at previous operand. There are two cases:
1. + or -: add / subtract current number.
2. * or /: subtract previous number from result. Add previous * or / number to result. Set previous = previous * or / number.

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 int calculate(String s) { char operand = '+'; int i = 0; int number = 0; int previous = 0; int result = 0; while (i < s.length() || number > 0) { char c = i < s.length() ? s.charAt(i) : 'e'; if (Character.isDigit(c)) { number = number * 10 + (c - '0'); } else if (c != ' ') { if (operand == '+') { result += number; previous = number; } else if (operand == '-') { result -= number; previous = -number; } else if (operand == '*') { result -= previous; result += previous * number; previous *= number; } else { result -= previous; result += previous / number; previous /= number; } number = 0; operand = c; } i++; } return result; } }

Time complexity: O(n).