[leetcode #227] Basic Calculator II

Problem

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2³¹, 2³¹ - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 2³¹ - 1].
The answer is guaranteed to fit in a 32-bit integer.

Idea

무조건 풀어봐야 할 좋은 문제다. 페이스북 면접 시험에도 가끔 출제되는 문제라고 알고 있다.

String으로 주어진 수식을 계산하여 결과값을 리턴하면 된다. 보기엔 간단하게 보이지만 막상 풀면 쉽게 풀리지 않는다.

우선 주어진 문자열이 null이거나 비어있을 경우 곧바로 0을 리턴한다.

문자열이 유효한 수식일 경우 문자를 하나씩 확인하면서 수식을 계산한다. 이 때 앞에서 나온 연산을 저장할 문자로 operation을 지정한다. 처음 operation은 '+'가 되므로 '+'로 초기값을 설정한다.

현재 문자가 숫자일 경우 앞에서 계산한 값에 10을 곱하고 현재 문자에서 '0'을 빼면서 currentNumber를 계산한다. currentNumber는 문자가 연산이 되기 전까지 숫자를 의미한다.

현재 문자가 연산일 경우 앞에서 저장한 연산에 따라 처리하는 방식이 다르다.

앞에서 저장한 operation이 '+'나 '-'일 경우 lastNumber를 결과값에 더하고, lastNumber를 '+'나 '-'에 따라 currentNumber 또는 -currentNumber로 설정한다. 이 때 lastNumber는 '*'나 '/'가 나올 경우 연속된 수를 저장하기 위해 사용한다.

operation이 '*'일 경우 lastNumber에 currentNumber를 곱한다.

operation이 '/'일 경우 lastNumber를 currentNumber로 나눈다.

수 처리가 끝나면 operation은 현재 연산으로 바꾸고 currentNumber는 0으로 설정해준다.

마지막으로 유의할 사항은 문자의 index가 문자열의 마지막을 가리키고 숫자인 경우 lastNumber 계산을 해야 한다는 것이다. 이는 현재까지 사칙연산이 문자로 등장할 때마다 계산을 했기 때문에 마지막 수의 경우 계산이 생략될 수 있기 때문이다.

결과값을 리턴하기 전에 lastNumber를 더하면 된다.

Solution

class Solution {
    public int calculate(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        int currentNumber = 0;
        int lastNumber = 0;
        int result = 0;
        char operation = '+';
        int length = s.length();

        for (int i = 0; i < length; i++) {
            char currentChar = s.charAt(i);
            if (Character.isDigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }

            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length-1) {

                if (operation == '+' || operation == '-') {
                    result += lastNumber;
                    lastNumber = (operation == '+') ? currentNumber : -currentNumber;
                }
                if (operation == '*') {
                    lastNumber *= currentNumber;
                }
                if (operation == '/') {
                    lastNumber /= currentNumber;
                }
                operation = currentChar;
                currentNumber = 0;
            }
        }

        result += lastNumber;

        return result;
    }
}

Reference

https://leetcode.com/problems/basic-calculator-ii/