[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 asrese that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 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^5
• s consists of integers and operands ('+', '-', '*', '/') separated by some operandber of spaces.
• s represents a valid expression. All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

---

Solution

class Solution {
    public int calculate(String s) {
        int res = 0;
        int tmpRes = 0;
        int operand = 0;
        char operator = '+';
        // 현재 인덱스에서 피연산자가 나오면 이전에 존재하는 연산자와 피연산자가 무엇인지 알아야함.
        // 반복문 수행 중 피연산자가 등장해야 계산을 수행할 수 있다.
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c))
                operand = operand * 10 + c - '0'; // i 자리가 피연산자인 경우
            if (i == s.length() - 1 || !Character.isDigit(c) && c != ' ') { // i 자리가 연산자인 경우, 마지막 문자면 실행될 필요 없음.
                switch(operator) {
                    case '+':
                        res += tmpRes;
                        tmpRes = operand;
                        break;
                    case '-':
                        res += tmpRes;
                        tmpRes = -operand;
                        break;
                    // 우선 순위 때문에 
                    case '*':
                        tmpRes *= operand;
                        break;
                    case '/':
                        tmpRes /= operand;
                        break;
                }
                operator = c;
                operand = 0;
            }
        }
        res += tmpRes;
        return res;
    }
}

Explanation

• 결과 반환을 위한 변수 res을 선언하고 문자열의 각 문자를 참조하면서 피연산자와 연산자를 구분하기 위해서 for반복문을 작성한다.

  int res = 0;
  for (int i = 0; i < s.length(); i++)
  

• 문자열 s의 피연산자를 찾기 위해 변수 opertor를 선언하고, for반복문의 각 문자를 참조하면서 피연산자를 찾기 위해 for반복문 내에 if조건문을 작성한다.

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

• 연산자 중에는 우선순위가 존재하므로 계산 결과를 단순히 중첩시켜 나가는 것이 아니라 우선 순위가 높은 연산자가 먼저 사용 되고 우선 순위가 낮은 연산자가 다음에 사용되어야 한다.따라서 우선 순위가 높은 연산자의 중간 계산 결과를 저장하기 위해서 변수 tmpRes를 선언하고, 문자열 s내에서 연산자를 찾기 위해 변수 operand를 선언한다.

  int tmpRes = 0;
  char operator = '+';
  

• 문자열을 탐색하다가 계산이 수행되는 시점은 연산자를 만났을 때가 된다. 우선순위가 낮은 연산자를 만나면 변수 res에 바로 계산결과를 합산하고 우선순위가 높은 연산자를 만나면 변수 tmpRes에 계산결과를 모아놓은 뒤 최종적으로 변수 res에 합산된도록 if조건문을 작성한다.
• 문자열 s에서 마지막 문자는 피연산자에 포함되는 문자이므로 연산자를 만나지 않게 되고, 계산에 포함되지 않을 수 있으므로, for반복문의 변수 i가 문자열 s의 마지막 문자열을 참조하는 것이라면 피연산자가 계산에 사용되도록 if조건문을 작성해야하고, else if문으로 작성해서는 안된다. 그리고 for반복문의 변수 i가 참조하는 문자가 숫자가 아님과 공백이 아니라는 조건을 추가해야 올바르게 if조건문이 실행될 수 있다.

  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (Character.isDigit(c))
        operand = operand * 10 + c - '0';
    if (i == s.length() - 1 || !Character.isDigit(c) && c != ' ') {
        switch(operator) {
            case '+':
                res += tmpRes;
                tmpRes = operand;
                break;
            case '-':
                res += tmpRes;
                tmpRes = -operand;
                break;
            case '*':
                tmpRes *= operand;
                break;
            case '/':
                tmpRes /= operand;
                break;
        }
        operator = c;
        operand = 0;
    }
  }
  

• for 반복문을 빠져나오면 변수 tmpRes에 계산결과가 남아있을 수 있으므로, 마지막에 계산된 변수 tmpRes의 값을 변수 res에 더해주고 그 값을 반환하도록 한다.

  res += tmpRes;
  return res;