LeetCode 2020-11-24: Basic Calculator II

Basic Calculator II (medium) の挑戦メモです。

問題の概要

• 文字列で与えられる計算式を評価した結果を求める
  • 演算子は四則演算のみ
  • カッコはなし
  • 除算は整数で行い、端数は切り捨て
  • 負数はなし

考え方

• 大学の C 言語演習か何かでこういうのやった気がするなあ…
• それはさておき、これはスタックを利用する方法で解くことができるね
  • 数値を積むスタックと、演算子を積むスタックの 2 つを用意する
  • 計算式の文字列を先頭からパースする
    • 数値が現れた場合、それを数値スタックに積む
      • このとき、 演算子スタックの一番上にある演算子が乗算もしくは除算 の場合にのみ、数値スタックから 2 つ数値を下ろして演算した結果を再度数値スタックに積む処理をする
    • 演算子が現れた場合、それを演算子スタックに積む
  • 計算式のパースを終えたところで、数値スタックと演算子スタックそれぞれを下から順になぞって加算・減算の演算をしていく
• スタックを使う方法で実装 → submit → accept
  • Runtime は 10ms で、Your runtime beats 48.37 % of java submissions.
  • こりゃ遅いですね 😵
• スタックを利用しているのが遅い原因な気がするので、スタックを使わない方法を考えてみよう
  • 1 + 2 ? 3 みたいな計算式を考えると、1 + 2 の部分は後続の演算子が加算・減算か乗算・除算かで計算できる・できないが決まるね
    • 加算・減算なら 1 + 2 を計算してしまえばいいし、乗算・除算の場合は 1 + (2 ? 3 を計算した結果) の計算を保留した状態で次に進めばよさそう
  • なので、直近二つの数値と一つの演算子を保持するようにしよう
• 実装して submit → runtime が 7ms まで縮まった 🤗
• 計算式に半角の空白が含まれるのがちょいちょいうざい
  • 事前に s.replace(" ", "") したら速くなるのかな？ → 1ms 縮まって 6ms になった
  • そういうことなら、 s.toCharArray() で char 配列に変換してから半角空白を潰す処理を入れればよいのでは？ 🤔
• char 配列化 & 空白潰す事前処理をいれた実装を submit → runtime 1ms だけど 100% beats 達成 🎉

コード

スタックを利用する方法

class Solution {
    public int calculate(String s) {
        Stack<Integer> values = new Stack<>();
        Stack<Character> operators = new Stack<>();

        for (int i = 0; i < s.length(); ) {
            char ch = s.charAt(i++);
            if (ch == ' ') {
                continue;
            }

            if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                operators.push(ch);
                continue;
            }

            int value = ch - '0';
            while (i < s.length()) {
                ch = s.charAt(i);
                if (ch < '0' || ch > '9') {
                    break;
                }
                value = value * 10 + (ch - '0');
                i++;
            }

            values.push(value);

            char topOperator = operators.isEmpty() ? ' ' : operators.peek();
            if (topOperator == '*' || topOperator == '/') {
                operators.pop();
                int rhs = values.pop();
                int lhs = values.pop();
                values.push(topOperator == '*' ? lhs * rhs : lhs / rhs);
            }
        }

        int result = values.get(0);
        for (int i = 0; i < operators.size(); i++) {
            char operator = operators.get(i);
            if (operator == '+') {
                result += values.get(i + 1);
            } else {
                result -= values.get(i + 1);
            }
        }

        return result;
    }
}

char 配列化 / 空白潰し

class Solution {
    public int calculate(String _s) {
        char[] chars = _s.toCharArray();
        int len = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                chars[len++] = chars[i];
            }
        }

        int v1 = 0, v2 = 0;
        char o1 = '+';

        int i = 0;
        int v = chars[i++] - '0';
        while (i < len && (chars[i]) >= '0') {
            v = v * 10 + (chars[i] - '0');
            i++;
        }
        v2 = v;

        while (i < len) {
            char o = chars[i++];

            v = chars[i++] - '0';
            while (i < len && (chars[i]) >= '0') {
                v = v * 10 + (chars[i] - '0');
                i++;
            }

            if (o == '+' || o == '-') {
                v1 = o1 == '+' ? v1 + v2 : v1 - v2;
                o1 = o;
                v2 = v;
            } else {
                v2 = o == '*' ? v2 * v : v2 / v;
            }
        }

        return o1 == '+' ? v1 + v2 : v1 - v2;
    }
}