読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

中置記法の数式文字列から計算結果を求める操車場アルゴリズム

最近 Algorithms, Part I - Princeton University | Coursera の社内勉強会を開いている。そこで「Stacks and Queues」という章をみんなで学習し、議論したところ、中置記法の数式文字列から計算結果を求める操車場アルゴリズム(Shunting-yard algorithm)というものがあるということを知った。

操車場アルゴリズムというのは、中置記法の数式文字列から計算結果を求めるというようなことができるアルゴリズム。オペレータスタックと値スタックの二つがあるだけでトークンを一つずつ読みつつその都度計算するだけで計算結果を求めることができる。パースして構文木を作るというフローを取ることなく計算ができるというのが面白い。このアルゴリズムの説明は Wikipedia操車場アルゴリズム - Wikipedia の説明が非常に分かりやすい。

このアルゴリズムを使うことで、例えば以下のような数式を計算する計算機を作ることができる。

  • 1 + 2
  • 1 / 2 + 2 * 3 - 1
  • 1.8 * 3 - 2.1 + 0.5
  • 1.8 * ( 3 - 2.1 ) + 0.5
  • ( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )

このアルゴリズム面白いなーと思い、実際に理解を深めるために、この操車場アルゴリズムを実装してみた。内容をブログに書いておく。

今回実装した仕様

操車場アルゴリズムの全てを実装しようとすると難しいので、今回は簡易版で実装してみた。実装した機能は次のとおり。

  • 数値にはdoubleの数値が使える
  • +, -, *, /の演算子が利用できる
  • 括弧を使うことができる

もっと作り込めば右結合性の演算子(例えば^)や関数(例えばsqrt)にもこのアルゴリズムで対応できる。

アルゴリズムの流れ

基本的には数値や演算子、括弧といったトークンを一つずつ読み取り、読み取ったトークンに従ってそれぞれ次のように処理をするだけで良い。

  • tokenが数値なら値スタックに積む
  • tokenがオペレータ(o1)の時
    • オペレータスタックのトップにオペレータo2 があり、o1 が左結合性で、かつ優先順位が o2 と等しいか低い場合、以下を繰り返す
        • o2 をオペレータスタックからpopし、値スタックから値を二つpopし、演算し、結果を値スタックにpushする
    • o1 をオペレータスタックにプッシュする。
    • 注) 右結合性のオペレータは未実装
  • トークンが左括弧の場合、オペレータスタックにプッシュする
  • トークンが右括弧の場合
    • オペレータスタックのトップにあるトークンが左括弧になるまで、オペレータスタックからオペレータをpopし、値スタックから値を二つpopし、それらを演算し、値スタックに結果をプッシュする
    • 左括弧があったらスタックからpopし、何もせずに捨てる

全てのトークンの読み込みが終わったら、最後の処理として

  • オペレータスタックが空になるまで、オペレータスタックからオペレータをpopし、値スタックから値を二つpopし、それらを演算し、値スタックに結果をプッシュする
  • 値スタックに入っている値を返す

この流れで計算式の文字列から計算をして、結果を返すということができる。状態はスタック二つしかないのでそこまで複雑になっていない。

アルゴリズムの実装

アルゴリズムの流れが分かったので、次は実装してみる。上の流れは明確なアルゴリズムとなっているので、そのまま実装すれば良い。

今回はJavaで実装してみた。コード上にコメントも書いているのでコードを読めばスムーズに理解できると思う。

https://github.com/shibayu36/algorithms/blob/master/src/main/java/org/shibayu36/algorithms/FormulaCalculator.java

package org.shibayu36.algorithms;

import java.math.BigDecimal;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import org.apache.commons.lang3.math.NumberUtils;

public class FormulaCalculator {
  // オペレーターの優先順位
  private static final Map<String, Integer> opPriority = new HashMap<String, Integer>() {
    {
      put("+", 2);
      put("-", 2);
      put("*", 3);
      put("/", 3);
    }
  };

  /**
   * 数式の文字列を与えると計算結果を返す
   * @param formula 数式の文字列。トークンは空白で区切られている必要がある
   * @return
   */
  public static double calculate(String formula) {
    Stack<String> ops = new Stack<>(); // オペレーターのスタック
    Stack<Double> vals = new Stack<>(); // 値のスタック

    String[] tokens = formula.split(" ");

    for (String token: tokens) {
      if (NumberUtils.isCreatable(token)) {
        // tokenが数値なら値スタックに積む
        vals.push(Double.parseDouble(token));
      }
      else if (isOperator(token)) {
        // tokenがオペレータ(o1)の時
        // - オペレータスタックのトップにオペレータo2 があり、o1 が左結合性で、
        //   かつ優先順位が o2 と等しいか低い場合、以下を繰り返す
        //     - o2 をオペレータスタックからpopし、値スタックから値を二つpopし、
        //       演算し、結果を値スタックにpushする
        // - o1 をオペレータスタックにプッシュする。
        // (右結合性のオペレータは未実装)
        while (ops.size() > 0) {
          String lastOp = ops.pop();
          // "("が入っている場合があるため
          // オペレータスタックの最後もオペレータであることを確認する
          if (isOperator(lastOp) && getOpPriority(token) <= getOpPriority(lastOp)) {
            double val2 = vals.pop();
            double val1 = vals.pop();
            vals.push(applyOperator(lastOp, val1, val2));
          }
          else {
            ops.push(lastOp);
            break;
          }
        }
        ops.push(token);
      }
      else if (token.equals("(")) {
        // トークンが左括弧の場合、オペレータスタックにプッシュする
        ops.push(token);
      }
      else if (token.equals(")")) {
        // トークンが右括弧の場合
        // - オペレータスタックのトップにあるトークンが左括弧になるまで、
        //   オペレータスタックからオペレータをpopし、値スタックから値を二つpopし
        //   それらを演算し、値スタックに結果をプッシュする
        // - 左括弧をスタックからpopするが、何もせずに捨てる
        while (ops.size() > 0) {
          String op = ops.pop();
          if (op.equals("(")) {
            break;
          }
          else {
            double val2 = vals.pop();
            double val1 = vals.pop();
            vals.push(applyOperator(op, val1, val2));
          }
        }
      }
    }

    // 読み取るべきトークンが無くなったら、オペレータスタックが空になるまで
    // オペレータスタックからオペレータをpopし、値スタックから値を二つpopし
    // それらを演算し、値スタックに結果をプッシュする
    while (ops.size() > 0) {
      String op = ops.pop();
      if (isOperator(op)) {
        double val2 = vals.pop();
        double val1 = vals.pop();
        vals.push(applyOperator(op, val1, val2));
      }
    }

    // 値スタックに最後に入っている結果が演算結果である
    return vals.pop();
  }

  private static double applyOperator(String op, double val1, double val2) {
    BigDecimal b1 = new BigDecimal(String.valueOf(val1));
    BigDecimal b2 = new BigDecimal(String.valueOf(val2));
    switch (op) {
      case "+":
        return b1.add(b2).doubleValue();
      case "-":
        return b1.subtract(b2).doubleValue();
      case "*":
        return b1.multiply(b2).doubleValue();
      case "/":
        return b1.divide(b2).doubleValue();
    }

    // ここまで来たら意図しないoperatorが来たということなので例外
    throw new RuntimeException("Unexpected operator: " + op);
  }

  private static int getOpPriority(String token) {
    return opPriority.getOrDefault(token, 0);
  }

  private static boolean isOperator(String token) {
    return opPriority.containsKey(token);
  }
}

さらにテストでうまく動いているか確認する。
https://github.com/shibayu36/algorithms/blob/master/src/test/java/org/shibayu36/algorithms/FormulaCalculatorTest.java

package org.shibayu36.algorithms;

import static org.assertj.core.api.Assertions.assertThat;

import org.junit.Test;

public class FormulaCalculatorTest {

  @Test
  public void calculate() throws Exception {
    double result;

    result = FormulaCalculator.calculate("1 + 2");
    assertThat(result).isEqualTo(3);

    result = FormulaCalculator.calculate("1 / 2 + 2 * 3 - 1");
    assertThat(result).isEqualTo(5.5);

    result = FormulaCalculator.calculate("1.8 * 3 - 2.1 + 0.5");
    assertThat(result).isEqualTo(3.8);

    result = FormulaCalculator.calculate("1.8 * ( 3 - 2.1 ) + 0.5");
    assertThat(result).isEqualTo(2.12);

    result = FormulaCalculator.calculate("( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )");
    assertThat(result).isEqualTo(3.85);
  }
}

これでテストが通ったので、操車場アルゴリズムを実装し、中置記法の数式文字列から計算結果を求めることができた。

まとめ

今回は操車場アルゴリズム(Shunting-yard algorithm)というものを実際に実装してみた。単純にスタックを二つ使うだけで、構文木などを作らなくとも、パースしながら同時に計算することで計算結果を得られるというのが面白かった。

実際に実装してみるとアルゴリズムについて理解が深まり、かつ知識が定着するので、今後も面白そうなアルゴリズムがあったら実装してみたい。

【補足】実行しながらスタックの様子を眺めてみる

理解度を深めるために、実行しながらスタックの様子を眺めてみる。部分部分に注釈を書いた。

実装してみるとこんな感じで自由に動かしてさらに理解が深められるので良いですね。

( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )

formula: ( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )
===============
token: (
ops: [(]
vals: []
------------
token: 10
ops: [(]
vals: [10.0]
------------
token: +
ops: [(, +]
vals: [10.0]
------------
token: 2.2
ops: [(, +]
vals: [10.0, 2.2]
------------
token: *
ops: [(, +, *]
vals: [10.0, 2.2]
------------
token: 5.5
ops: [(, +, *]
vals: [10.0, 2.2, 5.5]
------------
# *と/の優先度が一緒なので*を計算して/をpush
token: /
ops: [(, +, /]
vals: [10.0, 12.1]
------------
token: 2.2
ops: [(, +, /]
vals: [10.0, 12.1, 2.2]
------------
# /と*の優先度が一緒なので、/を計算して*をpush
token: *
ops: [(, +, *]
vals: [10.0, 5.5]
------------
token: (
ops: [(, +, *, (]
vals: [10.0, 5.5]
------------
token: 1.2
ops: [(, +, *, (]
vals: [10.0, 5.5, 1.2]
------------
token: -
ops: [(, +, *, (, -]
vals: [10.0, 5.5, 1.2]
------------
token: 0.6
ops: [(, +, *, (, -]
vals: [10.0, 5.5, 1.2, 0.6]
------------
token: *
ops: [(, +, *, (, -, *]
vals: [10.0, 5.5, 1.2, 0.6]
------------
token: 3.0
ops: [(, +, *, (, -, *]
vals: [10.0, 5.5, 1.2, 0.6, 3.0]
------------
# )があったので、最初に(が見つかるまで、つまり*と-を計算して値をpush
token: )
ops: [(, +, *]
vals: [10.0, 5.5, -0.6]
------------
token: /
ops: [(, +, /]
vals: [10.0, -3.3]
------------
token: 2
ops: [(, +, /]
vals: [10.0, -3.3, 2.0]
------------
# /より+のほうが優先度が低いので、/を計算して+をpush
token: +
ops: [(, +]
vals: [8.35]
------------
token: 4.5
ops: [(, +]
vals: [8.35, 4.5]
------------
token: *
ops: [(, +, *]
vals: [8.35, 4.5]
------------
token: (
ops: [(, +, *, (]
vals: [8.35, 4.5]
------------
token: 2.0
ops: [(, +, *, (]
vals: [8.35, 4.5, 2.0]
------------
token: -
ops: [(, +, *, (, -]
vals: [8.35, 4.5, 2.0]
------------
token: 3
ops: [(, +, *, (, -]
vals: [8.35, 4.5, 2.0, 3.0]
------------
token: )
ops: [(, +, *]
vals: [8.35, 4.5, -1.0]
------------
token: )
ops: []
vals: [3.85]
------------

問題の効率的な解決方法を学ぶ - 「世界一やさしい問題解決の授業」読んだ

仕事で何かしら課題を見つけた時に、それを効率よく解決する方法にはどういうものが知りたかった。そこで参考になりそうな「世界一やさしい問題解決の授業」を読んだ。

世界一やさしい問題解決の授業―自分で考え、行動する力が身につく

世界一やさしい問題解決の授業―自分で考え、行動する力が身につく

この本は非常に良かった。100ページ強と非常に少ないページ数ながら、その中に問題解決のためのエッセンスが詰め込まれていて勉強になった。分解の木や課題分析シートなど問題解決のためのツールもコラムに書かれていて、これらも参考になる。とにかくおすすめ。

「課題を見つけて解決策をとりあえず試してみたけど何かうまくいかなかった」というような経験をしたことがある人は読んでみると良いと思う。薄い本ですぐに読めるので、とりあえず誰でも読んでみると良さそう。


この本の中で自分が印象に残った次の二点をまとめておく。

  • 問題解決とは「現状を正確に理解し」「問題の原因を見極め」「効果的な打ち手までを考え抜き」「実行する」こと
  • イデアを書き出し、分類や並び替えをし、分解の木を作る

問題解決とは「現状を正確に理解し」「問題の原因を見極め」「効果的な打ち手までを考え抜き」「実行する」こと

課題を発見した時に、よくやってしまいがちなミスはとりあえず思いついた解決策を実行してしまうことだ。例えば「チーム内でコミュニケーションが取れていない」という状況を発見した時に、じゃあ「コミュニケーションを取るために毎日会話ミーティングを用意しよう」と短絡的に解決策を実施してしまうということがある。やってみるとうまく解決できなかったということがよく起こる。

この本では問題解決とは「1.現状を正確に理解し」「2.問題の原因を見極め」「3.効果的な打ち手までを考え抜き」「4.実行する」ことと定義されている。例えば「チーム内でコミュニケーションが取れていない」という状況を見つけた時について考えてみると

  • 1.現状を正確に理解し : 「チーム内でコミュニケーションが取れていない」という状況を見つけた時、そもそもその状況は問題なのか、その状況によってどういう問題が起こっているかを自問し、現在の状態を正確に理解する
  • 2.問題の原因を見極め : コミュニケーションが取れていない状態はなぜ起こっているのかを深く考え、原因を見極める
  • 3.効果的な打ち手までを考え抜き : その課題に対して、どのようにすればコミュニケーションが取れる状態になるかをたくさん考え、その中から効果的な打ち手を洗い出す
  • 4.実行する : 効果的な打ち手を考えられたら、実際に実行する

というふうになる。この手順で考えれば、解決策を実施する前に、実は問題ではないかも、見えていることが原因ではないかも、やろうとしていた改善策は効果的ではないかもというようなことが見えてくる。結果として先程のように短絡的に解決策を実施したけどあまり効果はなかったということを防ぐことができそうだった。

今後何か課題を見つけたときは基本的にこの手順を意識して、解決策を無駄打ちしないようにしたいと思う。

イデアを書き出し、分類や並び替えをし、分解の木を作る

この本の中で問題解決のツールとして、分解の木というものが紹介されていた。このツールは原因を探したり、アイデアを広げたりするのに便利らしい。分解の木とは、ロジックツリーとも呼ばれているもので、要素を漏れなくダブりなく分解していくもの。【3分でわかる】ロジックツリーの使いこなし方 | 株式会社いないいないばぁ を見るとどのようなものか分かると思う。

このロジックツリーというものが役立つということは昔から知っていた。しかし、いざやってみようとすると、はじめからうまく分解するということが難しく困っていた。

そのように思っていたら、この本で最初からうまく分解することが出来ない時や途中で煮詰まった時にどうすればよいか書かれていたので非常に参考になった。うまく分解できないと思ったら、

  • とりあえず思いつくアイデアをメモ書きでも良いので全部書きだす
  • 書き出したアイデアを似た者同士で分類したり、並び替えたりする
  • 分類してみると共通点が見つかるので、それらを使ってまた分解に戻る

といった手順を踏むといいらしい。確かに分解できないと煮詰まったときでも、課題の原因として考えつくものをとにかくリストアップしたり、解決策をとにかくリストアップしたりすることはできる。

今後は分解に煮詰まったときは、そこで頑張って分解しようと考え込みすぎず、とりあえず一回アイデアを書き出し、分類や並び替えをするということを心がけたいと思った。

まとめ

何かしら課題を見つけた時に、それを効率よく解決する方法を知るために「世界一やさしい問題解決の授業」を読み、印象に残ったところをまとめてみた。他にも、原因を見極めるいいやり方や、打ち手の考え方、課題分析シートや仮説の木など問題解決に役立つツールなどが解説されていて、それらも非常に参考になった。薄い本ながら非常に内容は濃いものだったのでおすすめ。

読書ノート

読みながら書いていた読書ノートを貼っておく。

  • 問題解決とは、「1. 現状を正確に理解し」「2. 問題の原因を見極め」「3. 効果的な打ち手までを考え抜き」「4. 実行する」こと 19 ☆
    • ありがちなのは、「数学の成績が落ちてきた」という現象に対して、2も3もすっ飛ばして「じゃあ、数学の成績をあげよう」「もっと勉強の時間を長くしよう」「部活はやめなきゃ」などと短絡的にと考えてしまうこと。原因もわからないので効果的な打ち手もない。
  • 分解の木 26 ☆
    • 原因を探したり、アイディアを広げたりするのに便利
    • 最初からびっしり細かい木は書けない。メモで良いのでアイデアをリストアップ、似たものをグループ化、「ほかには何があるか」「具体的にはどういうものか」と自分に問いかけ、という手順で行っていく
    • 煮詰まったらとりあえず思いつくアイディアを全部書き出して、それから並べ替えても良い
    • コショウの例が参考になる 29
  • 原因を見極めて、打ち手を考える 34 ☆
    • 1. 原因を見極める
      • 1-A. 原因としてありえるものを洗い出す
      • 1-B. 原因の仮説を立てる
      • 1-C. どんな分析をするか考え、情報を集める
      • 1-D. 分析する
    • 2. 打ち手を考える
      • 2-A. 打ちてのアイデアを幅広く洗い出す
      • 2-B. 最適な打ち手を選択する
      • 2-C. 実行プランを作成する
  • はい、いいえの木 46
    • 原因を調べる、考える道筋を明確にする
  • 課題分析シート 49 ☆
    • 何を調べる必要があるかを明確に
    • 「具体的な課題は何か」「現時点での仮説とその根拠は何か」「仮説を確かめるには、どんな情報を集めて分析する必要があるのか」を明確に
    • 課題、仮説、根拠、分析、分析・作業、情報源の項目でまとめていく
  • 仮説の木 87
    • 話の道筋を整理する
    • 並列型(帰納的)な仮説の木と解説型(演繹的)な仮説の木
  • 意思決定ツールその1 - 良い点、悪い点リスト 106
    • 1. 選択肢を洗い出す
    • 2. 各選択肢について、良い点と悪い点を書き出す
    • 3. 各項目について3段階で評価する
  • 意思決定ツールその2 - 評価軸x評価リスト 109
    • 1. 選択肢を洗い出す
    • 2. 各選択肢について、評価軸を書き出す
    • 3. 各評価軸の重要度を3段階などで評価する

ピラミッド原則を実践で学ぶ - 「考える技術・書く技術 ワークブック<上>」を読んだ

前回「考える技術・書く技術」を読んで、書く・考える時に役立つピラミッド原則というものについてもう少し理解を深めたくなった。そこで、実践形式で書き込みながら学べる「考える技術・書く技術 ワークブック<上>」を読んだ。

考える技術・書く技術 ワークブック〈上〉

考える技術・書く技術 ワークブック〈上〉

この本は「考える技術・書く技術」での1章〜5章に書かれたルールを、実際の文章を使って適用していきながら学んでいく本だ。「考える技術・書く技術」を読むだけだと、ピラミッド原則の重要さは分かる一方で、じゃあどうやって使ったら良いかということはよくわからなかった。そのため、この本で実践すると知識が補完されて良い。

僕は「考える技術・書く技術」を読んでから、ワークブックに取り掛かった。しかし、実際には「考える技術・書く技術」を読みながらワークブックをやるというほうが効率も良く、おすすめだと思った。


この本を読んで、ピラミッド原則という、「文章を書く前にはまず自分の考えをピラミッド型に並べていき、その後に文章にする」重要性について理解出来た。しかし、自分はいろんな文章を書く前にピラミッド構造をきちんと作るとまではしないかなと思う。

一方で書く前に言いたいことをまとめましょうというのは最もだと思う。そこで、もう少し簡易的に今後は以下のようにしていくかなーと思った。

  • 箇条書きで書きたいことをとりあえず並べてみる
  • ピラミッド構造というか見出し構造に並べてみる。この時点でテーマから外れているものは削除する。
  • 見出し構造に従って書いてみる。ただし、途中でいまいち文章がまとまらなかったとしても、あまりにもおかしくならない限りは、とりあえずそのまま書き続ける。
    • ここですぐに構造整理に戻ってしまうと、ドツボにはまることも多いため
  • 書いた文章を読みつつ、構造のわかりにくい部分を整理する。ここで、見出しもがらっと変えたほうが良いと思ったら変えてしまったら良い。