Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
39
Help us understand the problem. What is going on with this article?
@gushwell

逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算

More than 1 year has passed since last update.

数回に分けて、四則演算を行う数式(例えば、(1+5) * (2+3)のような式)を入力し、その計算結果を求めるプログラムを書いて行こうと思います。

第一回目の今回は、逆ポーランド記法で表された数式を計算するクラスを定義します。

逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算 ← 当記事
逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する
逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する
逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する
逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する
逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation, RPN)とは、数式の記述方法で、演算子を被演算子の後に記述する表記法です。日本語では、後置記法とも呼ばれたりします。
この記法は、演算の優先順位を指定する括弧が不要な点が特徴のひとつです。

たとえば、(1+5) * (2+3)は、

1 5 + 2 3 + *

と記述します。

詳しくは、Wikipediaのページをご覧ください。

逆ポーランド記法で表記された数式を計算する

まずは、逆ポーランド記法を表すクラスReversePolishNotationを定義します。

ReversePolishNotationクラス

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Rpn.App {
    public class ReversePolishNotation {
        public IEnumerable<string> Tokens { get; }

        public ReversePolishNotation(IEnumerable<string> tokens) {
            Tokens = tokens.ToList();
        }

        public ReversePolishNotation(string exp) {
            var tokens = exp.Split(' ').Where(s => s != "");
            Tokens = tokens.ToList();
        }
    }
}


このクラスは、与えられた式(文字列形式)を空白で区切って、リストに保持しているだけの簡単なものです。

2つのコンストラクタとプロパティを持っています。

RpnCalculatorクラス

次に、このReversePolishNotationクラスが保持している式を計算するクラスRpnCalculatorを定義します。

Wikipediaに書かれているように、スタック(Stack<T>)クラスを利用し、計算をしています。

ReversePolishNotationクラスに保持されたリストの先頭から順に要素を取り出し、演算子でなければ(つまり数値ならば)、スタックにその値を積み、演算子だったら、スタックから値を2つ取り出し計算を行い、その結果をスタックに積みます。これを繰り返すことで、計算を行います。

例えば、1 5 + 2 3 + *ならば、

  1. リストから 1 を取り出し、スタックに積む
  2. リストから 5 を取り出し、スタックに積む
  3. リストから + を取り出す。演算子なので、スタックから値を2つ取り出し、1 + 5 を計算する。その結果の6をスタックに積む
  4. リストから 2 を取り出し、スタックに積む
  5. リストから 3 を取り出し、スタックに積む
  6. リストから + を取り出し、演算子なので、スタックから値を2つ取り出し、2 + 3 を計算する。その結果の5をスタックに積む
  7. リストから * を取り出す。演算子なので、スタックから値を2つ取り出し、5 * 6 を計算する。その結果の30をスタックに積む
  8. リストが空になったので、スタックから値(30)を取り出す。これが最終的な結果となる。

とこんな感じで、計算をしていきます。

スタックの状態は、以下のように変化します。左側がスタックのTOPです。

  1. [1]
  2. [5, 1]
  3. [6]
  4. [2, 6]
  5. [3, 2, 6]
  6. [5, 6]
  7. [30]
  8. []

これをコードにしたのが、以下のRpnCalculatorクラスです。

using System;
using System.Net;
using System.Collections.Generic;

namespace Rpn.App {
    public class RpnCalculator {
        // 後置記法を計算する
        public static decimal Calculate(ReversePolishNotation rpn) {
            Stack<object> stack = new Stack<object>();
            foreach (var token in rpn.Tokens) {
                if (IsOperator(token)) {
                    var b = (decimal)stack.Pop();
                    var a = (decimal)stack.Pop();
                    var c = Operate(a, b, token);
                    stack.Push(c);
                } else {
                    stack.Push(decimal.Parse(token));
                }
            }
            return (decimal)stack.Pop();
        }

        private static decimal Operate(decimal a, decimal b, string ope) {
            switch (ope) {
                case "+":
                    return a + b;
                case "-":
                    return a - b;
                case "*":
                    return a * b;
                default:
                    return a / b;
            }
        }

        public static bool IsOperator(string s) {
            if (s.Length == 1) {
                if (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/')
                    return true;
            }
            return false;
        }
    }
}

このクラスは、staticクラスとしました。
すべての計算が終わった時には、スタックの先頭に計算結果が入っているので、それを返すようにしています。

Mainメソッド

ここまでできれば、コンソールから逆ポーランド記法の数式を入力し、それを計算するコードは簡単に書けますね。

using System;
using System.Linq;

namespace Rpn.App {
    class Program {
        static void Main(string[] args) {
            while (true) {
                try {
                    var exp = Console.ReadLine();
                    if (exp == null)
                        break;
                    var rpn = new ReversePolishNotation(exp);
                    var s = rpn.Tokens.Aggregate((t, v) => $"{t} {v}");
                    var ans = RpnCalculator.Calculate(rpn);
                    Console.WriteLine($"{s} = {ans}");
                } catch (Exception ex) {
                    Console.WriteLine(ex.ToString());
                }
            }
        }
    }
}

Ctrl+Z<Enter>するまで、繰り返しています。

実行例

以下、実行例です。

5 9 +
5 9 + = 14

18 5 -
18 5 - = 13

4 2 + 5 3 + *
4 2 + 5 3 + * = 48

^Z
続行するには何かキーを押してください . . .

無事、実行できました。


ということで、RpnCalculator.Calculateができたので、あとは、通常の数式を逆ポーランド記法に変換することができれば、キーボードから入力された数式を計算するプログラムが書けるということですね。

ただ、数式を逆ポーランド記法に変換するのが、意外と厄介なんですよね。

次回からは、数式を逆ポーランド記法に変換して、それを計算するプログラムを少しづつ作成していきたいと思います。

続く。


この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

39
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
39
Help us understand the problem. What is going on with this article?